Color-avoiding directed paths in tournaments
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914268217081856 |
|---|---|
| author | Fox, Jacob Sudakov, Benny Wigderson, Yuval |
| author_facet | Fox, Jacob Sudakov, Benny Wigderson, Yuval |
| contents | We study the following Ramsey-theoretic question: given a $q$-coloring of the edges of a tournament, how long of a directed path can we guarantee whose edges avoid one of the colors? Questions of this type have applications in many areas, such as vector sequences, convex geometry, and extremal hypergraph theory, and have been extensively studied over the past 50 years.
We prove that if $\varepsilon>0$ is fixed and $q$ is sufficiently large, then every $q$-edge-colored $N$-vertex tournament contains a color-avoiding directed path of length $N^{1-\varepsilon}$. This answers a question of Gowers and Long, strengthens several of their results, and extends earlier work of Loh. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_10438 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Color-avoiding directed paths in tournaments Fox, Jacob Sudakov, Benny Wigderson, Yuval Combinatorics We study the following Ramsey-theoretic question: given a $q$-coloring of the edges of a tournament, how long of a directed path can we guarantee whose edges avoid one of the colors? Questions of this type have applications in many areas, such as vector sequences, convex geometry, and extremal hypergraph theory, and have been extensively studied over the past 50 years. We prove that if $\varepsilon>0$ is fixed and $q$ is sufficiently large, then every $q$-edge-colored $N$-vertex tournament contains a color-avoiding directed path of length $N^{1-\varepsilon}$. This answers a question of Gowers and Long, strengthens several of their results, and extends earlier work of Loh. |
| title | Color-avoiding directed paths in tournaments |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2512.10438 |