Cliques with many colors in triple systems

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

Authors: Dhruv Mubayi, Andrew Suk 

Publication date: 3 February 2022

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

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.

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

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

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)

Cited In (3)

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

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)