pith. sign in

arxiv: 2604.27452 · v1 · submitted 2026-04-30 · 🧮 math.CO

The H-linkage problems in sparse robustly expanding digraphs

Zhilan Wang , Jin Yan This is my paper

Pith reviewed 2026-05-07 08:19 UTC · model grok-4.3

classification 🧮 math.CO
keywords digraphsdegree sequencesH-linkagesubdivision tilingNash-Williams conjectureHamilton cyclesgraph subdivisionsdirected graphs
0
0 comments X

The pith

Large digraphs satisfying specific asymptotic degree conditions are N H-linked for any fixed digraph H and admit perfect H-subdivision tilings.

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

The paper strengthens asymptotic versions of the Nash-Williams conjecture for Hamilton cycles by extending them to general H-linkage problems. It establishes that under degree sequence conditions involving a parameter gamma for all gamma in (0,1), a large digraph contains an H-subdivision for any H using any prescribed set of branch vertices with each path at least some minimum length. The same conditions ensure a perfect tiling of the vertex set by such H-subdivisions, each of order at least a constant depending on H. This matters to a reader because it shows how sparse degree conditions in directed graphs suffice not just for cycles but for embedding and decomposing into arbitrary fixed structures.

Core claim

If for every gamma in (0,1) and every integer i with 0 ≤ i < n/2, the out-degree sequence satisfies d_i^+ ≥ i + gamma n or d_{n-i-gamma n}^- ≥ n-i, and the in-degree sequence satisfies the symmetric condition, then a sufficiently large digraph D is (N H)-linked for any digraph H, meaning it contains an H-subdivision with given branch vertices and sufficiently long paths, and D admits a perfect H-subdivision tiling with each component having order at least C_0.

What carries the argument

The (N H)-linked property, which guarantees the existence of an H-subdivision with prescribed branch-vertex set U of size |V(H)| and path lengths l_i at least some l_0.

If this is right

  • The asymptotic Nash-Williams conjecture for directed Hamilton cycles follows as a special case when H is a directed cycle.
  • The digraph can be partitioned into vertex-disjoint copies of subdivided H covering all vertices.
  • Linkage results hold uniformly for all choices of branch vertices and for arbitrarily large path lengths in the subdivisions.
  • These conditions unify results on path, cycle, and more general subdivision embeddings in digraphs.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar conditions could be investigated for other classes of graphs or hypergraphs beyond digraphs.
  • The robust expansion properties implied by the degree conditions may allow for efficient algorithms to find the required subdivisions.
  • Relaxing the 'for every gamma' to a fixed gamma might still work but would require different proof techniques or stronger assumptions.
  • Connections to tiling problems in undirected graphs with analogous degree conditions remain open for exploration.

Load-bearing premise

The digraph must have sufficiently large order n and its degree sequences must satisfy the or-conditions for every gamma greater than zero and less than one.

What would settle it

A large digraph whose degree sequences meet the conditions for all gamma but fails to have an H-subdivision with some prescribed branch vertices U and large enough path lengths l_i for a small fixed H.

Figures

Figures reproduced from arXiv: 2604.27452 by Jin Yan, Zhilan Wang.

Figure 1
Figure 1. Figure 1: A ladder L = Q ∪ Q1 ∪ Q3 ∪ · · · ∪ Q2k−1 view at source ↗
Figure 2
Figure 2. Figure 2: Rung paths of L. 7 view at source ↗
Figure 3
Figure 3. Figure 3: Alternative rung paths of L. We say a ladder L is embedded in an H-subdivision H′ if all even-indexed rungs Ri (i ∈ {0, 2, 4, . . . , 2k}) are subpaths of some single subdivided path of H′ . Immediately after that, we present the following result. Lemma 2.9. Let H and D be digraphs, and let {v0, v∗ 0} ⊂ V (D). Consider a ladder Lv0,v∗ 0 ⊆ D embedded in an H-subdivision H′ ⊆ D. Then for any path P = v0 · · … view at source ↗
read the original abstract

The Nash-Williams conjecture establishes degree sequence conditions ensuring Hamilton cycles in digraphs. An asymptotic version of this conjecture for large digraphs was independently derived by several researchers. We strengthen these results by proving the following results under the same asymptotic degree sequence conditions. For any digraph $H$, a digraph $D$ is $(\mathcal{N}H)$-linked if there exists an integer $l_0$ such that for any vertex set $U$ of cardinality $|V(H)|$ and every integer set $\mathcal{N}=\{l_i\}_{i=1}^{|A(H)|}$ with $l_i\geq l_0$, $D$ contains an $H$-subdivision with $U$ as branch-vertex set and the values in $\mathcal{N}$ specifying the lengths of the subdivided paths. Let $D$ be a sufficiently large digraph of order $n$ with the out-degree sequence $d_1^+\leq\cdots\leq d_n^+$ and the in-degree sequence $d_1^-\leq\cdots\leq d_n^-$. We prove that if for every $\gamma\in(0, 1)$ and every integer $0\leq i<n/2$, the following conditions hold: (i) $d_i^+\geq i+\gamma n$ or $d_{n-i-\gamma n}^-\geq n-i$, and (ii) $d_i^-\geq i+\gamma n$ or $d_{n-i-\gamma n}^+\geq n-i$, then $D$ is $(\mathcal{N}H)$-linked, and also admits a perfect $H$-subdivision tiling with subdivision orders $\{n_1, \ldots, n_k\}$, where each $n_i\geq C_0$ for some integer $C_0$.

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

0 major / 4 minor

Summary. The manuscript proves that any sufficiently large digraph D whose out- and in-degree sequences satisfy the stated or-conditions (i) and (ii) for every γ ∈ (0,1) is (𝒩H)-linked for every fixed digraph H: for any branch-vertex set U of size |V(H)| and any tuple 𝒩 of path lengths all at least some l0, D contains an H-subdivision with those branch vertices and path lengths. The same degree conditions also guarantee a perfect tiling of V(D) by H-subdivisions each of order at least C0. The argument first extracts robust expansion (with parameters depending on γ) from the degree-sequence hypotheses via a Chvátal-type counting argument, then invokes known embedding and absorbing lemmas for subdivisions in robust expanders.

Significance. If the derivation holds, the result meaningfully strengthens the asymptotic Nash-Williams theorem by showing that the same sparse degree conditions already suffice for arbitrary fixed-H linkage and for perfect subdivision tilings. The reduction through robust expansion is a natural and economical route; the parameter tracking (l0 and C0 depending on H and the expansion constants) is absorbed by the “sufficiently large n” quantifier, which is explicitly stated. This supplies a unified sparse-expansion framework for a family of embedding problems that previously required separate arguments.

minor comments (4)
  1. [§1] §1 (Definition of (𝒩H)-linked): the quantifiers on l0 and the set 𝒩 are introduced only informally; a single displayed definition with all parameters would improve readability and make the dependence on |H| transparent.
  2. [§3] §3 (Derivation of robust expansion): the proof sketch that the or-conditions imply (γ,k)-robust expansion is standard, but the dependence of the expansion parameter k on γ and on the minimal degree should be recorded explicitly (even if only as k = k(γ) > 0) so that the subsequent choice of l0 can be verified to scale correctly.
  3. [Theorem 1.2] Theorem 1.2 (tiling): the statement that the tiling exists with each ni ≥ C0 is correct, yet the proof sketch does not indicate how the absorbing lemma is applied after the linkage step to guarantee that the leftover set is empty; a short paragraph outlining the absorption phase would remove any doubt about the reduction from tiling to repeated linkage.
  4. [Notation] Notation: the symbols d_i^+ and d_i^- are used both for the sorted sequences and for the actual degrees; a brief sentence clarifying that the sequences are non-decreasing would prevent any momentary confusion when the indices n-i-γn appear.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive and accurate summary of our manuscript, as well as for recommending only minor revision. The referee correctly notes that the results strengthen the asymptotic Nash-Williams theorem by establishing both (𝒩H)-linkage for arbitrary fixed H and perfect H-subdivision tilings under the same sparse degree-sequence conditions, with the proof proceeding via extraction of robust expansion followed by known embedding and absorbing lemmas. We agree that this supplies a unified framework and that the parameter dependence is absorbed by the sufficiently-large-n quantifier.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper derives robust expansion from the stated degree-sequence or-conditions via a standard Chvátal-type counting argument that is independent of the target linkage and tiling statements. It then invokes known embedding and absorbing lemmas for H-subdivisions whose parameters scale with the fixed H and l0; the 'sufficiently large n' quantifier absorbs all H-dependent constants. No equation or step reduces the claimed (NH)-linkage or perfect tiling to a fitted input, self-definition, or load-bearing self-citation chain. The central theorems therefore constitute an independent strengthening of prior asymptotic results rather than a tautological rephrasing of the input conditions.

Axiom & Free-Parameter Ledger

2 free parameters · 1 axioms · 0 invented entities

Relies on standard digraph definitions and degree sequences. Constants C_0 and l_0 are asserted to exist but not derived explicitly. No new entities or fitted parameters beyond existence claims.

free parameters (2)
  • C_0
    Existence of integer lower bound on tile orders depending on H.
  • l_0
    Lower bound on path lengths asserted for large n.
axioms (1)
  • standard math Standard properties of directed graphs, degree sequences, and subdivisions.
    Implicit in theorem statement and definitions.

pith-pipeline@v0.9.0 · 10136 in / 1197 out tokens · 117155 ms · 2026-05-07T08:19:25.758027+00:00 · methodology

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

24 extracted references · 4 canonical work pages

  1. [1]

    Bang-Jensen and G

    J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications, 2nd ed., Springer-Verlag, London, 2009

    2009

  2. [2]

    Cheng, Z

    Y. Cheng, Z. Wang, and J. Yan,A Dirac-type theorem for arbitrary HamiltonH- linked digraphs, arXiv:2401.17475

    work page arXiv

  3. [3]

    Cheng, Z

    Y. Cheng, Z. Wang, and J. Yan,SpanningH-subdivisions and perfectH-subdivision tilings in dense digraphs, arXiv:2411.07786

    work page arXiv

  4. [4]

    Christofides, P

    D. Christofides, P. Keevash, D. K¨ uhn, and D. Osthus,A semi-exact degree condition for Hamilton cycles in digraphs, SIAM J. Discrete Math.24(2010), 709–756

    2010

  5. [5]

    Christofides, P

    D. Christofides, P. Keevash, D. K¨ uhn, and D. Osthus,Finding Hamilton cycles in robustly expanding digraphsJ. Graph Algorithms Appl.16(2012), 335–358

    2012

  6. [6]

    Chv´ atal,On Hamilton’s ideals, J

    V. Chv´ atal,On Hamilton’s ideals, J. Combin. Theory Ser. B12(1972), 163–168. 14

    1972

  7. [7]

    Ferrara, M

    M. Ferrara, M. Jacobson, and F. Pfender,Degree conditions forH-linked digraphs, Combin. Probab. Comput.22(2013), 684–699

    2013

  8. [8]

    G. Wang, Y. Wang, and Z. Zhang,Arbitrary orientations of cycles in oriented graphs, arXiv:2504.09794v1

    work page arXiv

  9. [9]

    Keevash, D

    P. Keevash, D. K¨ uhn, and D. Osthus,An exact minimum degree condition for Hamil- ton cycles in oriented graphs, J. London Math. Soc.79(2009), 144–166

    2009

  10. [10]

    Kelly, D

    L. Kelly, D. K¨ uhn, and D. Osthus,A Dirac-type result on Hamilton cycles in oriented graphs, Combin. Probab. Comput.17(2008), 689–709

    2008

  11. [11]

    K¨ uhn and D

    D. K¨ uhn and D. Osthus,Linkedness and ordered cycles in digraphs, Combin. Probab. Comput.17(2008), 411–422

    2008

  12. [12]

    K¨ uhn and D

    D. K¨ uhn and D. Osthus,The minimum degree threshold for perfect graph packings, Combinatorica29(2009), 65–107

    2009

  13. [13]

    K¨ uhn and D

    D. K¨ uhn and D. Osthus,A survey on Hamilton cycles in directed graphs, Europ. J. Combin.33(2012), 750–766

    2012

  14. [14]

    K¨ uhn and D

    D. K¨ uhn and D. Osthus,Hamilton decompositions of regular expanders: a proof of Kelly’s conjecture for large tournaments, Adv. Math.237(2013), 62–146

    2013

  15. [15]

    K¨ uhn and D

    D. K¨ uhn and D. Osthus,Hamilton decompositions of regular expanders: applications, J. Combin. Theory Ser. B104(2014), 1–27

    2014

  16. [16]

    K¨ uhn, D

    D. K¨ uhn, D. Osthus, and A. Treglown,Hamilton degree sequences in digraphs, J. Combin. Theory Ser. B100(2010), 367–380

    2010

  17. [17]

    K¨ uhn, D

    D. K¨ uhn, D. Osthus, and A. Young,k-Ordered Hamilton cycles in digraphs, J. Com- bin. Theory Ser. B98(2008), 1165–1180

    2008

  18. [18]

    Lee,Spanning subdivisions in dense digraphs, Europ

    H. Lee,Spanning subdivisions in dense digraphs, Europ. J. Combin.124(2025), 104059

    2025

  19. [19]

    Lo, and V

    A. Lo, and V. Patel,Hamilton cycles in sparse robustly expanding digraphs, Electron J. Combin.25(2018), #P3.14

    2018

  20. [20]

    Nash-Williams, Hamilton circuits in graphs and digraphs, in: The Many Facets of Graph Theory, in: Springer Verlag Lecture Notes, vol

    C.St.J.A. Nash-Williams, Hamilton circuits in graphs and digraphs, in: The Many Facets of Graph Theory, in: Springer Verlag Lecture Notes, vol. 110, Springer Verlag, 1968, pp. 237–243

    1968

  21. [21]

    Nash-Williams,Hamilton circuits, Stud

    C.St.J.A. Nash-Williams,Hamilton circuits, Stud. Math.12(1975), 301–360

    1975

  22. [22]

    Osthus and K

    D. Osthus and K. Staden,Approximate Hamilton decompositions of robustly expand- ing regular digraphs, Siam J. Discrete Math.27(2013), 1372–1409. 15

    2013

  23. [23]

    R¨ odl, A

    V. R¨ odl, A. Ruci´ nski, and E. Szemer´ edi,A Dirac-type theorem for3-uniform hyper- graphs, Combin. Probab. Comput.15(2006), 229–251

    2006

  24. [24]

    Zhou and J

    J. Zhou and J. Yan,Arbitrary H-linked oriented graphs, arXiv:2407.06675. 16

    work page arXiv