Isolation and the high/low hierarchy

 Say that a d.c.e. degree d is isolated by a c.e. degree b, if b<d and any c.e. degree c below d is also below b, namely, b is the largest c.e. degree below d. Wu proved that there is a high d.c.e. degree d isolated by a low₂ c.e. degree b. In this paper, we improve this result by making b low, not merely low₂. RID="ID=" <E5>Mathematics Subject Classification (2000):</E5> 03D25, 03D30, 03D35 RID="ID=" <E5>Key words or phrases:</E5> Computably enumerable set &ndash; d.c.e. degree &ndash; Isolation &ndash; High/low hierarchy RID="ID=" Ishmukhametov's research is supported by RFBR grant 01-01-00733, and Wu's research is supported by the Marsden Fund of New Zealand. Wu would like to thank his supervisor, Prof. Rod Downey, for his many helpful suggestions and comments. Received: 31 January 2001 / Published online: 25 February 2002 RID=" ID=" <E5>Mathematics Subject Classification (2000):</E5> 03D25, 03D30, 03D35 RID=" ID=" <E5>Key words or phrases:</E5> Computably enumerable set &ndash; d.c.e. degree &ndash; Isolation &ndash; High/low hierarchy RID=" ID=" Ishmukhametov's research is supported by RFBR grant 01-01-00733, and Wu's research is supported by the Marsden Fund of New Zealand. Wu would like to thank his supervisor, Prof. Rod Downey, for his many helpful suggestions and comments.     

The algebraic structure of the isomorphic types of tally,polynomial time computable sets

 We investigate the polynomial time isomorphic type structure of (the class of tally, polynomial time computable sets). We partition P _T into six parts: D ⁻, D^ ⁻ , C, S, F, F^, and study their p-isomorphic properties separately. The structures of , , and are obvious, where F, F^, and C are the class of tally finite sets, the class of tally co-finite sets, and the class of tally bi-dense sets respectively. The following results for the structures of and will be proved, where D^ is the class of tally, co-dense, polynomial time computable sets and S is the class of tally, scatted (i.e., neither dense nor co-dense), polynomial time computable sets. 1. is a countable distributive lattice with the greatest element. 2. Infinitely many intervals in can be distinguished by first order formulas. 3. There exist infinitely many nontrivial automorphisms for . 4. is not distributive, but any interval in is a countable distributive lattice. RID="ID=" <E5>Mathematics Subject Classification (2000):</E5> 03D15, 03D25, 03D30, 03D35, 06A06, 06B20 RID="ID=" <E5>Key words or phrases:</E5> Computational complexity &ndash; Polynomial time &ndash; Degree structure &ndash; Lattice &ndash; Isomorphism RID="ID=" Part of this work was done when the author was a PhD student at the University of Heidelberg under the direction of Professor Ambos-Spies. Received: 23 July 1999 / Published online: 27 March 2002 RID=" ID=" <E5>Mathematics Subject Classification (2000):</E5> 03D15, 03D25, 03D30, 03D35, 06A06, 06B20 RID=" ID=" <E5>Key words or phrases:</E5> Computational complexity &ndash; Polynomial time &ndash; Degree structure &ndash; Lattice &ndash; Isomorphism RID=" ID=" Part of this work was done when the author was a PhD student at the University of Heidelberg under the direction of Professor Ambos-Spies.     

Finality regained: A coalgebraic study of Scott-sets and multisets

 In this paper we study iterated circular multisets in a coalgebraic framework. We will produce two essentially different universes of such sets. The unisets of the first universe will be shown to be precisely the sets of the Scott universe. The unisets of the second universe will be precisely the sets of the AFA-universe. We will have a closer look into the connection of the iterated circular multisets and arbitrary trees. RID="ID=" <E5>Mathematics Subject Classification (2000):</E5> 03B45, 03E65, 03E70, 18A15, 18A22, 18B05, 68Q85 RID="ID=" <E5>Key words or phrases:</E5> Multiset &ndash; Non-wellfounded set &ndash; Scott-universe &ndash; AFA &ndash; Coalgebra &ndash; Modal logic &ndash; Graded modalities Received: 15 March 2000 / Published online: 25 February 2002 RID=" ID=" <E5>Mathematics Subject Classification (2000):</E5> 03B45, 03E65, 03E70, 18A15, 18A22, 18B05, 68Q85 RID=" ID=" <E5>Key words or phrases:</E5> Multiset &ndash; Non-wellfounded set &ndash; Scott-universe &ndash; AFA &ndash; Coalgebra &ndash; Modal logic &ndash; Graded modalities     

Extensions of Hałkowska–Zajac's three-valued paraconsistent logic

 As it was proved in [4, Sect. 3], the poset of extensions of the propositional logic defined by a class of logical matrices with equationally-definable set of distinguished values is a retract, under a Galois connection, of the poset of subprevarieties of the prevariety generated by the class of the underlying algebras of the defining matrices. In the present paper we apply this general result to the three-valued paraconsistent logic proposed by Hałkowska–Zajac [2]. Studying corresponding prevarieties, we prove that extensions of the logic involved form a four-element chain, the only proper consistent extensions being the least non-paraconsistent extension of it and the classical logic. RID="ID=" <E5>Mathematics Subject Classification (2000):</E5> 03B50, 03B53, 03G10 RID="ID=" <E5>Key words or phrases:</E5> Many-valued logic &ndash; Paraconsistent logic &ndash; Extension &ndash; Prevariety &ndash; Distributive lattice Received 12 August 2000 / Published online: 25 February 2002 RID=" ID=" <E5>Mathematics Subject Classification (2000):</E5> 03B50, 03B53, 03G10 RID=" ID=" <E5>Key words or phrases:</E5> Many-valued logic &ndash; Paraconsistent logic &ndash; Extension &ndash; Prevariety &ndash; Distributive lattice     

Strongly meager and strong measure zero sets

 In this paper we present two consistency results concerning the existence of large strong measure zero and strongly meager sets. RID="ID=" <E5>Mathematics Subject Classification (2000):</E5>&ensp;03E35 RID="ID=" The first author was supported by Alexander von Humboldt Foundation and NSF grant DMS 95-05375. The second author was partially supported by Basic Research Fund, Israel Academy of Sciences, publication 658 Received: 6 January 1999 / Revised version: 20 July 1999 / Published online: 25 February 2002 RID=" ID=" <E5>Mathematics Subject Classification (2000):</E5>&ensp;03E35 RID=" ID=" The first author was supported by Alexander von Humboldt Foundation and NSF grant DMS 95-05375. The second author was partially supported by Basic Research Fund, Israel Academy of Sciences, publication 658     

Propagation of polarization in elastodynamics with residual stress and travel times

 We show that knowing the displacement-to-traction map associated to the equations of isotropic elastodynamics with residual stress we can determine the lens maps of compressional and shear waves. We derive several consequences of this for the inverse problem of determining the residual stress and the Lamé parameters from the displacement-to-traction map. Received: 6 December 2001 / Revised version: 29 October 2002 / Published online: 8 April 2003 RID="⋆" ID="⋆" The author thanks the Department of Mathematics at the University of Washington for its hospitality during his visit in fall 2000. RID="⋆⋆" ID="⋆⋆" Partly supported by NSF grant DMS-0070488 and a John Simon Guggenheim fellowship. The author also thanks MSRI for partial support and for providing a very stimulating environment during the inverse problems program in fall 2001.     

Injective hulls are not natural

In a category with injective hulls and a cogenerator, the embeddings into injective hulls can never form a natural transformation, unless all objects are injective. In particular, assigning to a field its algebraic closure, to a poset or Boolean algebra its Mac-Neille completion, and to an R-module its injective envelope is not functorial, if one wants the respective embeddings to form a natural transformation. Received January 21, 2000; accepted in final form August 10, 2001. RID="h1" RID="h2" RID="h3" ID="h1"The hospitality of York University is gratefully acknowledged by the first author. ID="h2"Third author partially supported by the Grant Agency of the Czech Republic under Grant no. 201/99/0310, and the hospitality of York University is also acknowledged. ID="h3"Partial financial assistance by the Natural Sciences and Engineering Councel of Canada is acknowledged by the fourth author.     

Isosceles Triangles Determined by a Planar Point Set

 It is proved that, for any ɛ>0 and n>n ₀(ɛ), every set of n points in the plane has at most triples that induce isosceles triangles. (Here e denotes the base of the natural logarithm, so the exponent is roughly 2.136.) This easily implies the best currently known lower bound, , for the smallest number of distinct distances determined by n points in the plane, due to Solymosi–Cs. Tóth and Tardos. Received: February, 2002 Final version received: September 15, 2002 RID="*" ID="*" Supported by NSF grant CCR-00-86013, PSC-CUNY Research Award 63382-00-32, and OTKA-T-032452 RID="†" ID="†" Supported by OTKA-T-030059 and AKP 2000-78-21     

A uniqueness result for a Neumann problem involving the critical Sobolev exponent

 In this paper we consider the problem

Homotopy equivalences of p-completed classifying spaces of finite groups

We study homotopy equivalences of p-completions of classifying spaces of finite groups. To each finite group G and each prime p, we associate a finite category ℒ _p ^c (G) with the following properties. Two p-completed classifying spaces BG _p ^∧ and BG’ _p ^∧ have the same homotopy type if and only if the associated categories ℒ _p ^c (G) and ℒ _p ^c (G’) are equivalent. Furthermore, the topological monoid Aut(BG _p ^∧) of self equivalences is determined by the self equivalences of the associated category ℒ _p ^c (G). Oblatum 5-VII-2001 & 28-VIII-2002?Published online: 8 November 2002 RID="*" ID="*"C. Broto is partially supported by DGICYT grant PB97–0203. RID="**" ID="**"R. Levi is partially supported by EPSRC grant GR/M7831. RID="***" ID="***"B. Oliver is partially supported by UMR 7539 of the CNRS.     

On Bipartite Graphs with Linear Ramsey Numbers

Dedicated to the memory of Paul Erdős We provide an elementary proof of the fact that the ramsey number of every bipartite graph H with maximum degree at most is less than . This improves an old upper bound on the ramsey number of the n-cube due to Beck, and brings us closer toward the bound conjectured by Burr and Erdős. Applying the probabilistic method we also show that for all and there exists a bipartite graph with n vertices and maximum degree at most whose ramsey number is greater than for some absolute constant c>1. Received December 1, 1999 RID="*" ID="*" Supported by NSF grant DMS-9704114 RID="**" ID="**" Supported by KBN grant 2 P03A 032 16     

A computational study of a gradient-based log-barrier algorithm for a class of large-scale SDPs

 The authors of this paper recently introduced a transformation [4] that converts a class of semidefinite programs (SDPs) into nonlinear optimization problems free of matrix-valued constraints and variables. This transformation enables the application of nonlinear optimization techniques to the solution of certain SDPs that are too large for conventional interior-point methods to handle efficiently. Based on the transformation, we proposed a globally convergent, first-order (i.e., gradient-based) log-barrier algorithm for solving a class of linear SDPs. In this paper, we discuss an efficient implementation of the proposed algorithm and report computational results on semidefinite relaxations of three types of combinatorial optimization problems. Our results demonstrate that the proposed algorithm is indeed capable of solving large-scale SDPs and is particularly effective for problems with a large number of constraints. Received: June 22, 2001 / Accepted: January 20, 2002 Published online: December 9, 2002 RID="†" ID="†"Computational results reported in this paper were obtained on an SGI Origin2000 computer at Rice University acquired in part with support from NSF Grant DMS-9872009. RID="⋆" ID="⋆"This author was supported in part by NSF Grants CCR-9902010, INT-9910084 and CCR-0203426 RID="⋆⋆" ID="⋆⋆"This author was supported in part by NSF Grants CCR-9902010, INT-9910084 and CCR-0203113 RID="⋆⋆⋆" ID="⋆⋆⋆"This author was supported in part by DOE Grant DE-FG03-97ER25331, DOE/LANL Contract 03891-99-23 and NSF Grant DMS-9973339. Key Words. semidefinite program – semidefinite relaxation – nonlinear programming – interior-point methods – limited memory quasi-Newton methods. Mathematics Subject Classification (1991): 90C06, 90C27, 90C30.     

Van Kampen’s embedding obstruction for discrete groups

We give a lower bound to the dimension of a contractible manifold on which a given group can act properly discontinuously. In particular, we show that the n-fold product of nonabelian free groups cannot act properly discontinuously on ℝ^{2 n −1}. Oblatum 19-I-2001 & 29-V-2002?Published online: 5 September 2002 RID="*" ID="*"All three authors gratefully acknowledge the support by the National Science Foundation.     

Subharmonic functions on Carnot groups

 Many results of classical Potential Theory are extended to sub-Laplacians ▵_𝔾 on Carnot groups 𝔾. Some characterizations of ▵_𝔾-subharmonicity, representation formulas of Poisson-Jensen's kind and Nevanlinna-type theorems are proved. We also characterize the Riesz-measure related to bounded-above ▵_𝔾-subharmonic functions in ℝ ^N . Received: 21 June 2000 / Revised version: 12 March 2002 / Published online: 2 December 2002 RID="★" ID="★" Investigation supported by University of Bologna. Funds for selected research topics. Mathematics Subject Classification (2000): 31B05, 35J70, 35H20     

Graph partitioning using linear and semidefinite programming

 Graph partition is used in the telecommunication industry to subdivide a transmission network into small clusters. We consider both linear and semidefinite relaxations for the equipartition problem and present numerical results on real data from France Telecom networks with up 900 nodes, and also on randomly generated problems. Received: August 8, 2001 / Accepted: November 9, 2001 Published online: December 9, 2002 RID="★★" ID="★★" This research was carried out while this author was working at France Telecom R & D, 38–40 rue du Général Leclerc, F-92794 Issy-Les-Moulineaux Cedex 9, France. RID="★" ID="★" This author greatfully acknowledges financial support from the Austrian Science Foundation FWF Project P12660-MAT. Key words. graph partitioning – semidefinite programming     

Degree complexity for a modified pigeonhole principle

 We consider a modification of the pigeonhole principle, M P H P, introduced by Goerdt in [7]. M P H P is defined over n pigeons and log n holes, and more than one pigeon can go into a hole (according to some rules). Using a technique of Razborov [9] and simplified by Impagliazzo, Pudlák and Sgall [8], we prove that any Polynomial Calculus refutation of a set of polynomials encoding the M P H P, requires degree Ω(log n). We also prove a simple Lemma giving a simulation of Resolution by Polynomial Calculus. Using this lemma, and a Resolution upper bound by Goerdt [7], we obtain that the degree lower bound is tight. Our lower bound establishes the optimality of the tree-like Resolution simulation by the Polynomial Calculus given in [6]. Received: 29 March 2001 / Published online: 2 September 2002 RID="⋆" ID="⋆" A prelimianry version appeared as part of the paper A Study of Proof Search Algorithms for Resolution and Polynomial Calculus published in the Proceedings of the 40-th IEEE Conference on Foundations of Computer Science, 1999 RID="†" ID="†" Partly supported by Project CICYT, TIC 98-0410-C02-01 and Promoción General del Conocimiento PB98-0937-C04-03. RID="††" ID="††" Part of this work was done while the author was a member of the School of Mathematics at Institute for Advanced Study supported by a NSF grant n. 9987845     

On the existence of large subsets of [λ]κ which contain no unbounded non-stationary subsets RID="★"ID="★" Publication number 698 in author's list. Partially supported by the Israel Science Foundation.

 Here we deal with some problems posed by Matet. The first section deals with the existence of stationary subsets of [λ]^<κ with no unbounded subsets which are not stationary, where, of course, κ is regular uncountable ≤λ. In the second section we deal with the existence of such clubs. The proofs are easy but the result seems to be very surprising. Theorem 1.2 was proved some time ago by Baumgartner (see Theorem 2.3 of [Jo88]) and is presented here for the sake of completeness. Received: 10 December 1998 / Revised version: 2 February 1999 / Published online: 27 March 2002 RID="&starf;" ID="&starf;" Publication number 698 in author's list. Partially supported by the Israel Science Foundation.     

Vertex Covers by Edge Disjoint Cliques

Dedicated to the memory of Paul Erdős Let H be a simple graph having no isolated vertices. An (H,k)-vertex-cover of a simple graph G = (V,E) is a collection of subgraphs of G satisfying 1.  , for all i = 1, ..., r, 2.  , 3.  , for all , and 4.  each is in at most k of the . We consider the existence of such vertex covers when H is a complete graph, , in the context of extremal and random graphs. Received October 31, 1999 RID="*" ID="*" Supported in part by NSF grant DMS-9627408. RID="†" ID="†" Supported in part by NSF grant CCR-9530974. RID="‡" ID="‡" Supported in part by OTKA Grants T 030059 and T 29074, FKFP 0607/1999 and by the Bolyai Foundation. RID="§" ID="§" Supported in part by NSF grant DMS-9970622.     

On complexity reduction of Σ<Subscript>1</Subscript> formulas

 For a fixed q  ℕ and a given Σ₁ definition φ(d,x), where d is a parameter, we construct a model M of 1 Δ₀ + ? exp and a non standard d  M such that in M either φ has no witness smaller than d or phgr; is equivalent to a formula ϕ(d,x) having no more than q alternations of blocks of quantifiers. Received: 29 September 1998 / Revised version: 7 November 2001 Published online: 10 October 2002 RID="⋆" ID="⋆" Research supported in part by The State Committee for Scientific Research (Poland), KBN, grant number 2 PO3A 018 13. RID="⋆" ID="⋆" Research supported in part by The State Committee for Scientific Research (Poland), KBN, grant number 2 PO3A 018 13.