2016/07/22 by Axenovich, Maria, Karrer, Annette
#05C15 #Combinatorics (math.CO) #FOS: Mathematics #G.2.2
paper · doi:10.48550/arxiv.1607.06600
A classical result of Erdős and Hajnal claims that for any integers k, r, g ≥ 2 there is an r-uniform hypergraph of girth at least g with chromatic number at least k. This implies that there are sparse hypergraphs such that in any coloring of their vertices with at most k-1 colors there is a monochromatic hyperedge. We show that for any integers r, g≥ 2 there is an r-uniform hypergraph of girth at least g such that in any coloring of its vertices there is either a monochromatic or a rainbow (totally multicolored) edge. We give a probabilistic and a deterministic proof of this result.