Every 8-uniform 8-regular hypergraph is 2-colorable

As is well known, Lovász Local Lemma implies that everyd-uniformd-regular hypergraph is 2-colorable, providedd 9. We present a different proof of a slightly stronger result; everyd-uniformd-regular hypergraph is 2-colorable, providedd 8.Research supported in part by Allon Fellowship and by a grant from the United States Israel Binational Science Foundation.     

Strengthening the Lovász bound for graph coloring

The Lovász -number is a way to approximate the independence number of a graph, but also its chromatic number. We express the Lovász bound as the continuous relaxation of a discrete Lovász -number which we derive from Karger et al.s formulation, and which is equal to the chromatic number. We also give another relaxation à la Schrijver-McEliece, which is better than the Lovász -number.     

Minimal imperfect graphs: A simple approach

We provide a very short proof of the following theorem of Lovász, and of its consequences:A graph is perfect if and only if in every induced subgraph the number of vertices does not exceed the product of the stability and clique numbers of the subgraph.This proof is conceptually new: it does not use the replication operation, or any kind of polyhedral argument; the arguments resemble more the well-known ways of deducing structural properties of minimal imperfect graphs. However, the known proofs of these structural properties use Lovász's result, whereas the present work leads to a proof of Lovász's result itself, and actually to a slight sharpening.The author gratefully acknowledges financial support from Ministère de la Recherche et de la Technologie (the French Ministry of Research and Technology, MRT) which sponsored his three month visit to Laboratory ARTEMIS of Grenoble University which motivated him to do this work.     

The gap between monotone and non-monotone circuit complexity is exponential

A. A. Razborov has shown that there exists a polynomial time computable monotone Boolean function whose monotone circuit complexity is at leastn ^{c losn} . We observe that this lower bound can be improved to exp(cn ^1/6–o(1)). The proof is immediate by combining the Alon—Boppana version of another argument of Razborov with results of Grötschel—Lovász—Schrijver on the Lovász — capacity, of a graph.     

Using equivariant obstruction theory in combinatorial geometry

A significant group of problems coming from the realm of combinatorial geometry can be approached fruitfully through the use of Algebraic Topology. From the first such application to Kneser's problem in 1978 by Lovász [L. Lovász, Knester's conjecture, chromatic number of distance graphs on the sphere, Acta. Sci. Math (Szeged) 45 (1983) 317-323] through the solution of the Lovász conjecture [E. Babson, D. Kozlov, Proof of Lovasz conjecture, Annals of Mathematics (2) (2004), submitted for publication; C. Schultz, A short proof of for all n and a graph colouring theorem by Babson and Kozlov, 2005, arXiv: math.AT/0507346v2], many methods from Algebraic Topology have been developed. Specifically, it appears that the understanding of equivariant theories is of the most importance. The solution of many problems depends on the existence of an elegantly constructed equivariant map. A variety of results from algebraic topology were applied in solving these problems. The methods used ranged from well known theorems like Borsuk-Ulam and Dold theorem to the integer/ideal-valued index theories. Recently equivariant obstruction theory has provided answers where the previous methods failed. For example, in papers [R.T. ?ivaljevi?, Equipartitions of measures in R⁴, arXiv: math.0412483, Trans. Amer. Math. Soc., submitted for publication] and [P. Blagojevi?, A. Dimitrijevi? Blagojevi?, Topology of partition of measures by fans and the second obstruction, arXiv: math.CO/0402400, 2004] obstruction theory was used to prove the existence of different mass partitions. In this paper we extract the essence of the equivariant obstruction theory in order to obtain an effective general position map scheme for analyzing the problem of existence of equivariant maps. The fact that this scheme is useful is demonstrated in this paper with three applications:

(A)

a “half-page” proof of the Lovász conjecture due to Babson and Kozlov [E. Babson, D. Kozlov, Proof of Lovasz conjecture, Annals of Mathematics (2) (2004), submitted for publication] (one of two key ingredients is Schultz' map [C. Schultz, A short proof of for all n and a graph colouring theorem by Babson and Kozlov, 2005, arXiv: math.AT/0507346v2]),

(B)

a generalization of the result of V. Makeev [V.V. Makeev, Equipartitions of continuous mass distributions on the sphere an in the space, Zap. Nauchn. Sem. S.-Petersburg (POMI) 252 (1998) 187-196 (in Russian)] about the sphere S² measure partition by 3-planes (Section 3), and

(C)

the new (a,b,a), class of 3-fan 2-measures partitions (Section 3).

These three results, sorted by complexity, share the spirit of analyzing equivariant maps from spheres to complements of arrangements of subspaces.     

Concentration in a thin Euclidean shell for log-concave measures

A weak version of a conjecture stated by Kannan, Lovász and Simonovits claims that an isotropic log-concave probability μ on Rn should be concentrated in a thin Euclidean shell in the following way:

(1)     

Edge coloring of hypergraphs and a conjecture of ErdÖs,Faber, Lovász

Call a bypergraphsimple if for any pairu, v of distinct vertices, there is at most one edge incident to bothu andv, and there are no edges incident to exactly one vertex. A conjecture of Erds, Faber and Lovász is equivalent to the statement that the edges of any simple hypergraph onn vertices can be colored with at mostn colors. We present a simple proof that the edges of a simple hypergraph onn vertices can be colored with at most [1.5n-2 colors].This research was partially supported by N.S.F. grant No. MCS-8311422.     

Circle grids and bipartite graphs of distances

Fort fixed,n+t pointsA ₁,A ₂,...,A _n andB ₁,B ₂,...,B _t are constructed in the plane withO(n) distinct distancesd(A _i B _j ) As a by-product we show that the graph of thek largest distances can contain a complete subgraphK _{t, n} withn=(k ²), which settles a problem of Erds, Lovász and Vesztergombi.Research partially supported by the Hungarian National Science Fund (OTKA) # 2117.     

Exponentially many perfect matchings in cubic graphs

We show that every cubic bridgeless graph G has at least ²|V(G)|/3656 perfect matchings. This confirms an old conjecture of Lovász and Plummer.     

A fractional version of the Erdős-Faber-Lovász conjecture

LetH be any hypergraph in which any two edges have at most one vertex in common. We prove that one can assign non-negative real weights to the matchings ofH summing to at most |V(H)|, such that for every edge the sum of the weights of the matchings containing it is at least 1. This is a fractional form of the Erds-Faber-Lovász conjecture, which in effect asserts that such weights exist and can be chosen 0,1-valued. We also prove a similar fractional version of a conjecture of Larman, and a common generalization of the two.Supported in part by NSF grant MCS 83-01867, AFOSR Grant 0271 and a Sloan Research Fellowship     

An Isoperimetric Inequality for Hyperplane Sections of a Convex Body

We obtain an inequality which estimates the product of the volumes of the two parts into which a convex body is divided by a hyperplane through its interior in terms of the volume of the hyperplane section. The basic tool in the proof is a Localization lemma for log-concave functions due to Kannan, Lovász and Simonovits.     

A Combinatorial Proof of Kneser’s Conjecture*

Knesers conjecture, first proved by Lovász in 1978, states that the graph with all k-element subsets of {1, 2, . . . , n} as vertices and with edges connecting disjoint sets has chromatic number n–2k+2. We derive this result from Tuckers combinatorial lemma on labeling the vertices of special triangulations of the octahedral ball. By specializing a proof of Tuckers lemma, we obtain self-contained purely combinatorial proof of Knesers conjecture.* Research supported by Charles University grants No. 158/99 and 159/99 and by ETH Zürich.     

On a theorem of lovász on covers inr-partite hypergraphs

A theorem of Lovász asserts that (H)/*(H)r/2 for everyr-partite hypergraphH (where and * denote the covering number and fractional covering number respectively). Here it is shown that the same upper bound is valid for a more general class of hypergraphs: those which admit a partition (V ₁, ...,V _k ) of the vertex set and a partitionp ₁+...+p _k ofr such that |eV _i |p _i r/2 for every edgee and every 1ik. Moreover, strict inequality holds whenr>2, and in this form the bound is tight. The investigation of the ratio /* is extended to some other classes of hypergraphs, defined by conditions of similar flavour. Upper bounds on this ratio are obtained fork-colourable, stronglyk-colourable and (what we call)k-partitionable hypergraphs.Supported by grant HL28438 at MIPG, University of Pennsylvania, and by the fund for the promotion of research at the Technion.This author's research was supported by the fund for the promotion of research at the Technion.     

On a Lovász-type lemma, applied to Brooks’ theorem for list-colouring

In this paper, I present a new structural lemma for k-regular graphs, similar to an earlier lemma by Lovász (1975) [5]. The new lemma is then used to give an algebraic proof of Brooks’ theorem for list-colouring.     

Cones of alternating and cut submodular set functions

We describe facets of the cones of alternating set functions and cut submodular set functions generated by directed and undirected graphs and by uniform even hypergraphs. This answers a question asked by L. Lovász at the Bonn Mathematical Programming Conference in 1982. We show that there is a network flow algorithm for minimizing a hypergraph cut set function.     

Quotients of peck posets

An elementary, self-contained proof of a result of Pouzet and Rosenberg and of Harper is given. This result states that the quotient of certain posets (called unitary Peck) by a finite group of automorphisms retains some nice properties, including the Sperner property. Examples of unitary Peck posets are given, and the techniques developed here are used to prove a result of Lovász on the edge-reconstruction conjecture.Supported in part by a National Science Foundation research grant.     

A propos de conjectures de Serre et Sullivan

Summary We first give a new proof of a conjecture of J.-P. Serre on the homotopy of finite complexes, which was recently proved by C. McGibbon and J. Neisendorfer. The emphasis is on a property of the mod. 2 homology of certain spaces: their quasi-boundedness as right modules over the Steenrod algebra. This property is preserved when one goes from a simply connected space to its loop space and also when one takes a covering of anH-space. Then we show that this notion of quasi-boundedness simplifies H. Miller's proof of D. Sullivan's conjecture on the contractibility of the space of pointed maps from the classifying space of the groupe /2 into a finite complex.     

Lift-and-project ranks and antiblocker duality

We present a very short proof of the beautiful result of Aguilera et al. that the BCC-rank of the clique polytope is invariant under complementation. Such properties do not extend to the N₀ and N procedures of Lovász and Schrijver, or to the N₊ procedure unless .     

On the number of faces of centrally-symmetric simplicial polytopes

I. Bárány and L. Lovász [Acta Math. Acad. Sci. Hung.40, 323–329 (1982)] showed that ad-dimensional centrally-symmetric simplicial polytopeP has at least 2 ^d facets, and conjectured a lower bound for the numberf _i ofi-dimensional faces ofP in terms ofd and the numberf ₀ =2n of vertices. Define integers A. Björner conjectured (unpublished) that (which generalizes the result of Bárány-Lovász sincef _d–1 = h _i ), and more strongly that , which is easily seen to imply the conjecture of Bárány-Lovász. In this paper the conjectures of Björner are proved.Partially supported by NSF grant MCS-8104855. The research was performed when the author was a Sherman Fairchild Distinguished Scholar at Caltech.