Towards a characterization of generalized twisted field planes

In this work we study semifield planes of orderq ⁿ(q=p ^r ,p prime) with a collineation whose order is ap-primitive divisor ofq ⁿ–1.Research supported in part by NSF Grant No. DMS-9107372Research supported in part by NSF grants RII-9014056, component IV of the EPSCoR of Puerto Rico grant and ARO grant for Cornell MSI.     

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.     

Upper bounds for configurations and polytopes inR d

We give a new upper bound onn ^d(d+1)n on the number of realizable order types of simple configurations ofn points inR ^d , and ofn2d ² n on the number of realizable combinatorial types of simple configurations. It follows as a corollary of the first result that there are no more thann ^d(d+1)n combinatorially distinct labeled simplicial polytopes inR ^d withn vertices, which improves the best previous upper bound ofn ^{cn d/2}.Supported in part by NSF Grant DMS-8501492 and PSC-CUNY Grant 665258.Supported in part by NSF Grant DMS-8501947.     

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.     

Cyclotomic and simplicial matroids

We show that two naturally occurring matroids representable over ℚ are equal: thecyclotomic matroid μ_n represented by then ^th roots of unity 1, ζ, ζ², …, ζ^n-1 inside the cyclotomic extension ℚ(ζ), and a direct sum of copies of a certain simplicial matroid, considered originally by Bolker in the context of transportation polytopes. A result of Adin leads to an upper bound for the number of ℚ-bases for ℚ(ζ) among then ^th roots of unity, which is tight if and only ifn has at most two odd prime factors. In addition, we study the Tutte polynomial of μ_n in the case thatn has two prime factors. First author supported by NSF Postdoctoral Fellowship. Second author supported by NSF grant DMS-0245379.     

Lower bounds for boundary roughness for droplets in Bernoulli percolation

We consider boundary roughness for the ``droplet' created when supercritical two-dimensional Bernoulli percolation is conditioned to have an open dual circuit surrounding the origin and enclosing an area at least l², for large l. The maximum local roughness is the maximum inward deviation of the droplet boundary from the boundary of its own convex hull; we show that for large l this maximum is at least of order l^1/3(logl)^–2/3. This complements the upper bound of order l^1/3(logl)^–2/3 proved in [Al3] for the average local roughness. The exponent 1/3 on l here is in keeping with predictions from the physics literature for interfaces in two dimensions. The research of the first author was supported by NSF grant DMS-9802368. The research of the second author was supported by NSF grants DMS-9802368 and DMS-0103790.Mathematics Subject Classification (2000): Primary 60K35; Secondary 82B20, 82B43     

Dynamical Borel-Cantelli lemmas for gibbs measures

LetT: X→X be a deterministic dynamical system preserving a probability measure μ. A dynamical Borel-Cantelli lemma asserts that for certain sequences of subsetsA _n ⊃ X and μ-almost every pointx∈X the inclusionT ⁿ x∈A _n holds for infinitely manyn. We discuss here systems which are either symbolic (topological) Markov chain or Anosov diffeomorphisms preserving Gibbs measures. We find sufficient conditions on sequences of cylinders and rectangles, respectively, that ensure the dynamical Borel-Cantelli lemma. Partially supported by NSF grant DMS-9732728. Partially supported by NSF grant DMS-9704489.     

On 2-Detour Subgraphs of the Hypercube

A spanning subgraph H of a graph G is a 2-detour subgraph of G if for each x, y ∈ V(G), d _H (x, y) ≤ d _G (x, y) + 2. We prove a conjecture of Erdős, Hamburger, Pippert, and Weakley by showing that for some positive constant c and every n, each 2-detour subgraph of the n-dimensional hypercube Q _n has at least clog₂ n · 2 ⁿ edges. József Balogh: Research supported in part by NSF grants DMS-0302804, DMS-0603769 and DMS-0600303, UIUC Campus Reseach Board #06139 and #07048, and OTKA 049398. Alexandr Kostochka: Research supported in part by NSF grants DMS-0400498 and DMS-0650784, and grant 06-01-00694 of the Russian Foundation for Basic Research.     

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.     

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     

Covering a square by small perimeter rectangles

We show that if the unit square is covered byn rectangles, then at least one must have perimeter at least 4(2m+1)/(n+m(m+1)), wherem is the largest integer whose square is at mostn. This result is exact forn of the formm(m+1) (orm ²).Research supported in part by NSF under contract DMS-8406100.Supported in part by the Weizmann Fellowship for Scientific Research.Supported in part by the University of Minnesota under the Ordway Endowment.     

Classification of manifolds with weakly 1/4-pinched curvatures

We show that a compact Riemannian manifold with weakly pointwise 1/4-pinched sectional curvatures is either locally symmetric or diffeomorphic to a space form. More generally, we classify all compact, locally irreducible Riemannian manifolds M with the property that M × R ² has non-negative isotropic curvature. The first author was partially supported by a Sloan Foundation Fellowship and by NSF grant DMS-0605223. The second author was partially supported by NSF grant DMS-0604960.     

On fixed points of permutations

The number of fixed points of a random permutation of {1,2,…,n} has a limiting Poisson distribution. We seek a generalization, looking at other actions of the symmetric group. Restricting attention to primitive actions, a complete classification of the limiting distributions is given. For most examples, they are trivial – almost every permutation has no fixed points. For the usual action of the symmetric group on k-sets of {1,2,…,n}, the limit is a polynomial in independent Poisson variables. This exhausts all cases. We obtain asymptotic estimates in some examples, and give a survey of related results. This paper is dedicated to the life and work of our colleague Manfred Schocker. We thank Peter Cameron for his help. Diaconis was supported by NSF grant DMS-0505673. Fulman received funding from NSA grant H98230-05-1-0031 and NSF grant DMS-0503901. Guralnick was supported by NSF grant DMS-0653873. This research was facilitated by a Chaire d’Excellence grant to the University of Nice Sophia-Antipolis.     

Cauchy-riemann operator and decomposition ofL 2 space on ℝ + n+1

We decompose L_α²(ℝ₊ ⁿ⁺¹) into direct sum of closed subspaces which are isomorphic to the monogenic Bergman space. Application on commutators is also discussed. Research supported in part by the NSF Grant DMS-9622890     

Curvature and uniformization

We approach the problem of uniformization of general Riemann surfaces through consideration of the curvature equation, and in particular the problem of constructing Poincaré metrics (i.e., complete metrics of constant negative curvature) by solving the equation Δu-e ^2u=K_o(z) on general open surfaces. A few other topics are discussed, including boundary behavior of the conformal factore ^2u giving the Poincaré metric when the Riemann surface has smoothly bounded compact closure, and also a curvature equation proof of Koebe's disk theorem. Research supported in part by NSF Grant DMS-9971975 and also at MSRI by NSF grant DMS-9701755. Research supported in part by NSF Grant DMS-9877077     

An approximate Dirac-type theorem for k-uniform hypergraphs

A k-uniform hypergraph is hamiltonian if for some cyclic ordering of its vertex set, every k consecutive vertices form an edge. In 1952 Dirac proved that if the minimum degree in an n-vertex graph is at least n/2 then the graph is hamiltonian. We prove an approximate version of an analogous result for uniform hypergraphs: For every K ≥ 3 and γ > 0, and for all n large enough, a sufficient condition for an n-vertex k-uniform hypergraph to be hamiltonian is that each (k − 1)-element set of vertices is contained in at least (1/2 + γ)n edges. Research supported by NSF grant DMS-0300529. Research supported by KBN grant 2P03A 015 23 and N201036 32/2546. Part of research performed at Emory University, Atlanta. Research supported by NSF grant DMS-0100784.     

The monodromy group of a function on a general curve

LetC _g be a general curve of genusg≥4. Guralnick and others proved that the monodromy group of a coverC _g →ℙ¹ of degreen is eitherS _n orA _n . We show thatA _n occurs forn≥2g+1. The corresponding result forS _n is classical. Partially supported by NSA grant MDA-9049810020. Partially supported by NSF grant DMS-0200225.     

A local version of the two-circles theorem

A necessary and sufficient condition is given so that in a domain Ω there are no functions whose average over all balls contained in Ω of radiir ₁,r ₂ vanish except the zero function. Partially supported by NSF grant DMS-8401356 and by NSF grant OJR 85-OV-108 through the Systems Research Center of the University of Maryland.     

Focal points and support functions in affine differential geometry

The notions of focal point and support function are considered for a nondegenerate hypersurfaceM ⁿ in affine spaceR ⁿ⁺¹ equipped with an equiaffine transversal field. IfM ⁿ is locally strictly convex, these two concepts are related via an Index theorem concerning the critical points of the support functions onM ⁿ . This is used to obtain characterizations of spheres and ellipsoids in terms of the critical point behavior of certain classes of affine support functions.Research supported by NSF Grant No. DMS-9101961.     

On integer points in polyhedra

We give an upper bound on the number of vertices ofP _I , the integer hull of a polyhedronP, in terms of the dimensionn of the space, the numberm of inequalities required to describeP, and the size of these inequalities. For fixedn the bound isO(m ^{n n–} ). We also describe an algorithm which determines the number of integer points in a polyhedron to within a multiplicative factor of 1+ in time polynomial inm, and 1/ when the dimensionn is fixed.Supported by Sonderfschungsbereich 303 (DFG) and NSF grant ECS-8611841.Partially supported by NSF grant DMS-8905645.Supported by NSF grants ECS-8418392 and CCR-8805199.mcd%vax.oxford.ac.uk