Loading...
Please wait, while we are loading the content...
Similar Documents
On Ramsey numbers of hedgehogs
| Content Provider | Scilit |
|---|---|
| Author | Fox, Jacob Li, Ray |
| Copyright Year | 2019 |
| Description | The hedgehog $H_{t}$ is a 3-uniform hypergraph on vertices $1, \ldots ,t + \left({\matrix{t \cr 2}}\right)$ such that, for any pair (i, j) with 1 ≤ i < j ≤ t, there exists a unique vertex k > t such that {i, j, k} is an edge. Conlon, Fox and Rödl proved that the two-colour Ramsey number of the hedgehog grows polynomially in the number of its vertices, while the four-colour Ramsey number grows exponentially in the square root of the number of vertices. They asked whether the two-colour 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). |
| Related Links | http://arxiv.org/pdf/1902.10221 https://www.cambridge.org/core/services/aop-cambridge-core/content/view/B0DC14A250A162A462CA9CC65560F84F/S0963548319000312a.pdf/div-class-title-on-ramsey-numbers-of-hedgehogs-div.pdf |
| Ending Page | 112 |
| Page Count | 12 |
| Starting Page | 101 |
| ISSN | 09635483 |
| e-ISSN | 14692163 |
| DOI | 10.1017/s0963548319000312 |
| Journal | Combinatorics, Probability and Computing |
| Issue Number | 1 |
| Volume Number | 29 |
| Language | English |
| Publisher | Cambridge University Press (CUP) |
| Publisher Date | 2020-01-01 |
| Access Restriction | Open |
| Subject Keyword | Combinatorics, Probability and Computing Primary 05c55 Secondary 05c65 |
| Content Type | Text |
| Resource Type | Article |
| Subject | Applied Mathematics Statistics and Probability Theoretical Computer Science Computational Theory and Mathematics |
