Cycle-factors of regular graphs via entropy
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918129469227008 |
|---|---|
| author | Christoph, Micha Draganić, Nemanja Girão, António Hurley, Eoin Michel, Lukas Müyesser, Alp |
| author_facet | Christoph, Micha Draganić, Nemanja Girão, António Hurley, Eoin Michel, Lukas Müyesser, Alp |
| contents | It is a classical result that a random permutation of $n$ elements has, on average, about $\log n$ cycles. We generalise this fact to all directed $d$-regular graphs on $n$ vertices by showing that, on average, a random cycle-factor of such a graph has $\mathcal{O}((n\log d)/d)$ cycles. This is tight up to the constant factor and improves the best previous bound of the form $\mathcal{O}(n/\sqrt{\log d})$ due to Vishnoi. Our results also yield randomised polynomial-time algorithms for finding such a cycle-factor and for finding a tour of length $(1+\mathcal{O}((\log d)/d)) \cdot n$ if the graph is connected. This makes progress on a conjecture of Magnant and Martin and on a problem studied by Vishnoi and by Feige, Ravi, and Singh. Our proof uses the language of entropy to exploit the fact that the upper and lower bounds on the number of perfect matchings in regular bipartite graphs are extremely close. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_19417 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Cycle-factors of regular graphs via entropy Christoph, Micha Draganić, Nemanja Girão, António Hurley, Eoin Michel, Lukas Müyesser, Alp Combinatorics Discrete Mathematics Data Structures and Algorithms Probability It is a classical result that a random permutation of $n$ elements has, on average, about $\log n$ cycles. We generalise this fact to all directed $d$-regular graphs on $n$ vertices by showing that, on average, a random cycle-factor of such a graph has $\mathcal{O}((n\log d)/d)$ cycles. This is tight up to the constant factor and improves the best previous bound of the form $\mathcal{O}(n/\sqrt{\log d})$ due to Vishnoi. Our results also yield randomised polynomial-time algorithms for finding such a cycle-factor and for finding a tour of length $(1+\mathcal{O}((\log d)/d)) \cdot n$ if the graph is connected. This makes progress on a conjecture of Magnant and Martin and on a problem studied by Vishnoi and by Feige, Ravi, and Singh. Our proof uses the language of entropy to exploit the fact that the upper and lower bounds on the number of perfect matchings in regular bipartite graphs are extremely close. |
| title | Cycle-factors of regular graphs via entropy |
| topic | Combinatorics Discrete Mathematics Data Structures and Algorithms Probability |
| url | https://arxiv.org/abs/2507.19417 |