On Ramsey numbers of hedgehogs

DOI10.1017/S0963548319000312MaRDI QIDQ5222572zbMATH OpenOpenAlexWikidataFDO

Authors Jacob Fox, Ray Li

Publication date 6 April 2020

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

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

zbMATH Keywords

3-uniform hypergraphRamsey number

Mathematics Subject Classification ID

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

Abstract: The hedgehog $H_t$ is a 3-uniform hypergraph on vertices $$ such that, for any pair $(i,j)$ with $1lei<jlet$, there exists a unique vertex $k>t$ such that $i,j,k$ is an edge. Conlon, Fox, and R"odl proved that the two-color Ramsey number of the hedgehog grows polynomially in the number of its vertices, while the four-color Ramsey number grows exponentially in the number of its vertices. They asked whether the two-color Ramsey number of the hedgehog $H_t$ is nearly linear in the number of its vertices. We answer this question affirmatively, proving that $r(H_t)=O(t^{2}lnt)$.

Recommendations

• Hedgehogs are not colour blind
• Hypergraph Ramsey numbers: triangles versus cliques
• Off-diagonal hypergraph Ramsey numbers
• Ramsey numbers of Berge-hypergraphs and related structures
• Hypergraph Ramsey numbers

Cites work

• scientific article; zbMATH DE number 46958 (Why is no real title available?)
• scientific article; zbMATH DE number 3494449 (Why is no real title available?)
• Combinatorial Theorems on Classifications of Subsets of a Given Set
• Hedgehogs are not colour blind
• Hypergraph Ramsey numbers
• 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
• Recent developments in graph Ramsey theory
• Turán Numbers of Bipartite Graphs and Related Ramsey-Type Questions
• Two remarks on the Burr-Erdős conjecture

Cited in

(3)

• Ramsey numbers of Berge-hypergraphs and related structures
• HEDGEHOGS IN LEHMER’S PROBLEM
• Hedgehogs are not colour blind

This page was built for publication: On Ramsey numbers of hedgehogs

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