Counterexamples to an Extremal Conjecture for Random Cycle-Factors
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918487669080064 |
|---|---|
| author | Gajjala, Rishikesh |
| author_facet | Gajjala, Rishikesh |
| contents | Christoph, Draganić, Girão, Hurley, Michel, and Müyesser conjectured that, when $d\mid n$, the expected number of cycles in a uniformly random cycle-factor of a directed $d$-regular graph on $n$ vertices is uniquely maximised by the disjoint union of $n/d$ copies of the complete looped digraph $K_d^\circ$, with value $(n/d)H_d$ [FOCS 2025]. We disprove this conjecture in the strongest possible range. For every $d\ge 3$ and every multiple $n=kd$ with $k\ge 2$, we construct a directed $d$-regular graph on $n$ vertices whose uniformly random cycle-factor has expected cycle count strictly larger than $kH_d$. We also show that the conjectured extremal picture is correct in degree $d=2$, giving a sharp dichotomy between degree two and all higher degrees. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_26101 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Counterexamples to an Extremal Conjecture for Random Cycle-Factors Gajjala, Rishikesh Combinatorics Discrete Mathematics Probability Christoph, Draganić, Girão, Hurley, Michel, and Müyesser conjectured that, when $d\mid n$, the expected number of cycles in a uniformly random cycle-factor of a directed $d$-regular graph on $n$ vertices is uniquely maximised by the disjoint union of $n/d$ copies of the complete looped digraph $K_d^\circ$, with value $(n/d)H_d$ [FOCS 2025]. We disprove this conjecture in the strongest possible range. For every $d\ge 3$ and every multiple $n=kd$ with $k\ge 2$, we construct a directed $d$-regular graph on $n$ vertices whose uniformly random cycle-factor has expected cycle count strictly larger than $kH_d$. We also show that the conjectured extremal picture is correct in degree $d=2$, giving a sharp dichotomy between degree two and all higher degrees. |
| title | Counterexamples to an Extremal Conjecture for Random Cycle-Factors |
| topic | Combinatorics Discrete Mathematics Probability |
| url | https://arxiv.org/abs/2604.26101 |