The asymptotic number of acyclic digraphs. I

We obtain an asymptotic formula forA _n,q , the number of digraphs withn labeled vertices,q edges and no cycles. The derivation consists of two separate parts. In the first we analyze the generating function forA _n,q so as to obtain a central limit theorem for an associated probability distribution. In the second part we show combinatorially thatA _n,q is a smooth function ofq. By combining these results, we obtain the desired asymptotic formula. Research supported by NSF under grant MCS-8300414. Research supported by NSERC under grant A4067. Research supported by NSF under grant MCS-8302282. Research supported by the Australian Department of Science and Technology under the Queen Elizabeth II Fellowship Scheme, while this author was at the University of Newcastle, Australia.     

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     

Polynomial dual network simplex algorithms

We show how to use polynomial and strongly polynomial capacity scaling algorithms for the transshipment problem to design a polynomial dual network simplex pivot rule. Our best pivoting strategy leads to an O(m ² logn) bound on the number of pivots, wheren andm denotes the number of nodes and arcs in the input network. If the demands are integral and at mostB, we also give an O(m(m+n logn) min(lognB, m logn))-time implementation of a strategy that requires somewhat more pivots.Research supported by AFOSR-88-0088 through the Air Force Office of Scientific Research, by NSF grant DOM-8921835 and by grants from Prime Computer Corporation and UPS.Research supported by NSF Research Initiation Award CCR-900-8226, by U.S. Army Research Office Grant DAAL-03-91-G-0102, and by ONR Contract N00014-88-K-0166.Research supported in part by a Packard Fellowship, an NSF PYI award, a Sloan Fellowship, and by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF grant DMS-8920550.     

Non-amenable finitely presented torsion-by-cyclic groups

Abstract. – We construct a finitely presented non-amenable group without free non-cyclic subgroups thus providing a finitely presented counterexample to von Neumann’s problem. Our group is an extension of a group of finite exponent n ≫ 1 by a cyclic group, so it satisfies the identity [x,y] ⁿ = 1. Manuscrit reĉu le 8 février 2001. RID="*" ID="*"Both authors were supported in part by the NSF grant DMS 0072307. In addition, the research of the first author was supported in part by the Russian Fund for Basic Research 99-01-00894 and by the INTAS grant, the research of the second author was supported in part by the NSF grant DMS 9978802.     

Some conjectures aboutL p norms of k-plane transforms

For 1≤k≤n-1, the k-plane transformT _k,n carries functionsf defined onR ⁿ to functionsT _k,n f defined on the set of affine k-planes inR ⁿ . It is known thatT _k,n mapsL ^p intoL ^q for certain values ofp andq. In this article we formulate conjectures for the exact values of the norm of theT _k,n , and state also a conjecture asserting that theL ^q norm ofT _k,n f changes monotonically whenf is replaced by its symmetric decreasing rearrangement. Conferenza tenuta il 6 marzo 1997 The first author was supported in part by NSF grants DMS-9206319 and DMS-9501293. The second author was supported in part by NSF grant DMS-9500840     

Note making a <Emphasis Type="Italic">K</Emphasis><Subscript>4</Subscript>-free graph bipartite

We show that every K ₄-free graph G with n vertices can be made bipartite by deleting at most n ²/9 edges. Moreover, the only extremal graph which requires deletion of that many edges is a complete 3-partite graph with parts of size n/3. This proves an old conjecture of P. Erdős. Research supported in part by NSF CAREER award DMS-0546523, NSF grant DMS-0355497, USA-Israeli BSF grant, and by an Alfred P. Sloan fellowship.     

Finding an interior point in the optimal face of linear programs

We study the problem of finding a point in the relative interior of the optimal face of a linear program. We prove that in the worst case such a point can be obtained in O(n ³ L) arithmetic operations. This complexity is the same as the complexity for solving a linear program. We also show how to find such a point in practice. We report and discuss computational results obtained for the linear programming problems in the NETLIB test set.Research supported in part by NSF Grant CCR-8810107, CCR-9019469 and a grant from GTE Laboratories.Research supported in part by NSF Grant DDM-8922636 and NSF Coop. Agr. No. CCR-8809615 through Rice University.     

The distribution of the root degree of a random permutation

Given a permutation ω of {1, …, n}, let R(ω) be the root degree of ω, i.e. the smallest (prime) integer r such that there is a permutation σ with ω = σ ^r . We show that, for ω chosen uniformly at random, R(ω) = (lnlnn − 3lnlnln n + O ^p (1))⁻¹ lnn, and find the limiting distribution of the remainder term. Research supported in part by NSF grants CCR-0225610, DMS-0505550 and ARO grant W911NF-06-1-0076. Research supported by NSF grant DMS-0406024.     

Self-similar sets of zero Hausdorff measure and positive packing measure

We prove that there exist self-similar sets of zero Hausdorff measure, but positive and finite packing measure, in their dimension; for instance, for almost everyu ∈ [3, 6], the set of all sums ∑ ₀ ⁸ a _n 4⁻ⁿ a _n 4⁻ⁿ with digits witha _n ∈ {0, 1,u} has this property. Perhaps surprisingly, this behavior is typical in various families of self-similar sets, e.g., for projections of certain planar self-similar sets to lines. We establish the Hausdorff measure result using special properties of self-similar sets, but the result on packing measure is obtained from a general complement to Marstrand’s projection theorem, that relates the Hausdorff measure of an arbitrary Borel set to the packing measure of its projections. Research of Y. Peres was partially supported by NSF grant #DMS-9803597. Research of K. Simon was supported in part by the OTKA foundation grant F019099. Research of B. Solomyak was supported in part by NSF grant #DMS 9800786, the Fulbright Foundation, and the Institute of Mathematics at The Hebrew University of Jerusalem.     

Sharpening the LYM inequality

The level sequence of a Sperner familyF is the sequencef(F)={f _i (F)}, wheref _i (F) is the number ofi element sets ofF . TheLYM inequality gives a necessary condition for an integer sequence to be the level sequence of a Sperner family on ann element set. Here we present an indexed family of inequalities that sharpen theLYM inequality.Research supported in part by Alexander v. Humboldt-StiftungResearch supported in part by NSF under grant DMS-86-06225 and AFOSR grant OSR-86-0078Research supported in part by NSF grant CCR-8911388Research supported in part by OTKA 327 0113     

Prime top extensions of division algebra

Every division algebra of degreep ^t has a prime-to-p extension which is a crossed product, ifft ≤ 2. Research of the first author supported in part by the NSA/MSP Grant MDA90-H4001 while the author was on Sabbatical at Yale University Second author is grateful for support order NSF grant DMS-8901778     

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     

Realizable posets

Certain p-local orders in n-dimensional division algebras over the rational numbers occur as endomorphism rings of torsion-free abelian groups of rank n if and only if an associated finite poset P has a strict faithful representation of dimension less than |P| over the field with p elements. In this note we obtain a simple characterization of those finite posets which do not admit such a representation.Research supported in part by NSF grant DMS-8802833.     

On the computation of the projective surgery obstruction groups

The computation of the projective surgery obstruction groupsL _n ^p (ZG), forG a hyperelementary finite group, is reduced to standard calculations in number theory, mostly involving class groups. Both the exponent of the torsion subgroup and the precise divisibility of the signatures are determined. ForG a 2-hyperelementary group, theL _n ^p (ZG) are detected by restriction to certain subquotients ofG, and a complete set of invariants is given for oriented surgery obstructions.Partially supported by NSERC grant A4000.Partially supported by NSF grant DMS-8610730(1) and the Danish Research Council.     

Vertical decompositions for triangles in 3-space

We prove that, for any constant ɛ>0, the complexity of the vertical decomposition of a set ofn triangles in three-dimensional space isO(n ^2+ɛ +K), whereK is the complexity of the arrangement of the triangles. For a single cell the complexity of the vertical decomposition is shown to beO(n ^2+ɛ ). These bounds are almost tight in the worst case. We also give a deterministic output-sensitive algorithm for computing the vertical decomposition that runs inO(n ² logn+V logn) time, whereV is the complexity of the decomposition. The algorithm is reasonably simple (in particular, it tries to perform as much of the computation in two-dimensional spaces as possible) and thus is a good candidate for efficient implementations. The algorithm is extended to compute the vertical decomposition of arrangements ofn algebraic surface patches of constant maximum degree in three-dimensional space in timeO(nλ _q (n) logn +V logn), whereV is the combinatorial complexity of the vertical decomposition, λ _q (n) is a near-linear function related to Davenport-Schinzel sequences, andq is a constant that depends on the degree of the surface patches and their boundaries. We also present an algorithm with improved running time for the case of triangles which is, however, more complicated than the first algorithm. Mark de Berg was supported by the Dutch Organization for Scientific Research (N.W.O.), and by ESPRIT Basic Research Action No. 7141 (project ALCOM II:Algorithms and Complexity). Leonidas Guibas was supported by NSF Grant CCR-9215219, by a grant from the Stanford SIMA Consortium, by NSF/ARPA Grant IRI-9306544, and by grants from the Digital Equipment, Mitsubishi, and Toshiba Corporations. Dan Halperin was supported by a Rothschild Postdoctoral Fellowship, by a grant from the Stanford Integrated Manufacturing Association (SIMA), by NSF/ARPA Grant IRI-9306544, and by NSF Grant CCR-9215219. A preliminary version of this paper appeared inProc. 10th ACM Symposium on Computational Geometry, 1994, pp. 1–10.     

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.     

Quasiconformal homogeneity of hyperbolic manifolds

We exhibit strong constraints on the geometry and topology of a uniformly quasiconformally homogeneous hyperbolic manifold. In particular, if n3, a hyperbolic n-manifold is uniformly quasiconformally homogeneous if and only if it is a regular cover of a closed hyperbolic orbifold. Moreover, if n3, we show that there is a constant K_n>1 such that if M is a hyperbolic n-manifold, other than which is K–quasiconformally homogeneous, then KK_n.Mathematics Subject Classification (2000): 30C60Research supported in part by NSF grant 070335 and 0305704.Research supported in part by NSF grant 0203698.Research supported in part by the NZ Marsden Fund and the Royal Society (NZ).Research supported in part by NSF grant 0305704.     

Forbidding Complete Hypergraphs as Traces

Let 2 ≤q ≤min{p, t − 1} be fixed and n → ∞. Suppose that is a p-uniform hypergraph on n vertices that contains no complete q-uniform hypergraph on t vertices as a trace. We determine the asymptotic maximum size of in many cases. For example, when q = 2 and p∈{t, t + 1}, the maximum is , and when p = t = 3, it is for all n≥ 3. Our proofs use the Kruskal-Katona theorem, an extension of the sunflower lemma due to Füredi, and recent results on hypergraph Turán numbers. Research supported in part by NSF grants DMS-0400812 and an Alfred P. Sloan Research Fellowship. Research supported in part by NSA grant H98230-06-1-0140. Part of the research conducted while his working at University of Illinois at Chicago as a NSF VIGRE postdot.     

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.     

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.