no. G12
Article de recherche - Combinatoire, Géométrie et Topologie
Expansion properties of Whitehead moves on cubic graphs
[Sur les propriétés d’expansion de transformations de Whitehead sur les graphes trivalents]
Grave de Peralta, Laura1 ; Kolpakov, Alexander2 
1Impact Initiatives, 9 Chemin de Balexert, 1219 Geneva, Switzerland
2University of Austin, 522 Congress Ave., Austin, TX 78701, United States
Comptes Rendus. Mathématique, Tome 362 (2024) no. G12, pp. 1825-1836

The present note concerns the “graph of graphs” that has cubic graphs as vertices connected by edges represented by the so-called Whitehead moves. Here, we prove that the outer-conductance of the graph of graphs tends to zero as the number of vertices tends to infinity. This answers a question of K. Rafi in the negative.

Cette note porte sur le « graphe des graphes », dont les sommets sont des graphes trivalents reliés par des arêtes correspondant aux transformations de Whitehead. Nous montrons ici que la conductance externe de ce graphe tend vers zéro lorsque le nombre de sommets tend vers l’infini. Cela donne une réponse négative à la question posée par K. Rafi.

Reçu le :
Révisé le :
Accepté le :
Publié le :
DOI : 10.5802/crmath.691
Classification : 05C48, 05C75, 05C90
Keywords: Trivalent graph, cubic graph, expander graph, Whitehead move, conductance
Mots-clés : Graphes trivalents, graphes expanseurs, transformation de Whitehead, conductance

Grave de Peralta, Laura  1   ; Kolpakov, Alexander  2

1 Impact Initiatives, 9 Chemin de Balexert, 1219 Geneva, Switzerland
2 University of Austin, 522 Congress Ave., Austin, TX 78701, United States
Licence : CC-BY 4.0
Droits d'auteur : Les auteurs conservent leurs droits
@article{CRMATH_2024__362_G12_1825_0,
     author = {Grave de Peralta, Laura and Kolpakov, Alexander},
     title = {Expansion properties of {Whitehead} moves on cubic graphs},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {1825--1836},
     year = {2024},
     publisher = {Acad\'emie des sciences, Paris},
     volume = {362},
     number = {G12},
     doi = {10.5802/crmath.691},
     zbl = {07949990},
     language = {en},
     url = {https://www.numdam.org/articles/10.5802/crmath.691/}
}
TY  - JOUR
AU  - Grave de Peralta, Laura
AU  - Kolpakov, Alexander
TI  - Expansion properties of Whitehead moves on cubic graphs
JO  - Comptes Rendus. Mathématique
PY  - 2024
SP  - 1825
EP  - 1836
VL  - 362
IS  - G12
PB  - Académie des sciences, Paris
UR  - https://www.numdam.org/articles/10.5802/crmath.691/
DO  - 10.5802/crmath.691
LA  - en
ID  - CRMATH_2024__362_G12_1825_0
ER  - 
%0 Journal Article
%A Grave de Peralta, Laura
%A Kolpakov, Alexander
%T Expansion properties of Whitehead moves on cubic graphs
%J Comptes Rendus. Mathématique
%D 2024
%P 1825-1836
%V 362
%N G12
%I Académie des sciences, Paris
%U https://www.numdam.org/articles/10.5802/crmath.691/
%R 10.5802/crmath.691
%G en
%F CRMATH_2024__362_G12_1825_0
Grave de Peralta, Laura; Kolpakov, Alexander. Expansion properties of Whitehead moves on cubic graphs. Comptes Rendus. Mathématique, Tome 362 (2024) no. G12, pp. 1825-1836. doi: 10.5802/crmath.691

[1] Bollobás, Béla The asymptotic number of unlabelled regular graphs, J. Lond. Math. Soc., Volume 26 (1982) no. 2, pp. 201-206 | DOI | MR | Zbl

[2] Chung, Fan R. K. Spectral graph theory, Reg. Conf. Ser. Math., 92, American Mathematical Society, 1997, xii+207 pages | MR | Zbl

[3] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford Introduction to algorithms, MIT Press, 2009, xx+1292 pages | MR | Zbl

[4] Culler, Marc; Vogtmann, Karen Moduli of graphs and automorphisms of free groups, Invent. Math., Volume 84 (1986) no. 1, pp. 91-119 | DOI | MR | Zbl

[5] Disarlo, Valentina; Parlier, Hugo Simultaneous flips on triangulated surfaces, Mich. Math. J., Volume 67 (2018) no. 3, pp. 451-464 | DOI | MR | Zbl

[6] Disarlo, Valentina; Parlier, Hugo The geometry of flip graphs and mapping class groups, Trans. Am. Math. Soc., Volume 372 (2019) no. 6, pp. 3809-3844 | DOI | MR | Zbl

[7] Hatcher, Allen Pants decompositions of surfaces (1999) (https://arxiv.org/abs/math/9906084)

[8] Hatcher, Allen; Thurston, William A presentation for the mapping class group of a closed orientable surface, Topology, Volume 19 (1980) no. 3, pp. 221-237 | DOI | MR | Zbl

[9] Janson, Svante; Luczak, Tomasz; Rucinski, Andrzej Random graphs, John Wiley & Sons, 2011 | MR

[10] Lind, Douglas; Marcus, Brian An introduction to symbolic dynamics and coding, Cambridge Mathematical Library, Cambridge University Press, 2021, xix+550 pages | DOI | MR | Zbl

[11] Rafi, Kasra K. Rafi’s webpage, 2024 (http://www.math.toronto.edu/~rafi/gofg.html)

[12] Rafi, Kasra; Tao, Jing The diameter of the thick part of moduli space and simultaneous Whitehead moves, Duke Math. J., Volume 162 (2013) no. 10, pp. 1833-1876 | DOI | MR | Zbl

[13] Vogtmann, Karen Automorphisms of free groups and outer space, Geom. Dedicata, Volume 94 (2002), pp. 1-31 | MR | DOI | Zbl

[14] Wolf, Ute Die Aktion der Abbildungsklassengruppe auf dem Hosenkomplex, Ph. D. Thesis, Karlsruher Institut für Technologie (2009)

[15] Wolf, Ute The action of the mapping class group on the pants complex (2009) (https://www.math.kit.edu/iag3/~wolf/media/wolf-the-action-of-the-mapping-class-group-on-the-pants-complex.pdf)

Cité par Sources :