Convergent sequences of combinatorial submodular setfunctions

Krist\'of B\'erczi; L\'aszl\'o Lov\'asz; L\'aszl\'o M\'arton T\'oth; M\'arton Borb\'enyi

REVIEW 3 major objections 3 minor 11 references

Convergent sequences of combinatorial submodular setfunctions

T0 review · 3 major / 3 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read Dense graph sequences approaching a positive graphon have quotient-convergent cycle matroids, with a universal limit independent of the graphon.

desk verdict A useful but uneven paper: the cycle-matroid universality theorem is likely right, but the cut-capacity theorem is false as stated without a density assumption. read the letter →

arxiv 2507.15105 v1 pith:JG44MC4P submitted 2025-07-20 math.CO

Kristóf Bérczi , Márton Borbényi , László Lovász , László Márton Tóth This is my paper · ORCID

classification math.CO MSC 05B3505C80

keywords submodularsetfunctionquotient-convergencematroidfinitelinearspacegraphonscyclematroidscutcapacityhomomorphismdensities

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

The paper shows that several natural classes of submodular set functions become well-behaved in the limit: normalized rank functions of finite linear spaces over a fixed field are quotient-convergent, and for any dense sequence of graphs converging to a positive graphon, the normalized cycle matroid rank functions are quotient-convergent with a limit that does not depend on the graphon. It also proves that cut capacity functions of dense-convergent graph sequences quotient-converge to the cut capacity of the limit graphon, and that homomorphism-density set functions quotient-converge as well. This matters because it extends the limit theory of dense graphs to matroid-like objects: the finite quotient sets stabilize, so a large graph's cycle matroid or cut structure has a well-defined limiting profile, even when no explicit limit object is described. Some of the proofs, such as the edge-coloring transfer lemma behind the cycle matroid result, are substantial.

What carries the argument

The core object is the $k$-quotient set $Q_k(\varphi)$ of a submodular set function $\varphi$: the collection of all functions on $2^{[k]}$ obtained by pulling $\varphi$ back through a measurable map from the ground set to $[k]$ and normalizing. A sequence is quotient-convergent exactly when these compact sets are Cauchy in Hausdorff distance for every $k$. To reach that conclusion the paper builds on coarser crop sets $T_k(\varphi)$, proves a general criterion (Theorem 3.4) that turns rank-preserving and stretch embeddings between matroid flat lattices into crop-convergence, and then uses the richness condition $R(k,m)$ to upgrade crop-convergence to quotient-convergence via Lemma 3.9, which constructs nearly disjoint bases of flats. For cycle matroids the decisive tool is Lemma 5.10: if $G$ is close to a positive graphon and $H$ is close to any positive graphon, every edge-coloring quotient of $G$ is $\varepsilon$-close to an edge-coloring quotient of $H$. Positivity guarantees that every large vertex subset contains a large complete subgraph, which is what lets the coloring be transferred from $G$ to $H$.

What would settle it

Take a concrete dense sequence converging to a positive graphon, for instance random graphs on $n$ vertices with fixed edge probability $p>0$, and numerically compute the Hausdorff distance between the 2-quotient sets $Q_2(\rho_n)$ and $Q_2(\rho_m)$ of the normalized cycle matroid rank functions for increasing $n,m$. Theorem 5.2 predicts this distance tends to $0$ and that the same limiting set appears for every $p>0$ and for other positive graphons; exhibiting any dense sequence converging to a positive graphon for which the distance does not tend to $0$, or two sequences converging to different positive graphons with different limiting sets, would refute the theorem.

Watch

Extended reading notes

Core claim

The central claim is that quotient-convergence, a notion developed for submodular functions in the companion paper [3], applies to a broad range of combinatorial examples. For a sequence of dense graphs converging to a positive graphon $W$, the normalized cycle matroid rank functions $\rho_n = r_{G_n}/|V(G_n)|$ form a quotient-convergent sequence, and the limit is universal: it does not depend on which positive graphon $W$ is the limit. The mechanism is a two-sided approximation lemma: whenever two dense graphs are close, in cut distance, to positive graphons (possibly different ones), every $\ell$-color quotient of the first graph's cycle matroid can be matched, up to $\varepsilon$, by an $\ell$-color quotient of the second graph's cycle matroid. Consequently, for every fixed $k$, the quotient sets $Q_k(\rho_n)$ form a Cauchy sequence in Hausdorff distance, and the limiting set is the same for all positive graphons. The paper also proves analogous quotient-convergence for cut capacities, for finite linear spaces, and for homomorphism-density submodular functions.

Load-bearing premise

The proof assumes the graph sequence is dense in the sense of having order $n^2$ edges and that the limit graphon is positive almost everywhere; empty graphs make the normalization undefined, and the sparse tree example shows the quotient sets can fail to converge without this density.

Editorial extensions

If this is right

Every dense graph sequence converging to a positive graphon has one well-defined limiting cycle-matroid profile, shared by all such sequences, so rank-based statistics of the cycle matroid stabilize as the graphs grow.
For cut capacities, the limit object is explicit: the quotient sets of the finite graphs converge to the quotient sets of the limiting graphon's cut capacity function.
Finite linear spaces over a fixed finite field yield a quotient-convergent sequence of normalized rank functions, giving a limit object that the paper leaves as an open representation problem.
The general crop-convergence criterion applies to any matroid sequence admitting rank-preserving and stretch embeddings between flats; combined with the richness condition, it gives a reusable route to quotient-convergence beyond the examples worked out.
Homomorphism-density set functions of dense graph sequences quotient-converge to the corresponding graphon-based functions, connecting submodular limits to the standard subgraph-density limit theory.

Reading between the lines

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

The universality in Theorem 5.2 is strong enough to suggest a concrete test: compare the limiting quotient sets for random dense graphs with different edge densities; if they truly coincide, the cycle matroid forgets the edge density entirely, which would be a striking structural feature of dense matroids.
The failure for zero graphons in Example 5.1 indicates that zero sets of the limit graphon control the limit; a natural extension is to characterize which non-positive graphons still yield quotient-convergence and which zero-region geometries break it.
The cut-capacity equivalence in Remark 5.14 implies that proving the node weights of graph quotients are approximately recoverable from the modified edge-weight quotients would turn quotient-convergence of cut capacities into an independent characterization of dense graph convergence.
For finite linear spaces, the limit may be representable by a continuous-geometry analogue over the same field; checking whether the quotient sets of that analogue match the limiting sets $Q_k$ computed from the finite spaces would settle the open problem raised in the paper.

Share X Bluesky LinkedIn Reddit HN

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

The real news here is Theorem 5.2: cycle matroid rank functions of dense graph sequences converging to a positive graphon are quotient-convergent, and the limit is independent of the graphon. That is a genuine, nontrivial result, and the proof via crop-convergence and the coloring lemma is the strongest part of the paper. The counterexample in Example 5.1 also sharpens the boundary nicely. The rest of the paper supplies proofs for results advertised in the authors' earlier [3]: finite linear spaces and cut capacities. Those proofs are useful to have, but the paper is not in final shape.

The cut-capacity theorem, Theorem 5.13, is false as stated. The stress-test example is right: a path and a disjoint union of triangles both dense-converge to the zero graphon, yet the k=2 quotient sets of their normalized cut capacities converge to different limit sets—[0,1] for the path and [0,2/3] for the triangle union. So quotient-convergence fails for zero-limit graphons. The theorem needs an explicit density hypothesis, e.g. |E(G_n)| = Ω(n^2) or a limit graphon W with ∫W > 0. The displayed equality (3) in the proof is also wrong: κ is normalized by |E|, not by m^2, so the claimed bound against labeled cut distance does not follow.

The other gaps are real but fixable. In Theorem 4.1, the assertion that F^n satisfies R(k,2k) for every k is false for q=2 and k≥2. The proof can likely be repaired by taking m = f(k) = O(log k) instead of 2k and invoking Corollary 3.10. Corollary 3.5 has an embedding issue: the hypothesis that M_a ⊕ M_b embeds into M_{a+b} usually means a restriction to a subset, while Theorem 3.4(i) requires restriction to a flat. Example 3.6's edge set is spanning in K_{a+b+1}, so it is not a flat. The corollary needs a stronger hypothesis or a different argument.

Despite these flaws, the paper is worth a serious referee. The main theorem is likely correct, the techniques are reusable, and the counterexample is instructive. I would send it to review, but the referee should be told to focus on Theorem 5.13's missing density assumption and the Corollary 3.5 gap. After those are fixed, the paper should be publishable.

Referee Report

3 major / 3 minor

Summary. The paper develops convergence results for sequences of submodular setfunctions arising from matroids and graphs. It proves quotient-convergence for the normalized rank functions of finite vector spaces over a fixed finite field (Theorem 4.1), for cycle matroids of dense graph sequences converging to a positive graphon (Theorem 5.2), for the normalized cut-capacity functions of dense-convergent graph sequences (Theorem 5.13), and it recalls a result on homomorphism-density setfunctions (Theorem 5.15). The main techniques are crop-convergence, Hausdorff-distance arguments via Lemma 2.1, and approximation lemmas for graphs close to a positive graphon.

Significance. If the issues below are repaired, the paper is a valuable contribution to the limit theory of submodular functions: Theorem 5.2 is a striking universality result, showing that the cycle-matroid quotient limit is independent of the positive graphon limit, and the paper demonstrates that quotient-convergence is a workable framework for several natural combinatorial objects. The proofs are mostly detailed and the paper explicitly builds on the authors' prior framework in [2,3]. However, the false statement of Theorem 5.13 as it stands is a serious defect, and the paper cannot be accepted without a corrected density assumption and a repaired proof.

major comments (3)

[Section 5.2, Theorem 5.13] Theorem 5.13 is false as stated because it lacks a density hypothesis. The alternating sequence with G_n a path on n vertices for odd n and a disjoint union of n/3 triangles for even n is dense-convergent to the zero graphon (both subsequences have edge density O(1/n)), yet Q_2(κ_{G_n}) accumulates on [0,1] along odd n (all cut sizes j/(n−1) are realized) and on [0,2/3] along even n (each triangle contributes 0 or 2 crossing edges), giving Hausdorff distance 1/3 between the two limit sets. Moreover, κ_W is undefined when the denominator ∫∫W is zero, so the asserted approximation by Q_k(κ_W) has no meaning for W=0. The theorem should require |E(G_n)| = Ω(n^2), equivalently a limit graphon W with ∫∫W > 0.
[Section 5.2, proof of Theorem 5.13, equation (3)] Equation (3) is wrong: for two graphs on the same m-vertex set, κ_{G_i}(X) = e_{G_i}(X,V\X)/|E(G_i)|, so the difference is not bounded by (1/m^2)|e_{G_1}-e_{G_2}| unless |E(G_1)|=|E(G_2)|=m^2/2, which is not assumed. The subsequent derivation of (2) therefore does not follow. In the same proof, the Azuma bound in (4) implicitly assumes |E(G)| = Ω(m^2): changing one vertex-class indicator changes κ_{G(n)} by at most deg(u)/|E(G)|, so the stated tail probability 2 exp(−ε^2 m/32) only holds for dense G. These two issues are the technical manifestation of the missing density hypothesis identified in the theorem statement.
[Section 5.1.2, proof of Lemma 5.10] The displayed chain 'ρH'/c' = |V(G')|/|V(H')| · ρH'/c' = n·q/m · ρH'/c'' is self-referential and clearly misprinted; it should read ρ_{H'}/c' = (|V(G')|/|V(H')|) · ρ_{G'}/c' = (nq/m) · ρ_{G'}/c'. The intended inequality following it is correct, so this is a presentation issue rather than a substantive gap, but it should be fixed for readability.

minor comments (3)

[Throughout] There are several typos: 'submdolar' in Section 2.1, 'convergnece' in the Introduction, 'the the theorem' in Section 5.1, and 'ifδ2' missing a space in the proof of Lemma 5.10.
[Section 5.2, proof of Theorem 5.13] In the rounding argument for (4), the final sentence introduces 'a k-partition P'' of V(G)' but then refers to 'a k-partition P'' once more with the same symbol; the last occurrence should be P'' (or a different letter) to avoid confusion.
[Section 5.2, Remark 5.14] Equations (5) and (6) relate κ_G/P to the edge weights γ(ij) = e_G(V_i,V_j)/|V|^2, but κ_G is defined with denominator |E|, so the identities are off by the factor |V|^2/|E|. This does not affect the main proof, but the remark should clarify that the equivalence holds only up to a graph-dependent scaling factor.

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity: the main convergence proofs are derived from definitions and standard graph-limit tools; self-citations to the authors' prior framework are not load-bearing.

full rationale

The paper's central new results, especially Theorem 5.2 (cycle matroid rank functions quotient-converge for dense graph sequences converging to positive graphons), are proved directly from the definitions of quotient-convergence, Lemma 2.1, and standard dense graph limit machinery (cut distance, counting lemma, Azuma's inequality). No fitted parameter is renamed as a prediction. The framework of quotient-convergence is indeed taken from the authors' earlier papers [2] and [3], but the present proofs do not reduce to those papers' conclusions: Lemma 5.10, Lemma 5.8, and the edge-coloring argument supply an independent derivation of the inclusion Q_l(rho_G) subset Q_l(rho_H)^epsilon. The 'limit does not depend on W' part is also derived from that lemma rather than assumed. Theorem 5.13 for cut capacities is essentially a reformulation of known right-convergence, and Remark 5.14 explicitly acknowledges the similarity and the open converse; this is translation of a known result, not a circular derivation. The proof contains a genuine normalization error in equation (3) where kappa is divided by m^2 instead of by |E|, and Theorem 5.13 as stated lacks a density hypothesis for zero-limit graphons; however, these are correctness issues, not circularity. Theorem 5.15 is cited to the authors' prior work [3], but the cited proof uses graph property testing, an external body of results, and no reduction of the theorem to its own input is exhibited. Overall, there is minor self-citation at the foundation but no load-bearing circular step, so the circularity score is 2.

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

The central claims rest on standard external theorems (Matroid Sum Theorem, Azuma, graph limit machinery) and on the authors' own submodular limit framework from [3]. No free parameters or invented entities appear. The main hidden premise is the nondegenerate density assumption for the cut capacity theorem.

assumptions (6)

standard math Matroid Sum Theorem of Edmonds and Fulkerson
Used in the proof of Lemma 3.8 to characterize the rank of a sum of matroids and derive disjoint bases for flats.
standard math Azuma's inequality
Used in the proof of Theorem 5.13 to bound deviations when rounding vertex sets of inflated graphs.
standard math Counting Lemma and cut-distance results from graph limit theory [5],[6],[9],[11]
Used throughout Section 5 to transfer statements about graphons close to graphs into edge-counting statements.
domain assumption The submodular quotient-convergence framework and limit object existence from [3]
The paper assumes the definitions and background theory developed in the authors' earlier preprint, including the existence of limit objects for convergent sequences, which is not reproved here.
domain assumption Positive graphon hypothesis in Theorem 5.2
The theorem is stated only for W(x,y)>0 almost everywhere; the counterexample shows convergence can fail when the limit graphon has zero regions, so this hypothesis is load-bearing.
domain assumption Implicit dense-edge assumption in Theorem 5.13
The theorem and its proof require |E(G_n)|=Theta(n^2) and a limit graphon with positive integral; without this, the normalization by |E| is degenerate and the statement is false or undefined.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Convergent sequences of combinatorial submodular setfunctions." pith.science (2026). https://pith.science/paper/JG44MC4P

@misc{pith2026250715105,
  author       = {Pith},
  title        = {Pith review of: Convergent sequences of combinatorial submodular setfunctions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/JG44MC4P}},
  note         = {Machine review of arXiv:2507.15105}
}

read the original abstract

To illustrate that the notion of convergence of submodular function sequences fits reasonably into the limit theory of graphs, we describe several classes of matroids and other submodular setfunctions for which convergence of appropriate sequences can be proved. Some of the proofs are surprisingly nontrivial.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

11 extracted references · 11 canonical work pages

[3]

Quotient-convergence of Submodular Setfunctions

K. B´ erczi, M. Borb´ enyi, L. Lov´ asz, and L. M. T´ oth. Quotient-convergence of submodular setfunctions. arXiv preprint arXiv:2406.08942 , 2024

work page Pith review arXiv 2024
[1]

K. Azuma. Weighted sums of certain dependent random variables. Tohoku Mathematical Journal, Second Series, 19(3):357–367, 1967

work page 1967
[2]

B´ erczi, M

K. B´ erczi, M. Borb´ enyi, L. Lov´ asz, and L. M. T´ oth. Cycle matroids of graphings: From convergence to duality. arXiv preprint, 2024

work page 2024
[4]

Borgs, J

C. Borgs, J. Chayes, and L. Lov´ asz. Moments of two-variable functions and the uniqueness of graph limits. Geometric and functional analysis , 19:1597–1619, 2010

work page 2010
[5]

Borgs, J

C. Borgs, J. T. Chayes, L. Lov´ asz, V. T. S´ os, and K. Vesztergombi. Convergent sequences of dense graphs I: Subgraph frequencies, metric properties and testing. Advances in Mathematics , 219(6):1801–1851, 2008

work page 2008
[6]

Borgs, J

C. Borgs, J. T. Chayes, L. Lov´ asz, V. T. S´ os, and K. Vesztergombi. Convergent sequences of dense graphs II. Multiway cuts and statistical physics. Annals of Mathematics , pages 151–219, 2012

work page 2012
[7]

G. Choquet. Theory of capacities. In Annales de l’institut Fourier , volume 5, pages 131–295, 1954

work page 1954
[8]

Edmonds and D

J. Edmonds and D. R. Fulkerson. Transversals and matroid partition. Journal of Research of the National Bureau of Standards (B) , 69:147–153, 1965

work page 1965

Show all 11 references

[9]

Lov´ asz.Large networks and graph limits , volume 60

L. Lov´ asz.Large networks and graph limits , volume 60. American Mathematical Society, 2012

2012
[10]

Lov´ asz

L. Lov´ asz. The matroid of a graphing. Journal of Combinatorial Theory, Series B , 169:542–560, 2024

2024
[11]

Lov´ asz and B

L. Lov´ asz and B. Szegedy. Limits of dense graph sequences. Journal of Combinatorial Theory, Series B, 96(6):933–957, 2006. 14

2006

Pith tools

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

[1] [3]

Quotient-convergence of Submodular Setfunctions

K. B´ erczi, M. Borb´ enyi, L. Lov´ asz, and L. M. T´ oth. Quotient-convergence of submodular setfunctions. arXiv preprint arXiv:2406.08942 , 2024

work page Pith review arXiv 2024

[2] [1]

K. Azuma. Weighted sums of certain dependent random variables. Tohoku Mathematical Journal, Second Series, 19(3):357–367, 1967

work page 1967

[3] [2]

B´ erczi, M

K. B´ erczi, M. Borb´ enyi, L. Lov´ asz, and L. M. T´ oth. Cycle matroids of graphings: From convergence to duality. arXiv preprint, 2024

work page 2024

[4] [4]

Borgs, J

C. Borgs, J. Chayes, and L. Lov´ asz. Moments of two-variable functions and the uniqueness of graph limits. Geometric and functional analysis , 19:1597–1619, 2010

work page 2010

[5] [5]

Borgs, J

C. Borgs, J. T. Chayes, L. Lov´ asz, V. T. S´ os, and K. Vesztergombi. Convergent sequences of dense graphs I: Subgraph frequencies, metric properties and testing. Advances in Mathematics , 219(6):1801–1851, 2008

work page 2008

[6] [6]

Borgs, J

C. Borgs, J. T. Chayes, L. Lov´ asz, V. T. S´ os, and K. Vesztergombi. Convergent sequences of dense graphs II. Multiway cuts and statistical physics. Annals of Mathematics , pages 151–219, 2012

work page 2012

[7] [7]

G. Choquet. Theory of capacities. In Annales de l’institut Fourier , volume 5, pages 131–295, 1954

work page 1954

[8] [8]

Edmonds and D

J. Edmonds and D. R. Fulkerson. Transversals and matroid partition. Journal of Research of the National Bureau of Standards (B) , 69:147–153, 1965

work page 1965