Maximizing Alternating Paths via Entropy
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_ | 1866916723429474304 |
|---|---|
| author | Chen, Hao Clemen, Felix Christian Noel, Jonathan A. |
| author_facet | Chen, Hao Clemen, Felix Christian Noel, Jonathan A. |
| contents | We prove that if $G$ is an $n$-vertex graph whose edges are coloured with red and blue, then the number of colour-alternating walks of length $2k+1$ with $k+1$ red edges and $k$ blue edges is at most $k^k(k+1)^{k+1}(2k+1)^{-2k-1}n^{2k+2}$. This solves a problem that was recently posed by Basit, Granet, Horsley, Kündgen and Staden. Our proof involves an application of the entropy method. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_03903 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Maximizing Alternating Paths via Entropy Chen, Hao Clemen, Felix Christian Noel, Jonathan A. Combinatorics We prove that if $G$ is an $n$-vertex graph whose edges are coloured with red and blue, then the number of colour-alternating walks of length $2k+1$ with $k+1$ red edges and $k$ blue edges is at most $k^k(k+1)^{k+1}(2k+1)^{-2k-1}n^{2k+2}$. This solves a problem that was recently posed by Basit, Granet, Horsley, Kündgen and Staden. Our proof involves an application of the entropy method. |
| title | Maximizing Alternating Paths via Entropy |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2505.03903 |