The Erdös-Faber-Lovász conjecture – the uniform regular case

We consider the Erdös-Faber-Lovász (EFL) conjecture for hypergraphs that are both regular and uniform. This paper proves that for fixed degree, there can be only finitely many counterexamples to EFL on this class of hypergraphs. The theorem is a direct application of a graph theoretic result of Alon, Krivelevich and Sudakov from 1999. This result combined with the known results for dense hypergraphs shows that any counterexample to EFL must be somewhere in the range between sparse and dense values.

Full Text (PDF format)

Published 1 January 2010