An improved bound for the stepping-up lemma

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

Benny Sudakov, Jacob Fox, David Conlon

Publication date: 29 November 2013

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

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.

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)

Cites Work

• Title not available (Why is that?)
• Some remarks on the theory of graphs
• The Ramsey number R(3, t) has order of magnitude t²/log t
• A note on Ramsey numbers
• Title not available (Why is that?)
• Title not available (Why is that?)
• Asymptotic lower bounds for Ramsey functions
• A new upper bound for diagonal Ramsey numbers
• The early evolution of the \(H\)-free process
• Hypergraph Ramsey numbers
• Partition relations for cardinal numbers
• Title not available (Why is that?)

Cited In (16)

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

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)