Ramsey numbers for 1-degenerate 3-graphs

2025/07/31 by Allen, Peter, Boyadzhiyska, Simona, Pavez-Signé, Matías
#05D10 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2507.23623

Abstract

We construct a 3-uniform 1-degenerate hypergraph on n vertices whose 2-colour Ramsey number is Ω(n^3/2/log n). This shows that all remaining open cases of the hypergraph Burr-Erdős conjecture are false. Our graph is a variant of the celebrated hedgehog graph. We additionally show near-sharp upper bounds, proving that all 3-uniform generalised hedgehogs have 2-colour Ramsey number O(n^3/2).

Citations

• Hedgehogs are not colour blind
• Ramsey numbers of degenerate graphs

Related

• Hedgehogs are not colour blind
• A note on lower bounds for hypergraph Ramsey numbers
• Two remarks on the Burr-Erdos conjecture
• Three Proofs of the Hypergraph Ramsey Theorem (An exposition)
• Ramsey numbers of degenerate graphs