On directed and undirected diameters of vertex-transitive graphs
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916637018423296 |
|---|---|
| author | Skresanov, Saveliy V. |
| author_facet | Skresanov, Saveliy V. |
| contents | A directed diameter of a directed graph is the maximum possible distance between a pair of vertices, where paths must respect edge orientations, while undirected diameter is the diameter of the undirected graph obtained by symmetrizing the edges. In 2006 Babai proved that for a connected directed Cayley graph on $n$ vertices the directed diameter is bounded above by a polynomial in undirected diameter and $\log n$. Moreover, Babai conjectured that a similar bound holds for vertex-transitive graphs. We prove this conjecture of Babai, in fact, it follows from a more general bound for connected relations of homogeneous coherent configurations. The main novelty of the proof is a generalization of Ruzsa's triangle inequality from additive combinatorics to the setting of graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_12943 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On directed and undirected diameters of vertex-transitive graphs Skresanov, Saveliy V. Combinatorics 05C12 (Primary) 05C20, 20B25 (Secondary) A directed diameter of a directed graph is the maximum possible distance between a pair of vertices, where paths must respect edge orientations, while undirected diameter is the diameter of the undirected graph obtained by symmetrizing the edges. In 2006 Babai proved that for a connected directed Cayley graph on $n$ vertices the directed diameter is bounded above by a polynomial in undirected diameter and $\log n$. Moreover, Babai conjectured that a similar bound holds for vertex-transitive graphs. We prove this conjecture of Babai, in fact, it follows from a more general bound for connected relations of homogeneous coherent configurations. The main novelty of the proof is a generalization of Ruzsa's triangle inequality from additive combinatorics to the setting of graphs. |
| title | On directed and undirected diameters of vertex-transitive graphs |
| topic | Combinatorics 05C12 (Primary) 05C20, 20B25 (Secondary) |
| url | https://arxiv.org/abs/2312.12943 |