An improved bound for the stepping-up lemma

DOI10.1016/J.DAM.2010.10.013zbMATH Open1277.05115OpenAlexW2115582932WikidataQ125056592 ScholiaQ125056592MaRDI QIDQ385142FDOQ385142

Authors David Conlon, Jacob Fox, Benny Sudakov

Publication date 29 November 2013

Published in Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

hypergraph Ramsey numbersstepping-up lemma

Mathematics Subject Classification ID

Generalized Ramsey theory (05C55) Hypergraphs (05C65)

Abstract: The partition relation N o (n)_{ell}^k means that whenever the k-tuples of an N-element set are ell-colored, there is a monochromatic set of size n, where a set is called monochromatic if all its k-tuples have the same color. The logical negation of N o (n)_{ell}^k is written as N

ot o (n)_{ell}^k. An ingenious construction of ErdH{o}s and Hajnal known as the stepping-up lemma gives a negative partition relation for higher uniformity from one of lower uniformity, effectively gaining an exponential in each application. Namely, if ell geq 2, k geq 3, and N ot o (n)_{ell}^k, then 2^N ot o (2n+k-4)_{ell}^{k+1}. In this note we give an improved construction for k geq 4. We introduce a general class of colorings which extends the framework of ErdH{o}s and Hajnal and can be used to establish negative partition relations. We show that if ell geq 2, k geq 4 and N ot o (n)_{ell}^k, then 2^N ot o (n+3)_{ell}^{k+1}. If also k is odd or ell geq 3, then we get the better bound 2^N

ot o (n+2)_{ell}^{k+1}. This improved bound gives a coloring of the k-tuples whose largest monochromatic set is a factor Omega(2^{k}) smaller than given by the original version of the stepping-up lemma. We give several applications of our result to lower bounds on hypergraph Ramsey numbers. In particular, for fixed ell geq 4 we determine up to an absolute constant factor (which is independent of k) the size of the largest guaranteed monochromatic set in an ell-coloring of the k-tuples of an N-set.

Recommendations

• Hypergraph Ramsey numbers
• Tower Gaps in Multicolour Ramsey Numbers
• New lower bounds for hypergraph Ramsey numbers
• A note on the Erdős-Hajnal hypergraph Ramsey problem
• Constructions in Ramsey theory

Cites work

• scientific article; zbMATH DE number 3711961 (Why is no real title available?)
• scientific article; zbMATH DE number 1131467 (Why is no real title available?)
• scientific article; zbMATH DE number 3361883 (Why is no real title available?)
• scientific article; zbMATH DE number 3019031 (Why is no real title available?)
• A new upper bound for diagonal Ramsey numbers
• A note on Ramsey numbers
• Asymptotic lower bounds for Ramsey functions
• Hypergraph Ramsey numbers
• Partition relations for cardinal numbers
• Some remarks on the theory of graphs
• The Ramsey number R(3, t) has order of magnitude t²/log t
• The early evolution of the \(H\)-free process

Cited in

(16)

• On multicolor Ramsey numbers and subset coloring of hypergraphs
• Lower bounds on the clique-chromatic numbers of some distance graphs
• Ramsey properties of algebraic graphs and hypergraphs
• On high-dimensional acyclic tournaments
• Higher-order Erdős-Szekeres theorems
• Hypergraph Ramsey numbers: tight cycles versus cliques
• A note on induced Ramsey numbers
• Erdős-Hajnal-type theorems in hypergraphs
• Ramsey numbers with prescribed rate of growth
• Ramsey-type results for semi-algebraic relations
• Hypergraph Ramsey numbers of cliques versus stars
• Some remarks on vertex Folkman numbers for hypergraphs
• The Erdős-Hajnal hypergraph Ramsey problem
• Multicolor Ramsey numbers for triple systems
• Boolean lattices: Ramsey properties and embeddings
• Off-diagonal hypergraph Ramsey numbers

This page was built for publication: An improved bound for the stepping-up lemma

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