Draganic 2025 cyclic subsets regular dirac graphs

../

conjecture_6_1: The paper proposes a clique-factor analog, later claimed for large orders.

external_inputs: Precise external graph and probability results used by the paper.

lemma_2_3: Bidensity and near-Dirac degree survive random vertex sampling.

lemma_2_4: Random sampling preserves two dense pieces and a crossing matching.

lemma_2_5: Regularity supplies enough internal edges to absorb a random imbalance.

lemma_3_12: Complementing Bernoulli trials converts a difference to one binomial.

lemma_3_4: Two disjoint crossing edges join dense halves into a Hamilton cycle.

lemma_3_5: One extra unit of minimum degree gives prescribed Hamilton-path endpoints.

lemma_3_6: Regularity forces a square-root-sized crossing matching.

lemma_3_7: An internal linear forest balances a dense bipartite core.

lemma_3_8: A dense balanced bipartite graph has prescribed opposite-part Hamilton paths.

lemma_3_9: The product of the two internal cover sizes is forced by regularity.

lemma_4_2: Internal matchings and linear forests beat a half-probability barrier.

lemma_4_3: Regularity and cover sizes give internal graphs suitable for linear arboricity.

lemma_4_4: A two-stage exposure loses only a factor four from cover to matching.

lemma_4_6: Small maximum degree relative to edge count gives relative concentration.

lemma_4_7: Two competing forest bounds give a uniform probability above one half.

lemma_5_1: Every proposed extremal graph has cyclic-subset density one half plus a central-binomial correction.

lemma_5_2: An exact difference identity and central-binomial expansion control second-order probabilities.

proposition_1_3: The paper states a nonregular sufficient condition and gives only a short proof pointer.

remarks_p14: The paper leaves the optimal two-factor and other sampling regimes unresolved.

remarks_p2: Balanced bipartite graphs and added stars explain the degree and regularity assumptions.

theorem_1_2: The published exact minimum theorem is recorded with explicit reconstruction gaps.

theorem_2_2: The three structural cases prove the Erdős–Faudree question.

theorem_4_1: A robust balanced-cut argument improves the initial positive constant to one half.

---

Nemanja Draganić, Peter Keevash, and Alp Müyesser, Cyclic Subsets in Regular Dirac Graphs, International Mathematics Research Notices 2025(14), rnaf215, 1–16, DOI.

Source versions

The canonical folder-name PDF is the published open-access article, received 19 March 2025, revised 23 June 2025, accepted 27 June 2025, and published online 22 July 2025. It was obtained from the Oxford University Research Archive on 2026-09-05. Its printed pages and PDF pages both run from 1 to 16. All result labels and page citations in this folder refer to that version.

The original 17-page PDF is retained unchanged as draganic_2025_cyclic_subsets_regular_dirac_graphs_arxiv_v2.pdf: arXiv:2503.01826v2, 31 March 2025. The arXiv record still lists v2 as its latest revision as of the source check. The mathematical result labels are retained in the published version; typesetting changes the page breaks, the unused McKay reference is removed, and later bibliography entries are renumbered. The specific arithmetic and proof-bookkeeping issues identified on result pages occur in both versions. No published correction was found in the bounded arXiv, author-page, journal, and title/erratum searches. The published PDF (draganic_2025_cyclic_subsets_regular_dirac_graphs.pdf) prints "© The Author(s) 2025. Published by Oxford University Press. This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted reuse, distribution, and reproduction in any medium, provided the original work is properly cited." on its first page, the Creative Commons Attribution 4.0 license. For the arXiv PDF (draganic_2025_cyclic_subsets_regular_dirac_graphs_arxiv_v2.pdf) the arXiv record names the Creative Commons Attribution 4.0 license (arXiv:2503.01826).

Results and proof coverage

A vertex subset is cyclic if it induces a graph with a Hamilton cycle. Writing $p(G)=\operatorname{Cyc}(G)/2^{|V(G)|}$ turns the problem into Hamiltonicity of a uniform random induced subgraph.

Theorem 2.2 proves that every $(n+1)$-regular graph on $2n$ vertices has $p(G)\ge c$ for an absolute $c>0$, resolving the Erdős–Faudree question. Its rewritten proof includes the bidense case Lemma 2.3, the two-almost-cliques case Lemma 2.4, and the almost-bipartite case Lemma 2.5, with their supporting path, matching, and cover lemmas. The external structural classification and probability tools are stated in external inputs, without recursive proofs.

Theorem 4.1 improves the lower bound to $1/2-o(1)$. The proof uses Lemma 4.2, combining cover sizes, internal bounded-degree subgraphs, asymptotic linear arboricity, and the calculus inequality in Lemma 4.7. The reconstruction makes the source's constant, parameter, and cut-transfer bookkeeping explicit; these local clarifications are identified on the affected pages.

Theorem 1.2 states that, for sufficiently large $n$, the minimum is attained in the family $\mathcal G_n$ obtained from $K_{n-1,n+1}$ by adding a $2$-factor in its larger part. Its exact-proof page currently contains a detailed source proof map and an unresolved conditional-exposure estimate in its small-cover cases and missing quantitative failure bounds, not a complete rewritten proof. Routine cut-transfer, matching, endpoint, and sign repairs are recorded separately. These stronger-result reconstruction limits do not change the original problem's proved status.

For every member of $\mathcal G_n$, Lemma 5.1 proves

$$p(G)=\frac12+\frac{3}{2\sqrt{\pi n}}+O(n^{-3/2}).$$

The theorem does not specify which $2$-factor minimizes the exponentially small remainder. remarks p14 preserves that question and other sampling and degree directions.

remarks p2 records the elementary obstructions when degree $n+1$ is lowered to $n$ or regularity is replaced by minimum degree. Proposition 1.3 records the nonregular $N/2+\Omega(\sqrt N)$ minimum-degree proposition as a source sketch, with its omitted details explicit. Conjecture 6.1 records the clique-factor question and the later Sun–Wei–Yang large-order resolution claim.

Later literature and formalization

The 2026-09-05 search also found Liu–Niu–Wang–Yan's lower-degree staircase bounds and Hunter–Liu–Milojević–Sudakov's tournament analog; precise primary-source leads and their differing scopes are in remarks p14. They were not found to replace the exact theorem for $(n+1)$-regular graphs on $2n$ vertices. Their proofs remain separate compilation tasks. No materially distinct accepted proof of the graph question was found in this bounded search or the discussion thread (accessed 2026-09-05).

The Problem 622 page accessed records no formalized statement or solution. A bounded GitHub/web search found no corresponding public Lean artifact; no Lean build or formalization was performed.

Bears on. Problem 622.