Cycle-factors of regular graphs via entropy
read the original abstract
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.
This paper has not been read by Pith yet.
Forward citations
Cited by 5 Pith papers
-
Counterexamples to an Extremal Conjecture for Random Cycle-Factors
The paper disproves the conjecture that the disjoint union of complete looped digraphs uniquely maximizes expected cycle count in random cycle-factors of d-regular digraphs for d >= 3, via explicit constructions yield...
-
Counterexamples to an Extremal Conjecture for Random Cycle-Factors
For every d >= 3 and n = k d with k >= 2, there exist directed d-regular graphs on n vertices whose random cycle-factors have expected cycle count strictly larger than k H_d, disproving the conjecture that the disjoin...
-
SWE-Edit: Rethinking Code Editing for Efficient SWE-Agent
Decomposing the code editing interface into Viewer and Editor subagents raises SWE-Bench Verified resolve rate by 2.1 pp, cuts inference cost by 17.9%, and lets an 8B model reach parity with larger editors via GRPO training.
-
The Lov\'asz conjecture holds for moderately dense Cayley graphs
Every large connected Cayley graph with degree at least n to the power 1-c for some fixed c>0 has a Hamilton cycle.
-
SWE-Edit: Rethinking Code Editing for Efficient SWE-Agent
SWE-Edit decomposes agent code editing into specialized subagents and adaptive editing modes, raising resolved rate 2.1% and cutting inference cost 17.9% on SWE-bench Verified while releasing a predictive editing benchmark.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.