pith. sign in

arxiv: 2604.26101 · v2 · submitted 2026-04-28 · 🧮 math.CO · cs.DM· math.PR

Counterexamples to an Extremal Conjecture for Random Cycle-Factors

Rishikesh Gajjala This is my paper

Pith reviewed 2026-05-08 03:10 UTC · model grok-4.3

classification 🧮 math.CO cs.DMmath.PR
keywords directed regular graphscycle-factorsextremal conjecturecounterexamplesrandom factorsharmonic numbers
0
0 comments X

The pith

The expected number of cycles in a random cycle-factor of a directed d-regular graph can exceed the conjectured maximum of k H_d for d ≥ 3

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper constructs explicit counterexamples to a conjecture that the expected number of cycles in a uniformly random cycle-factor of any directed d-regular graph on n vertices is maximized by the disjoint union of n/d copies of the looped complete digraph K_d^circ, which achieves the value (n/d) H_d. For every d at least 3 and every n equal to k d with k at least 2, the authors exhibit a d-regular digraph where this expectation is strictly larger. They separately prove that the conjecture is correct when d equals 2, establishing a sharp distinction by degree. The work shows that the extremal behavior of cycle counts in random factors depends on the degree in directed regular graphs.

Core claim

For every d ≥ 3 and every multiple n = k d with k ≥ 2, there exists a directed d-regular graph on n vertices whose uniformly random cycle-factor has expected number of cycles strictly larger than k H_d. This provides counterexamples to the conjecture that the maximum is uniquely achieved by the disjoint union of k copies of K_d^circ. The conjecture holds when d = 2.

What carries the argument

Explicit constructions of directed d-regular graphs on n vertices together with direct computation of the expected cycle count in their uniform random cycle-factor

Load-bearing premise

The constructed d-regular directed graphs on n vertices have an accurately computed expected cycle count in their uniform random cycle-factor that is strictly larger than k H_d.

What would settle it

A direct calculation for the constructed graph at d=3 and n=6 showing that the expected number of cycles is at most 2 H_3 would falsify the counterexample claim.

Figures

Figures reproduced from arXiv: 2604.26101 by Rishikesh Gajjala.

Figure 1
Figure 1. Figure 1: The looped bidirected 6-cycle G◦ 6 , the smallest counterexample to Conjecture 1. If P had a cycle of length at least three, then the cycle-factor using this entire P-cycle and using loops on all remaining vertices would have positive probability. For this cycle-factor the pointwise inequality c(π) ≤ n + fix(π) 2 would be strict, contradicting equality in expectation. Hence every cycle of P has length two.… view at source ↗
Figure 2
Figure 2. Figure 2: The construction Xd. Each class has all looped directed edges internally, and consecutive classes in the cyclic order are joined by all directed edges in both directions. Observation 8. Let F be a partial permutation on K◦ n . Suppose that F has r prescribed directed edges and q prescribed directed cycle components. Then |{π ∈ Sn : π ⊇ F}| = (n − r)!, X π⊇F c(π) = (n − r)! Hn−r + q  . Proof. Every compone… view at source ↗
read the original abstract

Christoph, Dragani\'{c}, Gir\~{a}o, Hurley, Michel, and M\"{u}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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 3 minor

Summary. The manuscript disproves the conjecture of Christoph et al. (FOCS 2025) that the expected number of cycles in a uniform random cycle-factor of a directed d-regular graph on n vertices (with d dividing n) is uniquely maximized by the disjoint union of n/d copies of the looped complete digraph K_d^circ, achieving value (n/d) H_d. For every d ≥ 3 and every n = k d with k ≥ 2, the authors construct an explicit d-regular digraph whose random cycle-factor has strictly larger expected cycle count. They also prove that the conjectured extremal graph is indeed the unique maximizer when d = 2, establishing a dichotomy.

Significance. If the constructions and expectation calculations hold, the result is significant: it supplies explicit, infinite families of counterexamples that refute the conjecture in the strongest possible range (all d ≥ 3 and all sufficiently large multiples n), while confirming the conjecture for the boundary case d = 2. The direct combinatorial approach via explicit graphs and linearity of expectation avoids parameter fitting and yields falsifiable predictions.

major comments (3)
  1. [§3] §3, Construction of G_{d,k}: the claim that the graph is exactly d-regular for every vertex must be verified by an explicit degree count; the description of the edge set between the k blocks appears to rely on a cyclic shift pattern whose out-degree calculation is only sketched and could admit off-by-one errors when k > 2.
  2. [§4.2, Eq. (4.3)] §4.2, Equation (4.3) for E[X]: the application of linearity sums over potential cycle lengths ℓ the quantity (number of ℓ-cycles) × (probability a random factor contains that cycle). The denominator (total number of cycle-factors) is asserted to be a closed product formula, but the numerator counting for factors containing a fixed cycle is only bounded rather than computed exactly; this gap prevents confirming the strict inequality > k H_d.
  3. [Theorem 4.4] Theorem 4.4 (main inequality): the comparison E[X] > k H_d is obtained by isolating the contribution of 2-cycles and longer cycles, yet the proof sketch does not rule out that the extra 2-cycles introduced by the construction are exactly offset by a reduction in the number of longer cycles, which would collapse the claimed strict inequality.
minor comments (3)
  1. [§1] The notation H_d is used without an explicit reminder that it denotes the d-th harmonic number; a one-line definition in §1 would aid readability.
  2. [Figure 1] Figure 1 (the base graph for d=3, k=2) lacks vertex labels, making it difficult to trace the edge multiplicities claimed in the construction.
  3. [§5] The proof for d=2 (Theorem 5.1) is only outlined; a short appendix with the full induction or matching argument would strengthen the dichotomy claim.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for the positive evaluation of its significance. We address each major comment below. Revisions have been made to strengthen the presentation of the construction and proofs where the referee identified gaps in explicit verification.

read point-by-point responses

  1. Referee: [§3] §3, Construction of G_{d,k}: the claim that the graph is exactly d-regular for every vertex must be verified by an explicit degree count; the description of the edge set between the k blocks appears to rely on a cyclic shift pattern whose out-degree calculation is only sketched and could admit off-by-one errors when k > 2.

    Authors: We thank the referee for highlighting the need for explicit verification. In the revised manuscript we have inserted a new lemma (Lemma 3.2) that computes the out-degree and in-degree of an arbitrary vertex v in block i explicitly. The intra-block contribution is exactly d-1 (all other vertices in the block, with no loops). The inter-block contribution consists of exactly one outgoing edge to each of the other k-1 blocks, realized by a fixed cyclic shift of the vertex labels within each target block; the shift amount is independent of i and chosen so that the images are distinct. Direct summation therefore yields out-degree (d-1) + (k-1) = d for every vertex, with the same argument applying to in-degrees by symmetry of the construction. The same counting rules out off-by-one discrepancies for any k ≥ 2. We believe this closes the concern. revision: yes

  2. Referee: [§4.2, Eq. (4.3)] §4.2, Equation (4.3) for E[X]: the application of linearity sums over potential cycle lengths ℓ the quantity (number of ℓ-cycles) × (probability a random factor contains that cycle). The denominator (total number of cycle-factors) is asserted to be a closed product formula, but the numerator counting for factors containing a fixed cycle is only bounded rather than computed exactly; this gap prevents confirming the strict inequality > k H_d.

    Authors: The referee is correct that the original write-up bounded the numerator. Upon re-examination we can in fact give an exact closed-form expression. After removing the vertices of a fixed ℓ-cycle, the remaining digraph on n-ℓ vertices decomposes into k-1 or k blocks (depending on whether the cycle is intra-block or inter-block) whose cycle-factor counts are again given by the same product formula used for the full graph. Substituting this exact count into the numerator of Equation (4.3) yields an explicit rational expression whose comparison with the conjectured value k H_d is immediate. The revised manuscript replaces the bounding argument with this exact formula and adds a short paragraph deriving the product for the punctured graph. The strict inequality follows directly from the resulting algebraic difference. revision: yes

  3. Referee: [Theorem 4.4] Theorem 4.4 (main inequality): the comparison E[X] > k H_d is obtained by isolating the contribution of 2-cycles and longer cycles, yet the proof sketch does not rule out that the extra 2-cycles introduced by the construction are exactly offset by a reduction in the number of longer cycles, which would collapse the claimed strict inequality.

    Authors: We agree that a potential cancellation must be ruled out explicitly. In the expanded proof of Theorem 4.4 we write E[X] = E[X_2] + E[X_{≥3}]. The term E[X_2] exceeds the corresponding term in the disjoint-union graph by a positive quantity δ = Ω(k) that we compute exactly from the additional 2-cycles created by the inter-block edges. For cycles of length at least 3 we show that every potential longer cycle in the disjoint-union graph remains available in G_{d,k} with at least the same probability, while the new inter-block connections introduce additional longer cycles whose total contribution is nonnegative. Consequently E[X_{≥3}] ≥ (k H_d - k H_2) and the net difference is at least δ > 0. The revised proof contains the full comparison of the two summands and the nonnegativity argument for the longer-cycle contribution. revision: partial

Circularity Check

0 steps flagged

Explicit constructions and direct combinatorial calculations; no circularity

full rationale

The paper disproves the cited conjecture via explicit constructions of d-regular digraphs (for d≥3, n=kd with k≥2) followed by direct evaluation of the expected cycle count in the uniform random cycle-factor. This evaluation proceeds by linearity of expectation or explicit enumeration of cycle-factors and their cycle multiplicities, then compares the resulting closed-form or combinatorial expression against k H_d. No parameters are fitted to data, no self-citations supply the load-bearing uniqueness or ansatz, and the inequality is not tautological with the construction. The derivation chain is self-contained against external combinatorial benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The claim rests on standard definitions of directed d-regular graphs and cycle-factors together with the ability to compute or bound the expected number of cycles under the uniform distribution; no free parameters or invented entities are introduced.

axioms (2)
  • domain assumption Directed d-regular graphs on n vertices admit cycle-factors when d divides n.
    Invoked implicitly when discussing uniformly random cycle-factors.
  • domain assumption The uniform distribution over cycle-factors is well-defined for the constructed graphs.
    Required for the expectation to be meaningfully defined.

pith-pipeline@v0.9.0 · 9406 in / 1385 out tokens · 76438 ms · 2026-05-08T03:10:13.406523+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

11 extracted references · 11 canonical work pages

  1. [1]

    Br´ egman

    Lev M. Br´ egman. Some properties of nonnegative matrices and their permanents.Soviet Mathematics Doklady, 14:945–949, 1973

    work page 1973

  2. [2]

    Augustin Louis Cauchy.Exercices d’analyse et de physique math´ ematique. Tome I. Bachelier, Paris, 1840

    work page

  3. [3]

    Charton, J.S

    Fran¸ cois Charton, Jordan S. Ellenberg, Adam Zsolt Wagner, and Geordie Williamson. Pat- ternboost: Constructions in mathematics with a little help from AI.CoRR, abs/2411.00566,

    work page arXiv

  4. [4]

    Charton, J.S

    URL:https://doi.org/10.48550/arXiv.2411.00566,arXiv:2411.00566,doi:10. 48550/ARXIV.2411.00566

    work page doi:10.48550/arxiv.2411.00566

  5. [5]

    Cycle- factors of regular graphs via entropy.arXiv preprint arXiv:2507.19417, 2025

    Micha Christoph, Nemanja Dragani´ c, Ant´ onio Gir˜ ao, Eoin Hurley, Lukas Michel, and Alp M¨ uyesser. Cycle-factors of regular graphs via entropy. In66th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2025, Sydney, Australia, December 14-17, 2025, pages 615–619. IEEE, 2025. Extended version available as arXiv:2507.19417v2.doi:10.48550/ ar...

    work page arXiv 2025

  6. [6]

    On the path partition number of 6-regular graphs.J

    Uriel Feige and Ella Fuchs. On the path partition number of 6-regular graphs.J. Graph Theory, 101(3):345–378, 2022. URL:https://doi.org/10.1002/jgt.22830,doi:10.1002/ JGT.22830

    work page doi:10.1002/jgt.22830 2022

  7. [7]

    Ravi, and Mohit Singh

    Uriel Feige, R. Ravi, and Mohit Singh. Short tours through large linear forests. In Jon Lee and Jens Vygen, editors,Integer Programming and Combinatorial Optimization - 17th Interna- tional Conference, IPCO 2014, Bonn, Germany, June 23-25, 2014. Proceedings, Lecture Notes in Computer Science, pages 273–284. Springer, 2014.doi:10.1007/978-3-319-07557-0\_23

    work page doi:10.1007/978-3-319-07557-0 2014

  8. [8]

    Cycle partitions of regular graphs.Comb

    Vytautas Gruslys and Shoham Letzter. Cycle partitions of regular graphs.Comb. Probab. Comput., 30(4):526–549, 2021.doi:10.1017/S0963548320000553

    work page doi:10.1017/s0963548320000553 2021

  9. [9]

    Colton Magnant and Daniel M. Martin. A note on the path cover number of regular graphs. Australas. J Comb., 43:211–217, 2009. URL:http://ajc.maths.uq.edu.au/pdf/43/ajc_ v43_p211.pdf

    work page 2009

  10. [10]

    Counting 1-factors in regular bipartite graphs.Journal of Combinatorial Theory, Series B, 72(1):122–135, 1998

    Alexander Schrijver. Counting 1-factors in regular bipartite graphs.Journal of Combinatorial Theory, Series B, 72(1):122–135, 1998. URL:https://www.sciencedirect.com/science/ article/pii/S0095895697917986,doi:10.1006/jctb.1997.1798

    work page doi:10.1006/jctb.1997.1798 1998

  11. [11]

    Nisheeth K. Vishnoi. A permanent approach to the traveling salesman problem. In2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pages 76–80, 2012.doi: 10.1109/FOCS.2012.81. 11

    work page doi:10.1109/focs.2012.81 2012