Groups with small Dehn functions and bipartite chord diagrams

We introduce a new invariant of bipartite chord diagrams and use it to construct the first examples of groups with Dehn function n²log n. Some of these groups have undecidable conjugacy problem. Our groups are multiple HNN extensions of free groups. We show that n²log n is the smallest Dehn function of a multiple HNN extension of a free group with undecidable conjugacy problem. Both authors were supported in part by the NSF grants DMS 0245600 and DMS 0455881. In addition, the research of the first author was supported in part by the Russian Fund for Basic Research 05-01-00895, the research of the second author was supported in part by the NSF grant DMS 9978802 and the US-Israeli BSF grant 1999298. Received: February 2005; Revision: September 2005; Accepted: September 2005     

Strongly meager sets can be quite big

AssumeCH. There exists a strongly meager setX⊆2^ω and a continuous functionF: 2^ω → 2^ω such thatF″ (X)=2^ω. The analogous statement for the strong measure zero, the notion dual to strongly meager, is false. The first author was partially supported by NSF grant DMS 9971282 and the Alexander von Humboldt Foundation. The second author was partially supported by grant BW 5100-5-0231-2.     

The prison yard problem

Given a polygon II withn vertices whose sides arewalls. Guards, located at vertices can see all directions, but cannot see beyond walls. We prove that at most [n/2] guards suffice to see everywhere the whole plane. If II is not convex, then [n/2] suffice.The research was done while this author visited the Department of Mathematics at Rutgers University. Research supported in part by the Hungarian National Science Foundation under grant No. 1812Supported in part by NSF grant DMS 86-06225 and AF grant OSR-86-0078     

Collapsed Riemannian manifolds with bounded diameter and bounded covering geometry

We study the class ofn-Riemannian manifolds in the title such that the torsion elements in the fundamental group have a definite bound on their orders. Our main result asserts the existence of a kind of generalized Seifert fiber structure onM ⁿ , for which the fundamental group of fibers injects into that ofM ⁿ . This provides a necessary and sufficient topological condition for a manifold to admit a sufficiently collapsed metric in our class. Among other consequences we obtain a strengthened version of the gap conjecture in this context.The work of the first author is partially supported by NSF Grant DMS 9303999. The work of the second author is supported by MSRI through NSF grant DMS 9022140 and partially supported by NSF Grant DMS 9204095.     

Wiggly sets and limit sets

We show that a compact, connected set which has uniform oscillations at all points and at all scales has dimension strictly larger than 1. We also show that limit sets of certain Kleinian groups have this property. More generally, we show that ifG is a non-elementary, analytically finite Kleinian group, and its limit set Λ(G) is connected, then Λ(G) is either a circle or has dimension strictly bigger than 1. The first author is partially supported by NSF Grant DMS 95-00577 and an Alfred P. Sloan research fellowship. The second author is partially supported by NSF grant DMS-94-23746.     

Intersecting Curves in the Plane

 We prove that for every family of n pairwise intersecting simple closed planar curves in general position, at least (4/5)n ²−O(n) points lie on more than one curve. This improves the previous lower bound of (3/4)n ²−O(n) due to Richter and Thomassen. Received: March 29, 2000 Final version received: August 30, 2001 RID="*" ID="*" Research supported in part by NSF grant DMS-9970325 Acknowledgments. I thank Bruce Richter for informing me about this problem, Gelasio Salazar for reading a preliminary version of the paper, and a Referee for useful comments. Current Address: Microsoft Research, One Microsoft Way, Redmond, WA 98052-6399, USA. e-mail: mubayi@microsoft.com 1991 Mathematics Subject Classification. 05C35, 52C10     

Toeplitz Operators on Analytic Besov Spaces

We characterize complex measures μ on the unit disk for which the Toeplitz operator T _μ is bounded or compact on the analytic Besov spaces B _p with 1 ≤ p < ∞. Research supported in part by NSF grant, DMS 0200587 (first author); and by a NSERC grant (third author).     

The moduli space of complete embedded constant mean curvature surfaces

We examine the space of finite topology surfaces in ³ which are complete, properly embedded and have nonzero constant mean curvature. These surfaces are noncompact provided we exclude the case of the round sphere. We prove that the spaceM _k of all such surfaces withk ends (where surfaces are identified if they differ by an isometry of ³) is locally a real analytic variety. When the linearization of the quasilinear elliptic equation specifying mean curvature equal to one has noL ²-nullspace, we prove thatM _k is locally the quotient of a real analytic manifold of dimension 3k–6 by a finite group (i.e. a real analytic orbifold), fork 3. This finite group is the isotropy subgroup of the surface in the group of Euclidean motions. It is of interest to note that the dimension ofM _k is independent of the genus of the underlying punctured Riemann surface to which is conformally equivalent. These results also apply to hypersurfaces of H ⁿ⁺¹ with nonzero constant mean curvature greater than that of a horosphere and whose ends are cylindrically bounded.Research of the first author supported in part by NSF grant # DMS9404278 and an NSF Postdoctoral Fellowship, of the second auther by NSF Young Investigator Award, a Sloan Foundation Postdoctoral Fellowship and NSF grant # DMS9303236, and of the third author by NSF grant # DMS9022140 and an NSF Postdoctoral Fellowship.     

Branched two-sheeted covers

In this paper we explore the connection between Weierstrass points of subspaces of the holomorphic differentials and the geometry of the canonical curve inPC ^g−1. In particular, we consider non-hyperelliptic Riemann surfaces with involution and the Weierstrass points of the −1 eigenspace of the holomorphic differentials. The case of coverings of a torus is considered in detail. Research of the first author supported in part by the Paul and Gabriella Rosenbaum Foundation, the Landau Center for Research in Mathematical Analysis (supported by Minerva Foundation-Germany) and a US-Israel BSF grant. Research by the second author supported in part by NSF Grant DMS 9003361 and a Lady Davis Visiting Professorship at the Hebrew University.     

Combinatorial interior point methods for generalized network flow problems

 We present combinatorial interior point methods for the generalized minimum cost flow and the generalized circulation problems based on Wallacher and Zimmermann's combinatorial interior point method for the minimum cost network flow problem. The algorithms have features of both a combinatorial algorithm and an interior point method. They work towards optimality by iteratively reducing the value of a potential function while maintaining interior point solutions. At each iteration, flow is augmented along a generalized circulation, which is computed by solving a TVPI (Two Variables Per Inequality) system. The algorithms run in time, where m and n are, respectively, the number of arcs and nodes in the graph, and L is the length of the input data. Received: June 1, 2001 / Accepted: May 23, 2002-08-22 Published online: September 27, 2002 RID="*" ID="*" This research was supported in part by NSF Grants DMS 94-14438, DMS 95-27124, CDA 97-26385 and DMS 01-04282, and DOE Grant DE-FG02-92ER25126 Mathematics Subject Classification (2000): 20E28, 20G40, 20C20     

The complex of maximal lattice free simplices

The simplicial complexK(A) is defined to be the collection of simplices, and their proper subsimplices, representing maximal lattice free bodies of the form (x: Axb), withA a fixed generic (n + 1) ×n matrix. The topological space associated withK(A) is shown to be homeomorphic to ⁿ , and the space obtained by identifying lattice translates of these simplices is homeorphic to then-torus.Corresponding author.The first author was partially supported by Hungarian NSF grants 1907 and 1909, and also by U.S. NSF grant CCR-9111491. The research of the second author was supported by DMS9103608 and the third author by NSF grant SES9121936.     

On the support of harmonic measure for the random walk

We show that harmonic measure for the simple random walk on then ×…×n cube in thed-dimensional lattice is supported on o(n ^d ) vertices. This research was supported in part by NSF grant # DMS-9353149.     

The intersection of the powers of the radical in Noetherian P.I. rings

LetR be a ring and J its radical. DefineJ ₁=∩Jⁿ, J₂=∩J ₁ ⁿ ,…,… J_k=∩J _k−1 ⁿ .... It is shown that in a ringR satisfying a polynomial identity and the ascending chain condition on ideals,J _k =0 for some appropriatek. The work of the first author was supported by an NSF grant at the University of Chicago. The work of the second author was supported by an NSF grant at the University of California, San Diego.     

Modified Busemann-Petty problem on sections of convex bodies

The Busemann-Petty problem asks whether convex origin-symmetric bodies in ℝ ⁿ with smaller central hyperplane sections necessarily have smallern-dimensional volume. It is known that the answer is affirmative ifn≤4 and negative ifn≥5. In this article we replace the assumptions of the original Busemann-Petty problem by certain conditions on the volumes of central hyperplane sections so that the answer becomes affirmative in all dimensions. The first-named author was supported in part by the NSF grant DMS-0136022 and by a grant from the University of Missouri Research Board.     

Bootstrap percolation on the hypercube

In the bootstrap percolation on the n-dimensional hypercube, in the initial position each of the 2ⁿ sites is occupied with probability p and empty with probability 1−p, independently of the state of the other sites. Every occupied site remains occupied for ever, while an empty site becomes occupied if at least two of its neighbours are occupied. If at the end of the process every site is occupied, we say that the (initial) position spans the hypercube. We shall show that there are constants c₁,c₂>0 such that for the probability of spanning tends to 1 as n→∞, while for the probability tends to 0. Furthermore, we shall show that for each n the transition has a sharp threshold function. J. Balogh: work was done while at The University of Memphis, USA Research supported in part by NSF grant DMS0302804 Research supported in part by NSF grant ITR 0225610 and DARPA grant F33615-01-C-1900     

Polynomial systems with few real zeroes

We study some systems of polynomials whose support lies in the convex hull of a circuit, giving a sharp upper bound for their numbers of real solutions. This upper bound is non-trivial in that it is smaller than either the Kouchnirenko or the Khovanskii bounds for these systems. When the support is exactly a circuit whose affine span is ℤⁿ, this bound is 2n+1, while the Khovanskii bound is exponential in n². The bound 2n+1 can be attained only for non-degenerate circuits. Our methods involve a mixture of combinatorics, geometry, and arithmetic. Part of work done at MSRI was supported by NSF grant DMS-9810361. Work of Sottile is supported by the Clay Mathematical Institute. Sottile and Bihan were supported in part by NSF CAREER grant DMS-0134860. Bertrand is supported by the European research network IHP-RAAG contract HPRN-CT-2001-00271.     

On the connected components of the space of line transversals to a family of convex sets

Let ℒ be the space of line transversals to a finite family of pairwise disjoint compact convex sets in ℝ³. We prove that each connected component of ℒ can itself be represented as the space of transversals to some finite family of pairwise disjoint compact convex sets. The research of J. E. Goodman was supported in part by NSF Grant DMS91-22065 and by NSA Grant MDA904-92-H-3069. R. Pollack's research was supported in part by NSF Grant CCR91-22103 and by NSA Grant MDA904-92-H-3075. The research of R. Wenger was supported in part by NSA Grant MDA904-93-H-3026 and by the NSF Regional Geometry Institute (Smith College, July 1993) Grant DMS90-13220.     

Two-letter group codes that preserve aperiodicity of inverse finite automata

We construct group codes over two letters (i.e., bases of subgroups of a two-generated free group) with special properties. Such group codes can be used for reducing algorithmic problems over large alphabets to algorithmic problems over a two-letter alphabet. Our group codes preserve aperiodicity of inverse finite automata. As an application we show that the following problems are PSpace-complete for two-letter alphabets (this was previously known for large enough finite alphabets): The intersection-emptiness problem for inverse finite automata, the aperiodicity problem for inverse finite automata, and the closure-under-radical problem for finitely generated subgroups of a free group. The membership problem for 3-generated inverse monoids is PSpace-complete. Both authors were supported in part by NSF grant DMS-9970471. The first author was also supported in part by NSF grant CCR-0310793. The second author acknowledges the support of the Excellency Center, “Group Theoretic Methods for the Study of Algebraic Varieties” of the Israeli Science Foundation.     

Compact deformations of Fuchsian groups

A conformal map Φ on the unit disk is called a compact deformation of a Fuchsian groupG if Φ has a quasiconformal extension to the planeh which conjugatesG to a Kleinian group G′ and the dilatation ofh is compactly supported moduloG. We show that for such deformations δ = dim(∧(G′)) = dim(∧_c(G′)) (if δ ≥1) and the image of ∧_e = ∧ ∧_c is contained in a countable union of rectifiable curves and has zero length iffG is divergence type. The first author is partially supported by NSF Grant DMS 01-03626. The second author is partially supported by NSF grant DMS-99-71311.     

Ehrhart polynomials and stringy Betti numbers

We study the connection between stringy Betti numbers of Gorenstein toric varieties and the generating functions of the Ehrhart polynomials of certain polyhedral regions. We use this point of view to give counterexamples to Hibi's conjecture on the unimodality of δ-vectors of reflexive polytopes. The first author was partially supported by NSF grant DMS 0500127 and the second author was supported by a Graduate Research Fellowship from the NSF