Proof of a Conjecture of Frankl and Füredi

AbstractWe give a simple linear algebraic proof of the following conjecture of Frankl and Füredi [7, 9, 13]. (Frankl–Füredi Conjecture) If F is a hypergraph onX={1, 2, 3, …, n} such that1⩽|E∩F|⩽k∀E, F∈F,E≠F,then |\cal F|\le\sum^k_{i=0} {n-1 \choose i}. We generalise a method of Palisse and our proof-technique can be viewed as a variant of the technique used by Tverberg to prove a result of Graham and Pollak [10, 11, 14]. Our proof-technique is easily described. First, we derive an identity satisfied by a hypergraph F using its intersection properties. From this identity, we obtain a set of homogeneous linear equations. We then show that this defines the zero subspace ofR|F|. Finally, the desired bound on |F| is obtained from the bound on the number of linearly independent equations. This proof-technique can also be used to prove a more general theorem (Theorem 2). We conclude by indicating how this technique can be generalised to uniform hypergraphs by proving the uniform Ray–Chaudhuri–Wilson theorem