Economical Covers with Geometric Applications

A cover of a hypergraph is a collection of edges whose unioncontains all vertices. Let H = (V, E) be a k-uniform, D-regularhypergraph on n vertices, in which no two vertices are containedin more than o(D/e^2k log D) edges as D tends to infinity. Ourresults include the fact that if k = o(log D), then there isa cover of (1 + o(1))n/k edges, extending the known result thatthis holds for fixed k. On the other hand, if k 4 log D thenthere are k-uniform, D-regular hypergraphs on n vertices inwhich no two vertices are contained in more than one edge, andyet the smallest cover has at least (nk) log (k log D)) edges.Several extensions and variants are also obtained, as well asthe following geometric application. The minimum number of linesrequired to separate n random points in the unit square is,almost surely, (n^2/3 / (log n)^1/3). 2000 Mathematical SubjectClassification: 05C65, 05D15, 60D05.     

Topological cliques of random graphs

Given a graph G, denote by tcl(G) the largest integer r for which G contains a TK^r, a toplogical complete r-graph. We show that for every ? > 0 almost every graph G of order n satisfies

$\text{(2?ε)n}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{?}\text{tlc}\text{(G)?(2+ε)}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$

     

Convex Bodies, Graphs and Partial Orders

A convex corner is a compact convex down-set of full dimensionin Rⁿ. Convex corners arise in graph theory, for instance asstable set polytopes of graphs. They are also natural objects of study in geometry, as they correspond to 1-unconditionalnorms in an obvious way. In this paper, we study a parameterof convex corners, which we call the content, that is relatedto the volume. This parameter has appeared implicitly before:both in geometry, chiefly in a paper of Meyer (Israel J. Math.} 55 (1986) 317–327) effectively using content to givea proof of Saint-Raymond's Inequality on the volume product of a convex corner, and in combinatorics, especially in apaper of Sidorenko (Order} 8 (1991) 331–340) relatingcontent to the number of linear extensions of a partial order.One of our main aims is to expose connections between workin these two areas. We prove many new results, giving in particular various generalizations of Saint-Raymond's Inequality. Contentalso behaves well under the operation of pointwise product oftwo convex corners; our results enable us to give counter-examplesto two conjectures of Bollobás and Leader Oper. TheoryAdv. Appl. 77 (1995) 13–24) on pointwise products. 1991Mathematics Subject Classification: 52C07, 51M25, 52B11, 05C60,06A07.     

Essentially infinite colourings of hypergraphs

We consider edge colourings of the complete r-uniform hypergraphK_n^(r)on n vertices. How many colours may such a colouring haveif we restrict the number of colours locally? The local restrictionis formulated as follows: for a fixed hypergraph H and an integerk we call a colouring (H, k)-local if every copy of H in thecomplete hypergraph K_n^(r) receives at most k different colours. We investigate the threshold for k that guarantees that every(H, k)-local colouring of K_n^(r) must have a globally boundednumber of colours as n , and we establish this threshold exactly.The following phenomenon is also observed: for many H (at leastin the case of graphs), if k is a little over this threshold,the unbounded (H, k)-local colourings exhibit their colourfulnessin a ‘sparse way’; more precisely, a bounded numberof colours are dominant while all other colours are rare. Hencewe study the threshold k₀ for k that guarantees that every (H,k)-local colouring n of K_n^(r) with k k₀ must have a globallybounded number of colours after the deletion of up to n^r edgesfor any fixed > 0 (the bound on the number of colours isallowed to depend on H and only); we think of such colouringsn as ‘essentially finite’. As it turns out, everyessentially infinite colouring is closely related to a non-monochromaticcanonical Ramsey colouring of Erdös and Rado. This secondthreshold is determined up to an additive error of 1 for everyhypergraph H. Our results extend earlier work for graphs byClapsadle and Schelp [‘Local edge colorings that are global’,J. Graph Theory 18 (1994) 389–399] and by the first twoauthors and Schelp [‘Essentially infinite colourings ofgraphs’, J. London Math. Soc. (2) 61 (2000) 658–670].We also consider a related question for colourings of the integersand arithmetic progressions.

---

2000 Mathematics Subject Classification 05D10 (primary), 05C35(secondary). The first author was partially supported by NSF grants CCR 0225610and DMS 0505550. The second author was partially supported byFAPESP and CNPq through a Temático–ProNEx project(Proc. FAPESP 2003/09925–5) and by CNPq (Proc. 306334/2004–6and 479882/2004–5). The third author was partially supportedby NSF grant DMS 0300529. The fourth author was partly supportedby the DFG within the European graduate program ‘Combinatorics,Geometry, and Computation’ (No. GRK 588/2) and by DFGgrant SCHA 1263/1–1. This work was supported in part bya CAPES/DAAD collaboration grant.     

A Short Proof of the Harris-Kesten Theorem

We give a short proof of the fundamental result that the criticalprobability for bond percolation in the planar square latticeZ² is equal to 1/2. The lower bound was proved by Harris, whoshowed in 1960 that percolation does not occur at p = 1/2. Theother, more difficult, bound was proved by Kesten, who showedin 1980 that percolation does occur for any p > 1/2. 2000Mathematics Subject Classification 60K35, 82B43.     

The number of 1-factors in 2k-connected graphs

Mader [Arch. Math. 23 (1972), 219–224] determined the minimal number of 1-factors in a 2k-connected graph having at least one 1-factor. We give a simple proof of this result and slightly extend it.     

Projections of Bodies and Hereditary Properties of Hypergraphs

We prove that for every n-dimensional body K, there is a rectangularparallelepiped B of the same volume as K, such that the projectionof B onto any coordinate subspace is at most as large as thatof the corresponding projection of K. We apply this theorem to projections of finite set systems andto hereditary properties. In particular, we show that everyhereditary property of uniform hypergraphs has a limiting density.     

A Polynomial Invariant of Graphs On Orientable Surfaces

We consider cyclic graphs, that is, graphs with cyclic ordersat the vertices, corresponding to 2-cell embeddings of graphsinto orientable surfaces, or combinatorial maps. We constructa three variable polynomial invariant of these objects, thecyclic graph polynomial, which has many of the useful propertiesof the Tutte polynomial. Although the cyclic graph polynomialgeneralizes the Tutte polynomial, its definition is very different,and it depends on the embedding in an essential way. 2000 MathematicalSubject Classification: 05C10.