Expansion properties of Whitehead moves on cubic graphs

Laura Grave de Peralta; Alexander Kolpakov

doi:10.5802/crmath.691

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]

Laura Grave de Peralta ¹ ; Alexander Kolpakov ²

¹ Impact Initiatives, 9 Chemin de Balexert, 1219 Geneva, Switzerland
² University of Austin, 522 Congress Ave., Austin, TX 78701, United States

Comptes Rendus. Mathématique, Volume 362 (2024), pp. 1825-1836.

Résumé
Abstract

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.

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.

Reçu le : 2024-03-10
Révisé le : 2024-07-18
Accepté le : 2024-09-18
Publié le : 2024-11-25

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

Affiliations des auteurs :

Laura Grave de Peralta ¹ ; Alexander Kolpakov ²

¹ Impact Initiatives, 9 Chemin de Balexert, 1219 Geneva, Switzerland
² 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 = {Laura Grave de Peralta and Alexander Kolpakov},
     title = {Expansion properties of {Whitehead} moves on cubic graphs},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {1825--1836},
     publisher = {Acad\'emie des sciences, Paris},
     volume = {362},
     year = {2024},
     doi = {10.5802/crmath.691},
     language = {en},
}

TY  - JOUR
AU  - Laura Grave de Peralta
AU  - Alexander Kolpakov
TI  - Expansion properties of Whitehead moves on cubic graphs
JO  - Comptes Rendus. Mathématique
PY  - 2024
SP  - 1825
EP  - 1836
VL  - 362
PB  - Académie des sciences, Paris
DO  - 10.5802/crmath.691
LA  - en
ID  - CRMATH_2024__362_G12_1825_0
ER  -

%0 Journal Article
%A Laura Grave de Peralta
%A Alexander Kolpakov
%T Expansion properties of Whitehead moves on cubic graphs
%J Comptes Rendus. Mathématique
%D 2024
%P 1825-1836
%V 362
%I Académie des sciences, Paris
%R 10.5802/crmath.691
%G en
%F CRMATH_2024__362_G12_1825_0

Laura Grave de Peralta; Alexander Kolpakov. Expansion properties of Whitehead moves on cubic graphs. Comptes Rendus. Mathématique, Volume 362 (2024), pp. 1825-1836. doi : 10.5802/crmath.691. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.5802/crmath.691/

Bibliographie
Cité par

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

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

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

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

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

[6] Valentina Disarlo; Hugo Parlier 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] Allen Hatcher Pants decompositions of surfaces (1999) (https://arxiv.org/abs/math/9906084)

[8] Allen Hatcher; William Thurston 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] Svante Janson; Tomasz Luczak; Andrzej Rucinski Random graphs, John Wiley & Sons, 2011

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

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

[12] Kasra Rafi; Jing Tao 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] Karen Vogtmann Automorphisms of free groups and outer space, Geom. Dedicata, Volume 94 (2002), pp. 1-31 | DOI | Zbl

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

[15] Ute Wolf 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 :

Commentaires - Politique