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 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 be a k-uniform set system on an underlying set X of n elements. Let us fix an ordering E1,E2,…,Et of E and a prescribed partition Ai∪Bi=Ei (Ai∩Bi=∅) for each member of E. Assume that for all i=1,2,…,t there exists a partition Ci∪Di=X(Ci∩Di=∅), such that Ei∩Ci=Ai and Ei∩Di=Bi, but Ej∩Ci≠Aj and Ej∩Ci≠Bj for all j