Contents Online

# Journal of Combinatorics

## Volume 12 (2021)

### Number 4

### Cliques with many colors in triple systems

Pages: 563 – 569

DOI: https://dx.doi.org/10.4310/JOC.2021.v12.n4.a2

#### Authors

#### Abstract

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.

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