Tower Gaps in Multicolour Ramsey Numbers

DOI10.1017/FMS.2023.89MaRDI QIDQ6047011zbMATH OpenOpenAlexFDO

Authors Quentin Dubroff, António Girão, Corrine Yap

Publication date 6 October 2023

Published in Forum of Mathematics, Sigma (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

\(q\)-colour Ramsey numbersErdős-Hajnal stepping-up lemma

Mathematics Subject Classification ID

Generalized Ramsey theory (05C55) Hypergraphs (05C65) Structural characterization of families of graphs (05C75) Ramsey theory (05D10)

Abstract: Generalizing the classical Ramsey numbers, $r_k(t;q,p)$ is the smallest integer $n$ such that every $q$-colouring of the $k$-sets on $n$ vertices contains a set of $t$ vertices spanning fewer than $p$ colours. We prove the first tower-type lower bounds on these numbers via two new stepping-up constructions, both variants of the original stepping-up lemma due to ErdH{o}s and Hajnal. We use these to resolve a problem of Conlon, Fox, and R"{o}dl. More precisely, we construct a family of hypergraphs with arbitrarily large tower height separation between their $2$-colour and $q$-colour Ramsey numbers.

Recommendations

• Off-diagonal hypergraph Ramsey numbers
• Shift graphs and lower bounds on Ramsey numbers \(r_ k(l;r)\)
• The Erdős-Hajnal hypergraph Ramsey problem
• Sharp bounds for some multicolour Ramsey numbers
• New lower bounds for hypergraph Ramsey numbers

Cites work

• Cliques with many colors in triple systems
• Combinatorial Theorems on Classifications of Subsets of a Given Set
• Erdős and Rényi conjecture
• Hedgehogs are not colour blind
• scientific article; zbMATH DE number 46958 (Why is no real title available?)
• scientific article; zbMATH DE number 3494449 (Why is no real title available?)
• Hypergraph Ramsey numbers
• On a Ramsey type theorem
• On Ramsey Numbers of Sparse Graphs
• On Ramsey numbers of uniform hypergraphs with given maximum degree
• Partition relations for cardinal numbers
• Ramsey numbers of degenerate graphs
• Set-coloring of edges and multigraph Ramsey numbers
• The probabilistic method
• Two remarks on the Burr-Erdős conjecture

Cited in

(2)

• An improved bound for the stepping-up lemma
• Ramsey numbers for 1-degenerate 3-graphs

This page was built for publication: Tower Gaps in Multicolour Ramsey Numbers

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