Oriented Ramsey numbers of graded digraphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866929333541535744 |
|---|---|
| author | Morawski, Patryk Wigderson, Yuval |
| author_facet | Morawski, Patryk Wigderson, Yuval |
| contents | 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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_01069 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Oriented Ramsey numbers of graded digraphs Morawski, Patryk Wigderson, Yuval Combinatorics 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$. |
| title | Oriented Ramsey numbers of graded digraphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2405.01069 |