Counterexamples to an Extremal Conjecture for Random Cycle-Factors
Rishikesh Gajjala · 2026
Read Counterexamples to an Extremal Conjecture for Random Cycle-Factors by Rishikesh Gajjala (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-26101.txt.
Introduction
Gajjala disproves a conjecture about random cycle-factors of directed regular graphs. The conjecture predicted that a disjoint union of complete looped digraphs uniquely maximizes the expected number of cycles. For every degree from three upward, and every multiple of that degree with at least two blocks, the paper constructs a directed regular graph. Its random cycle-factor averages strictly more cycles than the conjectured maximum. The paper also proves the conjectured picture correct in degree two. That gives a sharp split between degree two and all higher degrees.
Catalog record
| CREATOR | Rishikesh Gajjala |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 24549 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.26101
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Counterexamples to an Extremal Conjecture for Random Cycle-Factors Rishikesh Gajjala Abstract Christoph, Draganić, Girão, Hurley, Michel, and Müyesser conjectured that, when d | n d\mid n , the expected number of cycles in a uniformly random cycle-factor of a directed d d -regular graph on n n vertices is uniquely maximised by the disjoint union of n / d n/d copies of the complete looped digraph K d ∘ K_{d}^{\circ} , with value ( n / d ) H d (n/d)H_{d} [FOCS 2025]. We disprove this conjecture in the strongest possible range. For every d ≥ 3 d\geq 3 and every multiple n = k d n=kd with k ≥ 2 k\geq 2 , we construct a directed d d -regular graph on n n vertices whose uniformly random cycle-factor has expected cycle count strictly larger than k H d kH_{d} . We also show that the conjectured extremal picture is correct in degree d = 2 d=2 , giving a sharp dichotomy between degree two and all higher degrees. 1 Introduction A uniformly random permutation is one of the basic objects of discrete probability. It is a classical result that the expected number of cycles in a uniformly random permutation of m points is the harmonic number H_{m}:=\sum_{j=1}^{m}\frac{1}{j} [ 2 ] . Equivalently, if K_{m}^{\circ} denotes the complete looped digraph on m vertices, then a uniformly random cycle-factor of K_{m}^{\circ} is just a uniformly random permutation of m points, and hence has expected cycle count H_{m} . A natural way to generalise random permutations is to restrict the allowed images of each point. Throughout this paper, directed graphs are finite, may have loops and directed cycles of length two, but have no parallel edges. A loop contributes one to both the in-degree and the out-degree. A directed graph is d -regular if every vertex has in-degree and out-degree exactly d . A cycle-factor of a directed graph G is a permutation \sigma of V(G) such that v\to\sigma(v) is an edge of G for every v\in V(G) . We write \mathcal{C}(G) for the set of cycle-factors of G , and c(\sigma) for the number of directed cycles of the permutation \sigma . This problem is also naturally connected to permanents and perfect matchings. Given a directed graph G , form its bipartite double-cover B_{G} with left and right copies of V(G) , and with an edge u_{L}v_{R} whenever u\to v is an edge of G . Then cycle-factors of G are in bijection with perfect matchings of B_{G} . Thus |\mathcal{C}(G)| is the permanent of the bipartite adjacency matrix of B_{G} . Classical permanent inequalities give strong evidence that block constructions should play an extremal role here: the Brégman–Minc theorem gives sharp upper bounds for such permanents, while Schrijver’s theorem gives sharp lower bounds for the number of perfect matchings in regular bipartite graphs [ 1 , 9 ] . The entropy argument of Christoph, Draganić, Girão, Hurley, Michel, and Müyesser [ 4 ] is closely related to this. Christoph et al. [ 4 ] proved that a uniformly random cycle-factor of any directed d -regular graph on n vertices has O((n\log d)/d) cycles in expectation, generalising the classical fact that a random permutation has logarithmically many cycles. Their proof uses entropy to exploit the fact that the upper and lower bounds for permanent for regular bipartite graphs are very close. They conjectured the following sharp extremal form of their theorem. Conjecture 1 ( [ 4 , Extended version, Conjecture 4.1] ) . If d\mid n , then 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 K_{d}^{\circ} . The value in Conjecture 1 would be (n/d)H_{d} , since the random cycle-factor splits independently over the n/d components. This makes the conjecture very natural: the proposed extremal graph is the direct analogue of the complete graph for random permutations, and it is also the clique-type construction suggested by the permanent and path-partition viewpoints. The case n=d is trivial, since a directed d -regular graph on d vertices must be K_{d}^{\circ} . Thus the first possible range for counterexamples is n\geq 2d . Cycle-factors are also closely related to path partitions: after removing one edge from each cycle, one obtains a partition of the vertices into directed paths. This is one reason that cycle-factors appear in work on path partitions and short tours in regular graphs. Magnant and Martin [ 8 ] conjectured that every n -vertex d -regular undirected graph has a path partition with at most n/(d+1) paths; this would be tight for the disjoint union of n/(d+1) copies of K_{d+1} . Their conjecture is known for d\leq 6 [ 8 , 5 ] and for d=\Omega(n) [ 7 ] . Related work of Vishnoi [ 10 ] and Feige, Ravi, and Singh [ 6 ] studies short tours in regular graphs, where cycle-factors and path partitions provide natural starting points. In this light, Conjecture 1 proposed a random cycle-factor analogue of the same clique-type extremal phenomenon. Our main result shows that this is not the case: although the disjoint union of complete looped digraphs is the natural candidate, it does not maximise the expected number of cycles as soon as d\geq 3 . Theorem 2 . For every integer d\geq 3 and every integer k\geq 2 , there is a directed d -regular graph G_{k,d} on kd vertices such that, for a uniformly random \sigma\in\mathcal{C}(G_{k,d}) , \mathbb{E}c(\sigma)>kH_{d}. Consequently, Conjecture 1 fails for every d\geq 3 and every multiple n=kd\geq 2d . We also show that this failure starts at the first possible degree: in degree two, the conjectured extremal picture is correct. Observation 3 . If n is even, then the expected number of cycles in a uniformly random cycle-factor of a directed 2 -regular graph on n vertices is uniquely maximised, with value \frac{n}{2}H_{2}=\frac{3n}{4}, by the disjoint union of n/2 copies of K_{2}^{\circ} . Thus the conjecture exhibits a sharp dichotomy: it is true in the only nontrivial degree below three, but false for every d\geq 3 and every admissible order n\geq 2d . Section 2 proves Observation 3 . Section 3 presents the smallest counterexample, the looped bidirected 6 -cycle. Section 4 gives a general counterexample to all d\geq 3 and proves Theorem 2 . 2 The case d=2 For a directed graph G , let \lambda(G) denote the number of loops of G . For a permutation \sigma , let \fix(\sigma):=\bigl|\{v\in V(G):\sigma(v)=v\}\bigr| be the number of fixed points of \sigma . Theorem 4 . Let G be a directed 2 -regular graph on n vertices, and let \sigma be uniformly distributed in \mathcal{C}(G) . Then the following hold. (1) Every directed edge of G belongs to \sigma with probability 1/2 . (2) \mathbb{E}\fix(\sigma)=\lambda(G)/2\leq n/2 . (3) \mathbb{E}c(\sigma)\leq\frac{n}{2}+\frac{\lambda(G)}{4}\leq\frac{3n}{4}. (4) Equality in the bound \mathbb{E}c(\sigma)\leq 3n/4 holds if and only if n is even and G\cong\bigsqcup_{i=1}^{n/2}K_{2}^{\circ}. Proof. Let B be the bipartite double-cover of G . Its two vertex classes are left and right copies V_{L},V_{R} of V(G) , and for every directed edge u\to v of G we put an edge u_{L}v_{R}