Partition critical hypergraphs
by
Attila Sali
Alfréd Rényi Institute of Mathematics, Budapest, Hungary
Coauthors: Zoltán Füredi Department of Mathematics University of Illinois at Urbana-Champaign Urbana, Illinois, USA

A k-uniform hypergraph (X, E) is 3-color critical if it is not 2-colorable, but for all E ∈ E the hypergraph (X, E\{E}) is 2-colorable. Lovász proved in 1976, that

|E| ≤ ( n k-1 )

for a 3-color critical k-uniform hypergraph with |X|=n. Here we prove an ordered version that is a sharpening of Lovász' result. Let

E ⊆ ( [n] k )

be a k-uniform set system on an underlying set X of n elements. Let us fix an ordering E₁, E₂, ...E_t of E and a prescribed partition A_i∪B_i=E_i (A_i∩B_i=∅) for each member of E. Assume that for all i=1, 2, ..., t there exists a partition C_i∪D_i=X (C_i∩D_i=∅), such that E_i∩C_i=A_i and E_i∩D_i=B_i, but E_j∩C_i ≠ A_j and E_j∩C_i ≠ B_j for all j < i. (That is, the ith partition cuts the ith set as it is prescribed, but does not cut any earlier set properly.) Then

t ≤ ( n-1 k-1 )+( n-1 k-2 )+...+( n-1 0 )=( n k-1 )+O(nk-3).

This is sharp for k=2, 3. Furthermore, if A_i=E_i and B_i=∅ for all i, then

t ≤ ( n k-1 )

. We also construct a partition critical k-uniform hypergraph of size

( n k-1 ).

Date received: April 12, 2009