On Ramsey numbers of hedgehogs

DOI10.1017/S0963548319000312zbMATH Open1436.05071arXiv1902.10221OpenAlexW2980698421WikidataQ127029397 ScholiaQ127029397MaRDI QIDQ5222572FDOQ5222572

Authors: Jacob Fox, Ray Li 

Publication date: 6 April 2020

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

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)$.

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

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

zbMATH Keywords

3-uniform hypergraphRamsey number

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Combinatorial Theorems on Classifications of Subsets of a Given Set
• Ramsey numbers of degenerate graphs
• Title not available (Why is that?)
• Two remarks on the Burr-Erdős conjecture
• Turán Numbers of Bipartite Graphs and Related Ramsey-Type Questions
• On Ramsey Numbers of Sparse Graphs
• Hypergraph Ramsey numbers
• Partition relations for cardinal numbers
• Recent developments in graph Ramsey theory
• On Ramsey numbers of uniform hypergraphs with given maximum degree
• Hedgehogs are not colour blind

Cited In (2)

• Ramsey numbers of Berge-hypergraphs and related structures
• HEDGEHOGS IN LEHMER’S PROBLEM

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)