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.
Revised:
Accepted:
Published online:
Keywords: Trivalent graph, cubic graph, expander graph, Whitehead move, conductance
Mots-clés : Graphes trivalents, graphes expanseurs, transformation de Whitehead, conductance
Laura Grave de Peralta 1; Alexander Kolpakov 2
@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}, }
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/
[1] The asymptotic number of unlabelled regular graphs, J. Lond. Math. Soc., Volume 26 (1982) no. 2, pp. 201-206 | DOI | MR | Zbl
[2] Spectral graph theory, Reg. Conf. Ser. Math., 92, American Mathematical Society, 1997, xii+207 pages | MR | Zbl
[3] Introduction to algorithms, MIT Press, 2009, xx+1292 pages | MR | Zbl
[4] Moduli of graphs and automorphisms of free groups, Invent. Math., Volume 84 (1986) no. 1, pp. 91-119 | DOI | MR | Zbl
[5] Simultaneous flips on triangulated surfaces, Mich. Math. J., Volume 67 (2018) no. 3, pp. 451-464 | DOI | MR | Zbl
[6] 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] Pants decompositions of surfaces (1999) (https://arxiv.org/abs/math/9906084)
[8] 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] Random graphs, John Wiley & Sons, 2011
[10] An introduction to symbolic dynamics and coding, Cambridge Mathematical Library, Cambridge University Press, 2021, xix+550 pages | DOI | MR | Zbl
[11] K. Rafi’s webpage, 2024 (http://www.math.toronto.edu/~rafi/gofg.html)
[12] 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] Automorphisms of free groups and outer space, Geom. Dedicata, Volume 94 (2002), pp. 1-31 | DOI | Zbl
[14] Die Aktion der Abbildungsklassengruppe auf dem Hosenkomplex, Ph. D. Thesis, Karlsruher Institut für Technologie (2009)
[15] 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)
Cited by Sources:
Comments - Policy