Cliques with many colors in triple systems

Erdős and Hajnal constructed a $4$-coloring of the triples of an $N$-element set such that every $n$-element subset contains $2$ triples with distinct colors, and $N$ is double exponential in $n$. Conlon, Fox and Rödl asked whether there is some integer $q \geq 3$ and a $q$-coloring of the triples of an $N$-element set such that every $n$-element subset has $3$ triples with distinct colors, and $N$ is double exponential in $n$. We make the first nontrivial progress on this problem by providing a $q$-coloring with this property for all $q \geq 9$, where $N$ is exponential in $n^{2+cq}$ and $c \gt 0$ is an absolute constant.

Keywords

Ramsey theory, hypergraphs

2010 Mathematics Subject Classification

Primary 05D10. Secondary 05C55.

Full Text (PDF format)

The first-named author’s research was partially supported by NSF grant DMS-1763317.

The second-named author’s research was partially supported by an NSF CAREER award, by NSF award DMS-1952786, and by an Alfred Sloan Fellowship.

Received 23 May 2020

Accepted 2 November 2020

Published 31 January 2022