arXiv Open Access 2024

Oriented Ramsey numbers of graded digraphs

Patryk Morawski Yuval Wigderson

Lihat Sumber

Abstrak

We show that any graded digraph $D$ on $n$ vertices with maximum degree $Δ$ has an oriented Ramsey number of at most $C^Δn$ for some absolute constant $C > 1$, improving upon a recent result of Fox, He, and Wigderson. In particular, this implies that oriented grids in any fixed dimension have linear oriented Ramsey numbers, and gives a polynomial bound on the oriented Ramsey number of the hypercube. We also show that this result is essentially best possible, in that there exist graded digraphs on $n$ vertices with maximum degree $Δ$ such that their oriented Ramsey number is at least $c^Δn$ for some absolute constant $c > 1$.

Topik & Kata Kunci

math.CO

Penulis (2)

Patryk Morawski

Yuval Wigderson

Format Sitasi

APA MLA BibTeX

Morawski, P., Wigderson, Y. (2024). Oriented Ramsey numbers of graded digraphs. https://arxiv.org/abs/2405.01069

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2024
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓