加载中…
A classical result of Erd\H{o}s and Hajnal claims that for any integers $k, r, g \geq 2rg$ with chromatic number at least . This implies that there are sparse hypergraphs such that in any coloring of their vertices with at most colors there is a monochromatic hyperedge. We show that for any integers there is an -uniform hypergraph of girth at least 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.

生成讲解博客的中文版本

生成AI智能校验的中文版本