{"id":"arxiv/2604.26101","url":"https://arxiv.org/abs/2604.26101","tags":["math.CO","cs.DM","math.PR"],"score":0,"title":"Counterexamples to an Extremal Conjecture for Random Cycle-Factors","domain":"math.CO","source":"arxiv","authors":["Rishikesh Gajjala"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-04-28","reactions":{}}