Cliques with many colors in triple systems

DOI10.4310/JOC.2021.V12.N4.A2zbMATH Open1482.05332MaRDI QIDQ2073641FDOQ2073641

Authors Dhruv Mubayi, Andrew Suk

Publication date 3 February 2022

Published in Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2005.03078

zbMATH Keywords

Ramsey theoryhypergraphs

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Coloring of graphs and hypergraphs (05C15) Generalized Ramsey theory (05C55) Hypergraphs (05C65) Ramsey theory (05D10)

Abstract: ErdH{o}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"odl asked whether there is some integer $qge3$ 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 $qgeq9$, where $N$ is exponential in $n^{2+cq}$ and $c>0$ is an absolute constant.

Recommendations

• Coloring triple systems with local conditions
• Large almost monochromatic subsets in hypergraphs
• The Erdős-Hajnal conjecture for three colors and triangles
• Edge-coloring cliques with many colors on subcliques
• Edge-coloring cliques with three colors on all 4-cliques

Cited in

(3)

• Coloring triple systems with local conditions
• Large almost monochromatic subsets in hypergraphs
• Tower Gaps in Multicolour Ramsey Numbers

This page was built for publication: Cliques with many colors in triple systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2073641)