Back to Search
Start Over
On Ramsey numbers of hedgehogs
- Source :
- Combinator. Probab. Comp. 29 (2020) 101-112
- Publication Year :
- 2019
-
Abstract
- The hedgehog $H_t$ is a 3-uniform hypergraph on vertices $1,\dots,t+\binom{t}{2}$ such that, for any pair $(i,j)$ with $1\le i<j\le t$, 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\ln t)$.<br />Comment: 13 pages
Details
- Database :
- arXiv
- Journal :
- Combinator. Probab. Comp. 29 (2020) 101-112
- Publication Type :
- Report
- Accession number :
- edsarx.1902.10221
- Document Type :
- Working Paper
- Full Text :
- https://doi.org/10.1017/S0963548319000312