New lower bounds for hypergraph Ramsey numbers

DOI10.1112/BLMS.12133MaRDI QIDQ4637550zbMATH OpenOpenAlexFDO

Authors Dhruv Mubayi, Andrew Suk

Publication date 24 April 2018

Published in Bulletin of the London Mathematical Society (Search for Journal in Brave)

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

zbMATH Keywords

\(k\)-uniform hypergraphdouble exponentialErdős-Hajnal stepping-up lemmahypergraph Ramsey numberslower boundsMarkov inequalityoff-diagonal hypergraph Ramsey numbers

Mathematics Subject Classification ID

Hypergraphs (05C65) Ramsey theory (05D10) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: The Ramsey number $r_k(s,n)$ is the minimum $N$ such that for every red-blue coloring of the $k$-tuples of $1,ldots,N$, there are $s$ integers such that every $k$-tuple among them is red, or $n$ integers such that every $k$-tuple among them is blue. We prove the following new lower bounds for 4-uniform hypergraph Ramsey numbers: ${\displaystyle }$r_4(5,n) > 2^{n^{clog n}} qquad hbox{ and } qquad r_4(6,n) > 2^{2^{cn^{1/5}}},${\displaystyle }$ where $c$ is an absolute positive constant. This substantially improves the previous best bounds of $2^{n^{cloglogn}}$ and $2^{n^{clogn}}$, respectively. Using previously known upper bounds, our result implies that the growth rate of $r_4(6,n)$ is double exponential in a power of $n$. As a consequence, we obtain similar bounds for the $k$-uniform Ramsey numbers $r_k(k+1,n)$ and $r_k(k+2,n)$ where the exponent is replaced by an appropriate tower function. This almost solves the question of determining the tower growth rate for {emph {all}} classical off-diagonal hypergraph Ramsey numbers, a question first posed by ErdH os and Hajnal in 1972. The only problem that remains is to prove that $r_4(5,n)$ is double exponential in a power of $n$.

Recommendations

• Off-diagonal hypergraph Ramsey numbers
• Hypergraph Ramsey numbers
• Constructions in Ramsey theory
• New lower bounds for Ramsey numbers of graphs and hypergraphs
• Lower bounds for hypergraph Ramsey numbers

Cited in

(23)

• Shift graphs and lower bounds on Ramsey numbers \(r_ k(l;r)\)
• The Erdős-Hajnal hypergraph Ramsey problem
• New bounds on the Ramsey number r ( I_m , L_n )
• A survey of hypergraph Ramsey problems
• Lower bounds for small Ramsey numbers on hypergraphs
• Off-diagonal hypergraph Ramsey numbers
• Multicolor Ramsey numbers for triple systems
• Asymptotic lower bounds of Ramsey numbers for 4-uniform hypergraphs
• A lower bound on the hypergraph Ramsey number \(R(4,5;3)\)
• Hypergraph Ramsey numbers
• An improved bound for the stepping-up lemma
• Constructions in Ramsey theory
• scientific article; zbMATH DE number 6130240 (Why is no real title available?)
• A note on the Erdős-Hajnal hypergraph Ramsey problem
• scientific article; zbMATH DE number 2218940 (Why is no real title available?)
• Tower Gaps in Multicolour Ramsey Numbers
• Ramsey numbers of semi-algebraic and semi-linear hypergraphs
• Hypergraph Ramsey numbers of cliques versus stars
• Large cliques or cocliques in hypergraphs with forbidden order-size pairs
• On off-diagonal hypergraph Ramsey numbers
• New lower bounds for Ramsey numbers of graphs and hypergraphs
• Semi-algebraic and semi-linear Ramsey numbers (extended abstract)
• A note on the multicolour version of the Erdős-Hajnal conjecture

This page was built for publication: New lower bounds for hypergraph Ramsey numbers

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