pith. sign in

arxiv: 2604.05138 · v1 · submitted 2026-04-06 · 🧮 math.PR

Convergence rate of H-property for step-graphons

Wanting Gao , Hong Hu , Xudong Chen This is my paper

Pith reviewed 2026-05-10 18:48 UTC · model grok-4.3

classification 🧮 math.PR
keywords graphonsH-propertycycle coversconvergence ratesstep-graphonsrandom graphszero-one laws
0
0 comments X

The pith

For step-graphons the probability of a node-disjoint cycle cover in random graphs converges either exponentially or at rate 1 over square root of n.

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

The paper determines the speed at which the probability that a random graph sampled from a step-graphon possesses a node-disjoint cycle cover approaches its zero or one limit. This builds on the earlier zero-one law by distinguishing two possible speeds: exponential decay when the limit is reached quickly, and slower convergence of order one over square root of n when fluctuations last longer. A reader would care because the rate reveals how large n must be before the cycle-cover behavior becomes predictable in finite graphs drawn from the graphon. The distinction arises from the particular step structure of the graphon, and the authors supply both a proof and numerical checks.

Core claim

For any step-graphon the probability that a random simple undirected graph Gn on n vertices sampled from it has a node-wise disjoint cycle cover converges to either zero or one at a rate that is either exponential in n or of order 1/sqrt(n). The type of rate depends on the values and partition that define the step-graphon. The result is established by direct analysis of the cycle-cover probability under the standard graphon sampling model.

What carries the argument

The H-property of a graphon, defined by the existence of a node-disjoint cycle cover in the sampled random graph, together with the two-type classification of its convergence rate to the zero-one limit.

Load-bearing premise

The graphon must be a step-graphon and the cycle-cover probability must obey the zero-one law established in prior work.

What would settle it

Finding even one step-graphon where the cycle-cover probability converges to its limit at a rate that is neither exponential nor order 1/sqrt(n) would falsify the two-type claim.

Figures

Figures reproduced from arXiv: 2604.05138 by Hong Hu, Wanting Gao, Xudong Chen.

Figure 1
Figure 1. Figure 1: Left: A step-graphon W and its skeleton graph S. Right: The associated edge cone X(S) and concentration vector x ∗ plotted in the standard 2-simplex. Definition 3 (Concentration vector). Let W be a step-graphon with partition σ = (σ0, . . . , σq). The associated concentration vector x ∗ = (x ∗ 1 , . . . , x∗ q ) is such that x ∗ i := σi − σi−1, for all i = 1, . . . , q. Note that x ∗ is a probability vecto… view at source ↗
Figure 2
Figure 2. Figure 2: An example step-graphon W⋆ is shown in (a). The associated common skeleton graph is shown in (c), for ⋆ = a, b, c, d, e, f. The shaded region in (b) represents X := X∩∆2 . The blue points a, b, and c belong to int X and correspond to the concentration vectors x ∗ a , x ∗ b , and x ∗ c , respectively. The three red points d, e, and f belong to ∆2 −X and correspond to the concentration vectors x ∗ d , x ∗ e … view at source ↗
Figure 3
Figure 3. Figure 3: Linear fit of log(1 − p⋆(n)) for ⋆ = a, b, c. 20 40 60 80 100 120 140 160 180 200 −12 −10 −8 −6 −4 −2 Number of nodes n log( p⋆(n)) log(pd(n)) log(pe(n)) log(pf (n)) [PITH_FULL_IMAGE:figures/full_fig_p014_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Linear fit of log(p⋆(n)) for ⋆ = d, e, f. 14 [PITH_FULL_IMAGE:figures/full_fig_p014_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: plots log(p⋆(n)) versus n for ⋆ = g, h, i. The data again follow an approx￾imately linear trend, confirming exponential decay. The fitted rates are about e −0.014n , e −0.039n , and e −0.173n for Cases (g), (h), and (i), respectively. The difference in rates is explained by the relative positions of x ∗ with respect to X. 20 40 60 80 100 120 140 160 180 200 −12 −10 −8 −6 −4 −2 Number of nodes n log( p⋆(n))… view at source ↗
Figure 6
Figure 6. Figure 6: (a) A representative illustration of the step-graphon [PITH_FULL_IMAGE:figures/full_fig_p016_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Plot of log(pj (n)) versus log n with its linear fit. 3.2.2 Validation of item 4 Finally, we consider the step-graphon Wk shown in Fig. 6b, it can be verified that the concentration vector x ∗ k ∈ ∂X, so Pn(Wk) → p ∗ , with p ∗ = 0.1669 (See Example 2 in [3]). To examine the convergence rate, we plot log |pk(n)−p ∗ | versus log n and perform a linear 16 [PITH_FULL_IMAGE:figures/full_fig_p016_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Plot of log(|pk(n) − p ∗ |) versus log(n) with its linear fit, where p ∗ = 0.1669. Taken together, the experiments in this section clearly illustrate the two regimes stated by Theorem 1: exponential convergence for item 1 and item 2, and the n −1/2 order convergence in item 3 and item 4. They also show that in the exponential regime, the rate is strongly influenced by the location of x ∗ relative to X. 4 C… view at source ↗
read the original abstract

A graphon is said to have the $H$-property if a random undirected graph $G_n$ on $n$ nodes sampled from it has a node-wise disjoint cycle cover almost surely as $n\to\infty$. It has been shown in the earlier work that the $H$-property obeys the zero-one law, i.e., the probability that the random graph has a cycle cover tends to either one or zero. In this paper, we sharpen the result by characterizing the convergence rate of the probability. Specifically, we show that there are two different types of rates, with one being exponential and the other being root $n$. We provide a rigorous proof and numerical validation.

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

2 major / 3 minor

Summary. The paper sharpens the zero-one law for the H-property of step-graphons by establishing explicit convergence rates for the probability that a random graph G_n sampled from the graphon admits a node-disjoint cycle cover. For step-graphons, this probability converges to its limiting value (0 or 1) either exponentially fast or at rate n^{-1/2}, with the dichotomy determined by whether a linear combination of the step values lies strictly above or equals the critical threshold from the prior zero-one law. The argument reduces the problem to finite-dimensional functionals on the step blocks, applies large-deviation principles in one regime and the central limit theorem in the other, and includes numerical simulations comparing simulated probabilities to the predicted asymptotics.

Significance. If the derivations hold, the result supplies a quantitative refinement of the H-property zero-one law that distinguishes large-deviation and CLT regimes via an explicit criterion on the step values. The reduction to finite steps, explicit rate derivations, and numerical validation constitute strengths that could guide extensions to other subgraph properties in graphon sampling models.

major comments (2)
  1. [§3, Theorem 3.2] §3, Theorem 3.2 (exponential regime): the large-deviation rate function for the relevant edge-count functional is asserted to be strictly positive when the linear combination exceeds the threshold, but the proof sketch does not explicitly verify that the minimizer lies outside the feasible set for the cycle-cover event; this step is load-bearing for the exponential claim.
  2. [§4, Theorem 4.1] §4, Theorem 4.1 (root-n regime): the variance of the normalized edge-count statistic under the CLT is stated to be positive and finite, yet the argument relies on the block independence induced by the step-graphon without deriving the explicit covariance matrix from the step values; an explicit formula or bound would strengthen the rate statement.
minor comments (3)
  1. [§5] The notation for the step values w_{ij} and the threshold c is defined in §2 but reused in §5 without a brief reminder, which could confuse readers following the numerical examples.
  2. [Figure 2] Figure 2 caption should specify the exact step-graphon parameters (number of steps and values) used in the simulation to allow direct reproduction of the plotted curves.
  3. [§5] The abstract mentions 'numerical validation' but the main text does not include a table of fitted rates versus theoretical predictions; adding such a summary table would improve clarity.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We address each major comment below and will make the indicated revisions to strengthen the proofs.

read point-by-point responses

  1. Referee: [§3, Theorem 3.2] §3, Theorem 3.2 (exponential regime): the large-deviation rate function for the relevant edge-count functional is asserted to be strictly positive when the linear combination exceeds the threshold, but the proof sketch does not explicitly verify that the minimizer lies outside the feasible set for the cycle-cover event; this step is load-bearing for the exponential claim.

    Authors: We agree that the verification is load-bearing and that the sketch in the current manuscript does not make the argument fully explicit. In the revised version we will insert a short lemma establishing that, when the linear combination of step values strictly exceeds the critical threshold, the unique minimizer of the large-deviation rate function under the cycle-cover constraint lies outside the feasible set; this will confirm that the rate is strictly positive and complete the exponential claim. revision: yes

  2. Referee: [§4, Theorem 4.1] §4, Theorem 4.1 (root-n regime): the variance of the normalized edge-count statistic under the CLT is stated to be positive and finite, yet the argument relies on the block independence induced by the step-graphon without deriving the explicit covariance matrix from the step values; an explicit formula or bound would strengthen the rate statement.

    Authors: We acknowledge that an explicit covariance formula would improve clarity. In the revision we will compute the covariance matrix of the normalized edge-count vector directly from the step values and block sizes, and we will verify that the resulting variance is positive and finite under the standing assumptions of the theorem. revision: yes

Circularity Check

0 steps flagged

No significant circularity; rates derived independently from zero-one law base case

full rationale

The paper invokes an earlier zero-one law for the H-property (from prior work) as the starting point for classifying step-graphons into exponential vs. root-n regimes, but then performs fresh large-deviation and CLT analysis on the finite collection of block edge-count functionals to obtain the explicit rates. This additional analytic step is not reducible to the prior result by definition or by fitting; the classification criterion itself is stated in terms of an explicit linear combination of step values relative to the known threshold. No self-definitional loops, fitted inputs renamed as predictions, or load-bearing uniqueness theorems imported from the same authors appear in the derivation chain. The numerical validation compares simulations to the newly derived asymptotics rather than to quantities defined by the fit.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review supplies no explicit free parameters, axioms, or invented entities; the work builds on the prior definition of the H-property and the zero-one law without introducing new postulated objects.

pith-pipeline@v0.9.0 · 5405 in / 1058 out tokens · 35122 ms · 2026-05-10T18:48:51.345440+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

14 extracted references · 14 canonical work pages · 1 internal anchor

  1. [1]

    On the H-property for step-graphons and edge polytopes

    M.-A. Belabbas, X. Chen, and T. Ba¸ sar. “On the H-property for step-graphons and edge polytopes”. In:IEEE Control Systems Letters6 (2021), pp. 1766–1771

    work page 2021

  2. [2]

    Geometric Characterization of theH-property for Step-graphons

    M.-A. Belabbas and X. Chen. “Geometric Characterization of theH-property for Step-graphons”. In:IEEE Transactions on Automatic Control69.6 (2023), pp. 3849– 3864

    work page 2023

  3. [3]

    On theH-property for Step-graphons: The Residual Case

    W. Gao and X. Chen. “On theH-property for Step-graphons: The Residual Case”. In:IFAC-PapersOnLine59.4 (2025), pp. 7–12

    work page 2025

  4. [4]

    Decentralized stabilization with symmetric topolo- gies

    A. Kirkoryan and M.-A. Belabbas. “Decentralized stabilization with symmetric topolo- gies”. In:53rd IEEE Conference on Decision and Control. IEEE. 2014, pp. 1347– 1352. 17

    work page 2014

  5. [5]

    Sparse linear ensemble systems and structural controllability

    X. Chen. “Sparse linear ensemble systems and structural controllability”. In:IEEE Transactions on Automatic Control67.7 (2021), pp. 3337–3348

    work page 2021

  6. [6]

    Structural System Theory over Random Networks

    M.-A. Belabbas and X. Chen. “Structural System Theory over Random Networks”. In:2025 IEEE 64th Conference on Decision and Control (CDC). IEEE. 2025, pp. 7611– 7628

    work page 2025

  7. [7]

    Normal polytopes arising from finite graphs

    H. Ohsugi and T. Hibi. “Normal polytopes arising from finite graphs”. In:Journal of Algebra207.2 (1998), pp. 409–426

    work page 1998

  8. [8]

    Largest $2$-regular Subgraphs in complete $S$-partite Graphs

    Y. Jiang and X. Chen. “Largest 2-regular Subgraphs in completeS-partite Graphs”. In:arXiv:2603.27424(2026)

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  9. [9]

    Blow-up Lemma

    J. Koml´ os, G. N. S´ ark¨ ozy, and E. Szemer´ edi. “Blow-up Lemma”. In:Combinatorica 17.1 (1997), pp. 109–123

    work page 1997

  10. [10]

    Hamiltonicity of Step-graphons

    X. Chen. “Hamiltonicity of Step-graphons”. In:arXiv preprint arXiv:2510.02074 (2025)

    work page arXiv 2025

  11. [11]

    Probability inequalities for sums of bounded random variables

    W. Hoeffding. “Probability inequalities for sums of bounded random variables”. In: Journal of the American statistical association58.301 (1963), pp. 13–30

    work page 1963

  12. [12]

    Asymptotic behavior of the multinomial dstribution

    N. Arenbaev. “Asymptotic behavior of the multinomial dstribution”. In:Theory of Probability & Its Applications21.4 (1977), pp. 805–810

    work page 1977

  13. [13]

    On the dependence of the Berry–Esseen bound on dimension

    V. Bentkus. “On the dependence of the Berry–Esseen bound on dimension”. In: Journal of Statistical Planning and Inference113.2 (2003), pp. 385–402

    work page 2003

  14. [14]

    Vershynin.High-dimensional probability: An introduction with applications in data science

    R. Vershynin.High-dimensional probability: An introduction with applications in data science. Vol. 47. Cambridge university press, 2018. 18

    work page 2018