arxiv: 2605.10785 · v2 · submitted 2026-05-11 · 🧮 math.CO

Recognition: 2 theorem links

· Lean Theorem

Star observations in bounded-degree graphs

Balazs Szegedy

Authors on Pith no claims yet

Pith reviewed 2026-05-15 05:14 UTC · model grok-4.3

classification 🧮 math.CO

keywords graph limitslocal-global convergencebounded-degree graphscolored starsstar statisticscherry metricgraphings

0 comments

The pith

For bounded-degree graphings, convergence of colored star statistics equals local-global convergence.

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

This paper shows that for graphings of uniformly bounded degree, the topology of local-global convergence is completely determined by the distributions of colored degrees, which are equivalent to colored star statistics. A still simpler sampler called the colored cherry metric, which records only a root and two random neighbors, produces the identical topology. These equivalences mean the full local-global structure of a graphing can be recovered from families of very small colored observations. The result also supplies a key ingredient for unifying action convergence with both sparse and dense graph limit theories.

Core claim

For graphings of uniformly bounded degree, convergence of all colored degree distributions, or equivalently of all colored star statistics, is equivalent to local-global convergence. The colored cherry metric, in which one observes only the root and two randomly chosen neighbours, induces the same topology. Thus the full local-global structure can be reconstructed, at the level of topology, from families of very small colored observations.

What carries the argument

Colored star statistics recording the distribution of stars with colored edges around a randomly sampled root vertex.

If this is right

Local-global convergence can be verified using only the convergence of colored degree distributions.
The colored cherry metric supplies an equivalent and even more economical topology.
The star-observation theorem bridges local-global convergence to action convergence for graphs of any density.
Full local-global structure is recoverable from very small colored observations.

Where Pith is reading between the lines

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

Efficient sampling algorithms for network convergence could be built directly on colored-star or cherry distributions.
Similar minimal-observation equivalences might exist for other limit notions in measurable graph theory.
The result suggests that local-global properties in bounded-degree settings are largely encoded in two-step neighborhood statistics.

Load-bearing premise

The graphs or graphings have uniformly bounded degree, allowing the colored observations to capture the full local-global topology.

What would settle it

A pair of uniformly bounded-degree graphings that agree on all colored star distributions but differ in local-global convergence, or vice versa.

read the original abstract

Similarity metrics are central in the theory of large networks and graph limits. For bounded-degree graphs, the Benjamini--Schramm metric records the distribution of rooted neighbourhoods, while the stronger colored-neighbourhood metric gives rise to local-global convergence. In this paper we show that this intricate topology is already determined by much smaller observations. For technical convenience and greater generality, we work with graphings, which are measurable generalizations of finite graphs and include all finite graphs as special cases. We prove that, for graphings of uniformly bounded degree, convergence of all colored degree distributions, or equivalently of all colored star statistics, is equivalent to local-global convergence. We also introduce an even more economical sampling procedure, the colored cherry metric, in which one observes only the root and two randomly chosen neighbours, and prove that it induces the same topology. Thus the full local-global structure can be reconstructed, at the level of topology, from families of very small colored observations. Our star-observation theorem was previously announced in the work of Backhausz and the author as an important ingredient in the proof that the so-called action convergence unifies dense graph limit theory with local-global convergence, thereby providing a general graph limit theory for sparse, dense, and intermediate-density graphs.

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.

Desk Editor's Note private letter to a colleague

Szegedy proves that colored star statistics and the colored cherry metric both capture local-global convergence for bounded-degree graphings.

read the letter

The main point is that for uniformly bounded-degree graphings, local-global convergence is equivalent to convergence of colored degree distributions, which is the same as convergence of colored star statistics. The paper also shows that the colored cherry metric, which only looks at the root and two random neighbors, induces the same topology. This equivalence was announced earlier but now has a full argument here. The work with graphings keeps the result general while covering finite graphs as a special case. The proof splits cleanly into one direction via marginalization and the converse via measurable selection of colorings to recover the neighborhood distributions. That keeps the logic direct and avoids extra regularity conditions. The bounded-degree hypothesis is used explicitly to ensure local configurations stay finite, which is stated up front. Soft spots are minor. The abstract gives little proof detail, so the measurable selection step needs a close read to confirm it works without hidden choices, though the outline shows no gaps or circularity. No free parameters or invented entities are involved. This paper is for specialists in graph limit theory who already know Benjamini-Schramm and local-global notions and want tighter, cheaper characterizations of convergence. It could help with unification across sparse and dense cases. I would bring it to a reading group to walk through the selection argument. It is worth citing if you work on metrics in this area. It deserves peer review because the central claim is precise and the supporting outline holds up.

Referee Report

0 major / 2 minor

Summary. The manuscript proves that, for graphings of uniformly bounded degree, convergence of all colored degree distributions (equivalently, all colored star statistics) is equivalent to local-global convergence. It further introduces the colored cherry metric, based on sampling only the root and two randomly chosen neighbors, and shows that this metric induces the same topology on the space of such graphings. The results are framed in the measurable setting of graphings to encompass finite graphs and are noted as previously announced in related work on action convergence.

Significance. If the equivalences hold, the result is significant for graph limit theory: it demonstrates that the full local-global topology can be recovered from families of very small colored observations, via direct marginalization in one direction and measurable selection of colorings in the converse. This economical characterization strengthens the unification of sparse and dense graph limits through action convergence, as referenced in the manuscript.

minor comments (2)

Abstract: the prior announcement in the work of Backhausz and the author is mentioned but lacks a specific citation; adding the reference would aid readers tracing the result's history.
The bounded-degree hypothesis is used to ensure finite local configurations suffice, but a brief remark on whether the equivalence extends (even topologically) to unbounded-degree cases would clarify the scope.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful reading, accurate summary, and positive recommendation of minor revision. No specific major comments appear in the report.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The derivation proceeds by direct arguments in the graphing framework: one direction of the equivalence (colored degree/star convergence implies local-global) follows from marginalization of neighborhood distributions, while the converse uses measurable selection of colorings to recover the full local statistics. The colored cherry metric is shown to generate the same topology by explicit comparison of the induced metrics. The uniform bounded-degree hypothesis is stated upfront and used to guarantee that finite colored observations suffice for reconstruction; no parameters are fitted, no ansatz is smuggled via citation, and the prior announcement in Backhausz-Szegedy is referenced only historically without serving as a load-bearing premise. The central claims are therefore self-contained and do not reduce to their own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work relies on standard concepts from graph limit theory such as the Benjamini-Schramm metric and local-global convergence; no free parameters or invented entities are apparent from the abstract.

axioms (1)

domain assumption Graphings serve as measurable generalizations of finite graphs that include all finite graphs as special cases.
Invoked to extend results from finite graphs to a broader measurable setting for technical convenience.

pith-pipeline@v0.9.0 · 5508 in / 1160 out tokens · 53608 ms · 2026-05-15T05:14:41.850470+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Theorem 2.7 (Star theorem): ... convergence of all colored star statistics is equivalent to local-global convergence.
IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Theorem 4.2 (Cherry, star and local-global equivalence)

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages

[1]

Backhausz and B

Á. Backhausz and B. Szegedy, Action convergence of operators and graphs,Canad. J. Math.74(2022), no. 1, 72–121

work page 2022
[2]

Benjamini and O

I. Benjamini and O. Schramm, Recurrence of distributional limits of finite planar graphs,Electron. J. Probab.6(2001), no. 23, 1–13

work page 2001
[3]

Bollobás and O

B. Bollobás and O. Riordan, Sparse graphs: metrics and random models,Random Structures Algorithms39(2011), 1–38

work page 2011
[4]

Elek, Note on limits of finite graphs,Combinatorica27(2007), no

G. Elek, Note on limits of finite graphs,Combinatorica27(2007), no. 4, 503–507

work page 2007
[5]

Hatami, L

H. Hatami, L. Lovász and B. Szegedy, Limits of locally-globally convergent graph sequences,Geom. Funct. Anal.24(2014), no. 1, 269–296

work page 2014
[6]

A. S. Kechris,Classical Descriptive Set Theory, Graduate Texts in Mathematics, vol. 156, Springer, New York, 1995

work page 1995
[7]

A. S. Kechris, S. Solecki and S. Todorcevic, Borel chromatic numbers,Adv. Math.141 (1999), no. 1, 1–44

work page 1999
[8]

Kunszenti-Kovács, L

D. Kunszenti-Kovács, L. Lovász and B. Szegedy, Measures on the square as sparse graph limits,J. Combin. Theory Ser. B138(2019), 1–40

work page 2019
[9]

Levitt, On the cost of generating an equivalence relation,Ergodic Theory Dynam

G. Levitt, On the cost of generating an equivalence relation,Ergodic Theory Dynam. Systems15(1995), no. 6, 1173–1181

work page 1995
[10]

Lovász,Large Networks and Graph Limits, American Mathematical Society, Provid- ence, RI, 2012

L. Lovász,Large Networks and Graph Limits, American Mathematical Society, Provid- ence, RI, 2012

work page 2012
[11]

Lovász and B

L. Lovász and B. Szegedy, Limits of dense graph sequences,J. Combin. Theory Ser. B96(2006), no. 6, 933–957

work page 2006
[12]

Nešetřil and P

J. Nešetřil and P. Ossona de Mendez, Local-global convergence, an analytic and structural approach,Commentationes Mathematicae Universitatis Carolinae60(2019), no. 1, 97–129. Rényi Institute of Mathematics, Budapest, Hungary Email address:szegedyb@gmail.com

work page 2019