arXiv Open Access 2024

On off-diagonal hypergraph Ramsey numbers

David Conlon Jacob Fox Benjamin Gunby Xiaoyu He Dhruv Mubayi +2 lainnya
Lihat Sumber

Abstrak

A fundamental problem in Ramsey theory is to determine the growth rate in terms of $n$ of the Ramsey number $r(H, K_n^{(3)})$ of a fixed $3$-uniform hypergraph $H$ versus the complete $3$-uniform hypergraph with $n$ vertices. We study this problem, proving two main results. First, we show that for a broad class of $H$, including links of odd cycles and tight cycles of length not divisible by three, $r(H, K_n^{(3)}) \ge 2^{Ω_H(n \log n)}$. This significantly generalizes and simplifies an earlier construction of Fox and He which handled the case of links of odd cycles and is sharp both in this case and for all but finitely many tight cycles of length not divisible by three. Second, disproving a folklore conjecture in the area, we show that there exists a linear hypergraph $H$ for which $r(H, K_n^{(3)})$ is superpolynomial in $n$. This provides the first example of a separation between $r(H,K_n^{(3)})$ and $r(H,K_{n,n,n}^{(3)})$, since the latter is known to be polynomial in $n$ when $H$ is linear.

Topik & Kata Kunci

Penulis (7)

D

David Conlon

J

Jacob Fox

B

Benjamin Gunby

X

Xiaoyu He

D

Dhruv Mubayi

A

Andrew Suk

J

Jacques Verstraete

Format Sitasi

Conlon, D., Fox, J., Gunby, B., He, X., Mubayi, D., Suk, A. et al. (2024). On off-diagonal hypergraph Ramsey numbers. https://arxiv.org/abs/2404.02021

Akses Cepat

Lihat di Sumber
Informasi Jurnal
Tahun Terbit
2024
Bahasa
en
Sumber Database
arXiv
Akses
Open Access ✓