Expansion properties of Whitehead moves on cubic graphs
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....
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Académie des sciences
2024-11-01
|
| Series: | Comptes Rendus. Mathématique |
| Subjects: | |
| Online Access: | https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.5802/crmath.691/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1825206163916980224 |
|---|---|
| author | Grave de Peralta, Laura Kolpakov, Alexander |
| author_facet | Grave de Peralta, Laura Kolpakov, Alexander |
| author_sort | Grave de Peralta, Laura |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-83da496232c24b3391bf4f325cc453cd |
| institution | Kabale University |
| issn | 1778-3569 |
| language | English |
| publishDate | 2024-11-01 |
| publisher | Académie des sciences |
| record_format | Article |
| series | Comptes Rendus. Mathématique |
| spelling | doaj-art-83da496232c24b3391bf4f325cc453cd2025-02-07T11:26:37ZengAcadémie des sciencesComptes Rendus. Mathématique1778-35692024-11-01362G121825183610.5802/crmath.69110.5802/crmath.691Expansion properties of Whitehead moves on cubic graphsGrave de Peralta, Laura0Kolpakov, Alexander1Impact Initiatives, 9 Chemin de Balexert, 1219 Geneva, SwitzerlandUniversity of Austin, 522 Congress Ave., Austin, TX 78701, United StatesThe 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.https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.5802/crmath.691/Trivalent graphcubic graphexpander graphWhitehead moveconductance |
| spellingShingle | Grave de Peralta, Laura Kolpakov, Alexander Expansion properties of Whitehead moves on cubic graphs Comptes Rendus. Mathématique Trivalent graph cubic graph expander graph Whitehead move conductance |
| title | Expansion properties of Whitehead moves on cubic graphs |
| title_full | Expansion properties of Whitehead moves on cubic graphs |
| title_fullStr | Expansion properties of Whitehead moves on cubic graphs |
| title_full_unstemmed | Expansion properties of Whitehead moves on cubic graphs |
| title_short | Expansion properties of Whitehead moves on cubic graphs |
| title_sort | expansion properties of whitehead moves on cubic graphs |
| topic | Trivalent graph cubic graph expander graph Whitehead move conductance |
| url | https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.5802/crmath.691/ |
| work_keys_str_mv | AT gravedeperaltalaura expansionpropertiesofwhiteheadmovesoncubicgraphs AT kolpakovalexander expansionpropertiesofwhiteheadmovesoncubicgraphs |