Partition Critical Hypergraphs

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 1 , E 2 , … , 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 ( n k − 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 give aconstruction of size ( n k − 1 ) .