A note on the Erdős-Hajnal hypergraph Ramsey problem

DOI10.1090/PROC/15839MaRDI QIDQ5086917zbMATH OpenOpenAlexFDO

Authors Dhruv Mubayi, Andrew Suk, Emily Zhu

Publication date 8 July 2022

Published in Proceedings of the American Mathematical Society (Search for Journal in Brave)

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

zbMATH Keywords

5-uniform hypergraph

Mathematics Subject Classification ID

Hypergraphs (05C65) Ramsey theory (05D10)

Abstract: We show that there is an absolute constant $c>0$ such that the following holds. For every $n>1$, there is a 5-uniform hypergraph on at least $2^{2^{c{n}^{1/4}}}$ vertices with independence number at most $n$, where every set of 6 vertices induces at most 3 edges. The double exponential growth rate for the number of vertices is sharp. By applying a stepping-up lemma established by the first two authors, analogous sharp results are proved for $k$-uniform hypergraphs. This answers the penultimate open case of a conjecture in Ramsey theory posed by ErdH{o}s and Hajnal in 1972.

Recommendations

• The Erdős-Hajnal hypergraph Ramsey problem
• scientific article; zbMATH DE number 4213982
• A conjecture of Erdős on graph Ramsey numbers
• A note on Ramsey numbers for Berge-\(G\) hypergraphs
• A survey of hypergraph Ramsey problems
• Ramsey problems for Berge hypergraphs
• Note on a Ramsey-Turán type problem
• On a Ramsey-type problem of Erdős and Pach
• On a Ramsey-type problem of Erdős and Pach
• The Erdős-Gyárfás problem on generalized Ramsey numbers

Cites work

• A new upper bound for diagonal Ramsey numbers
• A note on Ramsey numbers
• Asymptotic lower bounds for Ramsey functions
• Combinatorial Theorems on Classifications of Subsets of a Given Set
• scientific article; zbMATH DE number 3198027 (Why is no real title available?)
• Hypergraph Ramsey numbers
• New lower bounds for hypergraph Ramsey numbers
• Open problems of Paul Erd�s in graph theory
• Partition relations for cardinal numbers
• Some remarks on the theory of graphs
• The early evolution of the \(H\)-free process
• The Erdős-Hajnal hypergraph Ramsey problem
• The triangle-free process

Cited in

(12)

• The Erdős-Hajnal hypergraph Ramsey problem
• Two Erdős-Hajnal-type theorems in hypergraphs
• Erdős-Hajnal conjecture for graphs with bounded VC-dimension
• An improved bound for the stepping-up lemma
• Polynomial to exponential transition in Ramsey theory
• Independent sets in hypergraphs with a forbidden link
• A conjecture of Erdős on graph Ramsey numbers
• The Erdős-Szekeres problem and an induced Ramsey question
• A note on highly connected and well-connected Ramsey theory
• Large cliques or cocliques in hypergraphs with forbidden order-size pairs
• Erdős-Hajnal problems for posets
• Erdős-Hajnal-type theorems in hypergraphs

This page was built for publication: A note on the Erdős-Hajnal hypergraph Ramsey problem

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