Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2509.08531 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918138777436160 |
|---|---|
| author | Csóka, Endre Fekete, Panna Tímea Nagy, Zoltán Lóránt Szemerédi, Levente |
| author_facet | Csóka, Endre Fekete, Panna Tímea Nagy, Zoltán Lóránt Szemerédi, Levente |
| contents | In this paper, we present a new factor of IID process based on the local algorithm introduced by Díaz, Serna, and Wormald (2007). This new approach allows us to improve the previously known upper bounds on the minimum and maximum bisection width and the maximum cut of random d-regular graphs for d > 4 by introducing a new recoloring phase after the termination of the original algorithm. As an application, we show that random 5-regular graphs asymptotically almost surely admit an internal partition, i.e., a partition of the vertex set into two nonempty classes so that every vertex has at least half of its neighbors in its own class. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_08531 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Bisection width, max-cut and internal partitions of 5-regular graphs Csóka, Endre Fekete, Panna Tímea Nagy, Zoltán Lóránt Szemerédi, Levente Combinatorics In this paper, we present a new factor of IID process based on the local algorithm introduced by Díaz, Serna, and Wormald (2007). This new approach allows us to improve the previously known upper bounds on the minimum and maximum bisection width and the maximum cut of random d-regular graphs for d > 4 by introducing a new recoloring phase after the termination of the original algorithm. As an application, we show that random 5-regular graphs asymptotically almost surely admit an internal partition, i.e., a partition of the vertex set into two nonempty classes so that every vertex has at least half of its neighbors in its own class. |
| title | Bisection width, max-cut and internal partitions of 5-regular graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2509.08531 |