Graph limits: An alternative approach to s-graphons

Martin Dole\v{z}al

Graph limits: An alternative approach to s-graphons

T0 review · 0 major / 5 minor · reviewed 2026-08-27 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper shows that s-convergence of graph sequences is equivalent to convergence of a single compact set, the shape.

desk verdict Clean new characterization of s-convergence via a single compact shape; solid proof with one acknowledged external dependency. read the letter →

arxiv 2009.10635 v2 pith:ODK5ORU4 submitted 2020-09-22 math.CO

Martin Doležal This is my paper · ORCID

classification math.CO MSC 05C8005C99

keywords graphlimitss-convergences-graphonsshapesk-shapesVietoristopologyfairlydistributedfunctionssparse

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper gives a new characterization of s-convergence, a unified notion of limit for arbitrary graph sequences that covers dense and sparse cases. Instead of checking the infinite family of k-shapes C(µ,k), it is enough to check convergence of one compact set of probability measures, the shape C(µ). The main theorem proves the two forms of convergence are equivalent, and the same statement transfers to sequences of finite graphs. A quantitative regularity lemma is the key tool: every shape is uniformly close to some embedded K-shape, with K depending only on the desired accuracy. This makes s-convergence amenable to the standard topology of hyperspaces of compact sets.

What carries the argument

The central object is the shape C(µ) = cl{Φ(f,µ) : f ∈ FDC}, built from continuous functions f on [0,1]^2 whose vertical and horizontal sections both integrate to 1. Lemma 1 shows the shape is the weak closure of the union of all embedded k-shapes, and Lemma 2 pins each embedded k-shape as the intersection of the shape with the piecewise-constant measures on a k×k grid. Lemma 3 is the load-bearing quantitative regularity lemma: for any metric compatible with the weak topology and any ε>0, there is a K such that every shape is within Hausdorff distance ε of its embedded K-shape, uniformly over all s-graphons. That uniform approximability is what lets a single convergent sequence of shapes control the infinite family of k-shapes.

What would settle it

Try to construct a sequence of s-graphons whose shapes converge in the Vietoris topology while some fixed k-shape does not converge; any such example would contradict Theorem 1, and a more targeted failure would be a Vietoris-convergent sequence of shapes whose limit is not the shape of any s-graphon.

Watch

Extended reading notes

Core claim

Theorem 1 states that for all s-graphons µ and µ_n, condition (1) — that for every k the k-shapes C(µ_n,k) converge to C(µ,k) in the Vietoris topology on compact subsets of k-by-k matrices — is equivalent to condition (2): the shapes C(µ_n) converge to C(µ) in the Vietoris topology on compact subsets of the space sG of s-graphons. The shape of µ is the weak closure of all measures Φ(f,µ), where f ranges over continuous fairly distributed functions and Φ(f,µ) has density φ(f,µ)(u,v) = ∫ f(x,u)f(y,v) dµ(x,y). Corollary 2 brings the result back to combinatorics: a sequence of finite graphs is s-convergent to µ exactly when the shapes of their normalized adjacency measures converge to C(µ).

Load-bearing premise

The proof of the implication from shape convergence to k-shape convergence imports the compactness of s-convergence and the fact that every s-graphon is an s-limit of some graph sequence; the paper explicitly does not give a self-contained proof of this compactness.

Editorial extensions

If this is right

Corollary 1: two s-graphons are isomorphic exactly when their shapes coincide, making the shape a complete isomorphism invariant.
Corollary 2: s-convergence of a graph sequence can be tested by convergence of the single sequence of shapes instead of the infinite family of k-shapes.
Because the hyperspace of compact subsets of sG is compact, shape convergence places s-convergence in a familiar compact topological framework, which can simplify compactness and diagonal arguments.
The definition of shape is robust: Proposition 1 shows that using arbitrary bounded Borel fairly distributed functions in place of continuous ones gives the same closure.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

A natural next step is to prove a self-contained compactness theorem for shapes: if every convergent sequence of shapes had a shape limit, the main result would no longer depend on the pre-existing s-convergence compactness theorems.
The analogy with envelopes suggests that shapes could support statistical testing of s-convergence, in the way that fractional quotients are connected to multiway cuts and statistical physics in the dense graphon case.
The fairly-distributed-function calculus might extend to other convergence notions, such as local-global or Benjamini-Schramm convergence, by replacing the unit square and Lebesgue measure with a different domain.
The equivalence is likely to be useful for proving results about s-graphons that would otherwise require bookkeeping of k-shapes for every k simultaneously.

Share X Bluesky LinkedIn Reddit HN

Formalized claims in Lean

Claim #1: Theorem 1 states that for all s-graphons µ and µ_n, condition (1) — that for every k the k-shapes C(µ_n,k) converge to C(µ,k) in the Vietoris topology on compact subsets of k-by-k matrices — is equivalent to condition (2): the shapes C(µ_n) converge to C(µ) in the Vietoris topology on compact subsets of the space sG of s-graphons. The shape of µ is the weak closure of all measures Φ(f,µ), where f

/-- @claim 1 Theorem 1 states that for all s-graphons µ and µ_n, condition (1) — that for every k the k-shapes C(µ_n,k) converge to C(µ,k) in the Vietoris topology on compact subsets of k-by-k matrices — is equivalent to condition (2): the shapes C(µ_n) converge to C(µ) in the Vietoris topology on compact subsets of the space sG of s-graphons. The shape of µ is the weak closure of all measures Φ(f,µ), where f  -/
def central_claim : Prop :=

Signed reviews

No signed human review yet.

Request a human review

A listed scientist reviews the paper for a fee and the review publishes here regardless of verdict. See the reviewers or get listed.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Here is the short version: this paper gives a single compact set—the shape—that determines s-convergence, replacing the whole list of k-shapes. The main theorem, Theorem 1, says shape convergence in the Vietoris topology is equivalent to convergence of all k-shapes. That is a useful reformulation of s-convergence, and the proof is largely self-contained.

What's actually new: the shape C(µ) as a subset of sG, the regularity lemma (Lemma 3) that controls how well k-shapes approximate the shape uniformly over all s-graphons, and the resulting equivalence. The earlier envelope result for graphons in [6] is the clear inspiration, and the author says so directly. The proofs are careful and complete in the direction (1)⇒(2); Lemma 1 shows the shape is the closure of the union of k-shapes, and Lemma 3 gives a quantitative version. Proposition 1, showing continuous fairly distributed functions suffice, is a nice bit of tidying.

The only real soft spot is the converse direction. To go from shape convergence back to k-shape convergence, the argument uses the fact that the space of s-graphons modulo isomorphism is compact under k-shape convergence. That compactness is imported from Kunszenti-Kovács–Lovász–Szegedy [9, Thms 4.5, 4.7]. The paper admits this openly and even says what a self-contained proof would require: showing a Vietoris limit of shapes is itself a shape. I don't see this as a flaw in the paper, because the dependency is external, published, and non-circular—[9] defines compactness via k-shapes, not via shapes. But it does mean the paper is not a self-contained redevelopment of s-convergence.

The citation pattern is clean. The main self-citation is to [6], the envelope paper, and that is exactly the result being generalized, so it is appropriate.

Overall this is a solid, honest paper. It will be useful to anyone working on sparse or unified graph limits, and it gives a cleaner topological picture of s-convergence. It does not open a new area or solve a long-standing problem, but it is not trying to. I would send it to a serious referee. If I were the editor, I would not desk reject it.

Referee Report

0 major / 5 minor

Summary. The paper proposes an alternative description of s-convergence for s-graphons. For each s-graphon µ, it defines a compact set C(µ) ⊂ sG, called the shape, as the weak closure of measures Φ(f,µ) obtained from continuous fairly distributed functions f. The main theorem (Theorem 1) states that a sequence of s-graphons (µ_n) converges to µ in the sense of all k-shapes (i.e., s-converges) if and only if the shapes C(µ_n) converge to C(µ) in the Vietoris topology on compact subsets of sG. The proof uses two lemmas relating shapes to k-shapes (Lemmas 1 and 2), a quantitative regularity lemma (Lemma 3), and a compactness argument for the topology induced by all k-shape maps. The paper also gives the corresponding statement for graph sequences (Corollary 2) and shows that replacing continuous fairly distributed functions by arbitrary bounded Borel ones does not change the shape (Proposition 1).

Significance. If correct, the result provides a clean single-object characterization of s-convergence, closely analogous to the envelope characterization of cut-distance convergence. The main new idea — replacing the infinite family of k-tuples of test functions in the definition of k-shapes by a single fairly distributed function — is natural and well executed. The proof is largely self-contained: Lemmas 1–3 and Proposition 1 are proved in detail, and the author carefully tracks the dependence on prior work. The only non-elementary input is the compactness of s-convergence, imported from Kunszenti-Kovács, Lovász and Szegedy [9, Theorems 4.5 and 4.7]; this dependency is openly acknowledged in the introduction and is not circular, since [9] proves compactness via k-shapes rather than via shapes. There are no free parameters, no fitting, and no signs of circularity. The paper is a solid contribution to graph limit theory.

minor comments (5)

[Section 5, Theorem 1 proof] The step concluding that the identity map from topology (A) to topology (B) is a homeomorphism should explicitly state that topology (B) is Hausdorff. This follows from Corollary 1 together with the fact that the hyperspace of compact subsets of sG is Hausdorff, but the current text leaves this implicit.
[Section 3, Lemma 1] The sentence 'It is enough to prove that Φ(f,µ) ∈ ⋃_{k∈N} ~C(µ,k) for every f ∈ F DC' is slightly imprecise, since the proof actually establishes membership in the closure of the union; the statement should be rephrased accordingly.
[Introduction and abstract] The name 'Rozhoˇv' in the abstract appears to be a typo for 'Rozhoň', as spelled in reference [6].
[Section 5, compactness proof] The compactness argument uses sequential convergence of graphs and s-graphons; it would be helpful to note explicitly that topology (A) is metrizable, as a subspace of the compact metrizable product of hyperspaces, so that sequential convergence suffices for continuity. Currently this is implicit.
[Section 1, limitation statement] The paper's own acknowledgment that it does not give a self-contained proof of the compactness of s-convergence is accurate: the proof of (2)⇒(1) in Theorem 1 relies on [9, Theorems 4.5 and 4.7]. This external dependency is acceptable and is correctly described in the manuscript, but readers should be aware of it.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the shape characterization is a new equivalent formulation, and the only external dependence (compactness from Kunszenti-Kovács–Lovász–Szegedy) is acknowledged and does not assume the theorem.

full rationale

The paper's core derivation is not circular. Lemma 1 and Lemma 2 prove, rather than assume, the relationship between the new shape C(µ) and the old k-shapes C(µ,k): Lemma 1 shows C(µ) is the closure of the union of the embedded k-shapes, and Lemma 2 shows the embedded k-shapes are recovered by intersecting the shape with the appropriate matrix block. Thus the shape is not defined as the closure of k-shapes; the encoding is a proved structural fact. Lemma 3 then provides the uniform finite-K approximation that makes the implication (1)⇒(2) work by a triangle inequality. The converse direction (2)⇒(1) uses compactness of the k-shape topology, which the paper explicitly imports from [9, Theorems 4.5 and 4.7] and explicitly flags as not self-contained: 'the results of this paper do not give a self-contained proof of the compactness of s-convergence. Moreover, we rely on this compactness (proved by means of k-shapes in [9]) in the proof of the implication (2) ⇒ (1) in Theorem 1.' This is a genuine external dependence, but it is not circular: [9] proves compactness via k-shapes, not via the new shapes, so the equivalence stated in Theorem 1 is not being fed back into itself. The only self-citation, to Doležal–Grebík–Hladký–Rocha–Rozhoň [6], is used solely as an analogy about envelopes and is not load-bearing for any proof step. There are no fitted parameters, no prediction from fitted data, and no uniqueness assertion imported from the author's own prior work to force the conclusion.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The central claim rests on standard measure-theoretic and hyperspace facts plus two external theorems from the prior s-graphon literature. No free parameters are fitted and no ad hoc entities are introduced. The most load-bearing external input is the compactness of s-convergence, which the paper openly says it does not reprove.

assumptions (6)

standard math Weak topology on Borel probability measures on [0,1]^2 is compact and metrizable.
Used to define shapes as compact subsets of sG (Section 2, before Definition 1).
standard math Vietoris topology on the hyperspace of compact subsets of a compact metrizable space is compact and compatible with Hausdorff distance.
Used throughout to interpret convergence of k-shapes and shapes (Section 2).
standard math Weak convergence of probability measures can be characterized by convergence on continuity sets (Kechris Theorem 17.20).
Used in Lemma 2 to approximate μ_M by Φ(f,μ).
standard math Continuous functions on compact [0,1]^2 are uniformly continuous.
Used in Lemma 3 and Proposition 1 to select K and to bound the metric ρ.
domain assumption Every s-graphon is an s-limit of some s-convergent graph sequence, and every graph sequence has an s-convergent subsequence [9, Theorems 4.5 and 4.7].
Load-bearing for compactness of topology (A) in Theorem 1, hence for implication (2)⇒(1); the paper explicitly relies on this.
domain assumption For k-shapes, non-negative Borel test functions can be replaced by continuous ones [9, Lemma 3.1].
Used in the definition of k-shapes and in Lemma 1 to pass from Borel f_i to continuous f_i.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Graph limits: An alternative approach to s-graphons." pith.science (2026). https://pith.science/paper/ODK5ORU4

@misc{pith2026200910635,
  author       = {Pith},
  title        = {Pith review of: Graph limits: An alternative approach to s-graphons},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ODK5ORU4}},
  note         = {Machine review of arXiv:2009.10635}
}

read the original abstract

We show that s-convergence of graph sequences is equivalent to the convergence of certain compact sets, called shapes, of Borel probability measures. This result is analogous to the characterization of graphon convergence (with respect to the cut distance) by the convergence of envelopes, due to Dole\v{z}al, Greb\'{i}k, Hladk\'{y}, Rocha, and Rozho\v{v}.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

12 extracted references · 11 canonical work pages

[6]

Relating the cut distance and the weak* topology for graphons

Martin Doleˇ zal, Jan Greb ´ ık, Jan Hladk´ y, Israel Rocha, and V´ aclav Rozhoˇ n. Relating the cut distance and the weak* topology for graphons. J. Combin. Theory Ser. B , 147:252–298, 2021

work page 2021
[9]

Measures on the square as sparse graph limits

D´ avid Kunszenti-Kov´ acs, L´ aszl´ o Lov´ asz, and Bal´ azs Szegedy. Measures on the square as sparse graph limits. J. Combin. Theory Ser. B , 138:1–40, 2019

work page 2019
[1]

Action convergence of operators and graphs

´Agnes Backhausz and Bal´ azs Szegedy. Action convergence of operators and graphs. arXiv e-prints, page arXiv:1811.00626, November 2018

work page Pith review arXiv 2018
[2]

Recurrence of distribu tional limits of ﬁnite planar graphs

Itai Benjamini and Oded Schramm. Recurrence of distribu tional limits of ﬁnite planar graphs. Electron. J. Probab. , 6:no. 23, 13, 2001

work page 2001
[3]

Sparse graphs: metr ics and random models

B´ ela Bollob´ as and Oliver Riordan. Sparse graphs: metr ics and random models. Random Structures Algorithms, 39(1):1–38, 2011

work page 2011
[4]

Borgs, J

C. Borgs, J. T. Chayes, L. Lov´ asz, V. T. S´ os, and K. Veszt ergombi. Convergent se- quences of dense graphs. I. Subgraph frequencies, metric pr operties and testing. Adv. Math. , 219(6):1801–1851, 2008

work page 2008
[5]

Borgs, J

C. Borgs, J. T. Chayes, L. Lov´ asz, V. T. S´ os, and K. Veszt ergombi. Convergent sequences of dense graphs II. Multiway cuts and statistical physics. Ann. of Math. (2) , 176(1):151–219, 2012

work page 2012
[7]

Limits of locally-globally convergent graph sequences

Hamed Hatami, L´ aszl´ o Lov´ asz, and Bal´ azs Szegedy. Limits of locally-globally convergent graph sequences. Geom. Funct. Anal. , 24(1):269–296, 2014. GRAPH LIMITS: AN ALTERNATIVE APPROACH TO S-GRAPHONS 15

work page 2014

Show all 12 references

[8]

Alexander S. Kechris. Classical descriptive set theory , volume 156 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1995

1995
[10]

Limits of dense graph sequences

L´ aszl´ o Lov´ asz and Bal´ azs Szegedy. Limits of dense graph sequences. J. Combin. Theory Ser. B, 96(6):933–957, 2006

2006
[11]

A uniﬁed approach to structural limits and limits of graphs with bounded tree-depth

Jaroslav Neˇ setˇ ril and Patrice Ossona de Mendez. A uniﬁed approach to structural limits and limits of graphs with bounded tree-depth. Mem. Amer. Math. Soc. , 263(1272):v + 108, 2020

2020
[12]

Regular partitions of graphs

Endre Szemer´ edi. Regular partitions of graphs. In Probl` emes combinatoires et th´ eorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976) , volume 260 of Colloq. Internat. CNRS, pages 399–401. CNRS, Paris, 1978

1976

Pith tools

Reviewed August 27, 2026 · model on record in the stance chip above.

[1] [6]

Relating the cut distance and the weak* topology for graphons

Martin Doleˇ zal, Jan Greb ´ ık, Jan Hladk´ y, Israel Rocha, and V´ aclav Rozhoˇ n. Relating the cut distance and the weak* topology for graphons. J. Combin. Theory Ser. B , 147:252–298, 2021

work page 2021

[2] [9]

Measures on the square as sparse graph limits

D´ avid Kunszenti-Kov´ acs, L´ aszl´ o Lov´ asz, and Bal´ azs Szegedy. Measures on the square as sparse graph limits. J. Combin. Theory Ser. B , 138:1–40, 2019

work page 2019

[3] [1]

Action convergence of operators and graphs

´Agnes Backhausz and Bal´ azs Szegedy. Action convergence of operators and graphs. arXiv e-prints, page arXiv:1811.00626, November 2018

work page Pith review arXiv 2018

[4] [2]

Recurrence of distribu tional limits of ﬁnite planar graphs

Itai Benjamini and Oded Schramm. Recurrence of distribu tional limits of ﬁnite planar graphs. Electron. J. Probab. , 6:no. 23, 13, 2001

work page 2001

[5] [3]

Sparse graphs: metr ics and random models

B´ ela Bollob´ as and Oliver Riordan. Sparse graphs: metr ics and random models. Random Structures Algorithms, 39(1):1–38, 2011

work page 2011

[6] [4]

Borgs, J

C. Borgs, J. T. Chayes, L. Lov´ asz, V. T. S´ os, and K. Veszt ergombi. Convergent se- quences of dense graphs. I. Subgraph frequencies, metric pr operties and testing. Adv. Math. , 219(6):1801–1851, 2008

work page 2008

[7] [5]

Borgs, J

C. Borgs, J. T. Chayes, L. Lov´ asz, V. T. S´ os, and K. Veszt ergombi. Convergent sequences of dense graphs II. Multiway cuts and statistical physics. Ann. of Math. (2) , 176(1):151–219, 2012

work page 2012

[8] [7]

Limits of locally-globally convergent graph sequences

Hamed Hatami, L´ aszl´ o Lov´ asz, and Bal´ azs Szegedy. Limits of locally-globally convergent graph sequences. Geom. Funct. Anal. , 24(1):269–296, 2014. GRAPH LIMITS: AN ALTERNATIVE APPROACH TO S-GRAPHONS 15

work page 2014