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

Dhruv Mubayi (Department of Mathematics, Statistics, and Computer Science, University of Illinois, Chicago, Il., U.S.A.)

Andrew Suk (Department of Mathematics, University of California, San Diego, Calif., U.S.A.)

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 full text of this article is unavailable through your IP address: 18.191.205.110

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