{"id":"b5c2dcb6-27d1-4610-a51b-a668b10a11c3","arxiv_id":"2507.15105","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper proves quotient-convergence for sequences of matroid and submodular set functions from finite linear spaces, cut capacities, and cycle matroids near positive graphons, and constructs a dense counterexample for nonpositive limits.","lead":"This paper proves that several natural families of submodular set functions, including rank functions of finite linear spaces and cut capacities, have convergent quotients under the limit theory developed in earlier work. It also proves a surprising convergence theorem for cycle matroids of dense graphs approaching positive graphons, and gives a counterexample showing dense graph convergence alone is not enough.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 5.13 is false as stated: sparse dense-convergent graph sequences can have cut-capacity quotient sets that fail to converge, so the cut-capacity claim needs a density/positive-limit hypothesis.","rationale":"The reader's weakest assumption correctly identifies Theorem 5.13 and its missing density hypothesis as a load-bearing defect. My stress test confirms and strengthens this: the defect is not merely that the limit object κ_W is undefined for the zero graphon; the quotient sets themselves need not converge for a mixed sparse sequence converging to zero. This is a genuine counterexample to the theorem as stated, not just a gap in the proof. I also checked the reader's strongest claim, Theorem 5.2. Its proof appears essentially sound: the edge-coloring construction in Lemma 5.10 omits the case of edges from U_j to the leftover set S, but this is repairable by coloring such edges as f(u,u) for the U-endpoint u, which preserves Claim 5.11 and the rank-increase bound. Thus I do not see a fatal flaw in the cycle matroid result. The normalization error in (3) of the Theorem 5.13 proof is real and is another symptom of the missing density treatment. The verdict should remain CONDITIONAL: the paper needs a revised cut-capacity theorem with explicit density assumptions and corrected proof, but the other main results, especially Theorem 5.2, appear likely correct and fixable.","tokens_in":16789,"tokens_out":39127,"duration_ms":472634,"concrete_test":"Compute, for a path on n vertices and for a disjoint union of n/3 triangles, the maximum value M(G)=max_{X⊆V} κ_G(X). For a path, M=1 (take one bipartition class); for triangles, M=2/3 (each triangle contributes at most 2 crossing edges). Then form the alternating sequence G_n = path if n is odd, triangle union if n is even. A short script enumerating all subsets for n up to, say, 30 will show that Q_2(κ_{G_n}) contains a point at distance at least 1/3 from a point in Q_2(κ_{G_{n+1}}), and the analytic argument above shows this persists for all large n. Since both subsequences converge to the zero graphon, this directly contradicts the assertion of Theorem 5.13 that every dense-convergent graph sequence yields a quotient-convergent sequence of cut capacities.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's strongest claim, Theorem 5.2, is plausibly correct, but the broader central claim that cut-capacity functions quotient-converge for every dense-convergent graph sequence (Theorem 5.13, Section 5.2) is false without an additional hypothesis. The proof already contains a concrete normalization error: in (3), for two graphs on the same m vertices it writes |κ_G1(X)−κ_G2(X)| = (1/m^2)·|e_G1(X,V∖X)−e_G2(X,V∖X)|, but κ_G is defined as e(X,V∖X)/|E|, not divided by m^2. More importantly, the theorem fails for zero-limit graphons. Let G_n be a path on n vertices when n is odd and a disjoint union of n/3 triangles when n is even. Both graph sequences converge to the zero graphon in the dense sense, because their edge densities tend to 0. Yet for k=2, Q_2(κ_{G_n}) tends to [0,1] for the path (all cut values j/(n−1), j=0,…,n−1 are achievable) and to [0,2/3] for the triangle union (each triangle contributes 0 or 2 crossing edges, so values are 2t/n, t=0,…,n/3). The Hausdorff distance between these limiting sets is 1/3, so the alternating sequence is not quotient-convergent. Thus Theorem 5.13 requires at least |E(G_n)|=Ω(n^2), or equivalently a nonzero limit graphon W with ∫W>0 so that κ_W is defined.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":17083,"tokens_out":17702,"duration_ms":195966,"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":[{"comment":"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":"Section 5.2, Theorem 5.13"},{"comment":"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":"Section 5.2, proof of Theorem 5.13, equation (3)"},{"comment":"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.","section":"Section 5.1.2, proof of Lemma 5.10"}],"minor_comments":[{"comment":"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":"Throughout"},{"comment":"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":"Section 5.2, proof of Theorem 5.13"},{"comment":"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.","section":"Section 5.2, Remark 5.14"}],"recommendation":"major_revision","confidential_remarks":"The main concern is the false Theorem 5.13. The counterexample with paths vs. triangle unions is decisive, and the normalization error in (3) confirms that the proof has not addressed this case. The fix is relatively local: add a positive-density/positive-integral hypothesis, correct the normalization in (3), and verify the Azuma bound under that hypothesis. If the authors make these changes, the paper's substantive contributions (especially Theorem 5.2) are likely sound. I would also suggest the authors state in Remark 5.14 that the converse question is only meaningful under a density assumption."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nThe 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.\n\nThe 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.\n\nDespite 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.","headline":"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.","tokens_in":17663,"tokens_out":10581,"would_cite":true,"duration_ms":126496,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05B35","05C80"],"pacs":[],"model":"deepseek-v4-flash","headline":"Dense graph sequences approaching a positive graphon have quotient-convergent cycle matroids, with a universal limit independent of the graphon.","keywords":["submodular setfunction","quotient-convergence","matroid","finite linear space","graphons","cycle matroids","cut capacity","homomorphism densities"],"falsifier":"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.","tokens_in":16575,"feed_emoji":"🧮","tokens_out":10547,"duration_ms":82151,"temperature":0.7,"pith_summary":"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.","feed_headline":"Cycle matroids get a universal limit for dense graphs","feed_subtitle":"Normalized rank quotients stabilize independently of the limit graphon, while cut capacity quotients converge to it.","key_machinery":"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$.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies Azuma's inequality, used to round partitions of the blown-up graph back to partitions of the original graph in the cut-capacity proof.","marker":"[1]"},{"why":"Proves quotient-convergence of cycle matroids in the bounded-degree graphing setting, the dense analogue of which Theorem 5.2 addresses.","marker":"[2]"},{"why":"Foundational companion paper defining quotient-convergence and the existence of limit objects for submodular set functions.","marker":"[3]"},{"why":"Gives uniqueness of graphon limits from moment data, supporting the independence of the cycle-matroid limit on the graphon.","marker":"[4]"},{"why":"Establishes dense graph convergence via cut distance and subgraph densities, providing the graphon framework used throughout.","marker":"[5]"},{"why":"Introduces graph quotient sets and right convergence, directly parallel to the quotient sets $Q_k(\\kappa_G)$ in Section 5.2.","marker":"[6]"},{"why":"Supplies the Matroid Sum Theorem used in Lemma 3.8 to construct disjoint bases of flats.","marker":"[8]"},{"why":"Provides the Counting Lemma, cut-distance results, and graphon convergence theorems used in Lemmas 5.5-5.7 and the proof of Theorem 5.2.","marker":"[9]"},{"why":"Establishes that left-convergent graph sequences have essentially unique graphon limits, a prerequisite for defining the limit in Theorem 5.2 and Theorem 5.13.","marker":"[11]"}],"fun_headline_variants":["Cycle matroid ranks converge to a universal limit","Universal matroid limit from dense graph sequences","Matroid convergence independent of graphon choice","Dense graphs force a single matroid limit","Submodular function limits unify across graphons"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Cycle matroid ranks converge to a universal limit","Universal matroid limit from dense graph sequences","Matroid convergence independent of graphon choice","Dense graphs force a single matroid limit","Submodular function limits unify across graphons"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000272,"raw_usage":{"total_tokens":1559,"prompt_tokens":801,"completion_tokens":758,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":417,"completion_tokens_details":{"reasoning_tokens":688}},"tokens_in":417,"tokens_out":758,"duration_ms":464919,"temperature":1.0,"reasoning_tokens":688,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T15:45:35.668697+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies Azuma's inequality, used to round partitions of the blown-up graph back to partitions of the original graph in the cut-capacity proof."},{"cited_title":"B´ erczi, M","cited_arxiv_id":null,"evidence_quote":"Proves quotient-convergence of cycle matroids in the bounded-degree graphing setting, the dense analogue of which Theorem 5.2 addresses."},{"cited_title":"Quotient-convergence of Submodular Setfunctions","cited_arxiv_id":"2406.08942","evidence_quote":"Foundational companion paper defining quotient-convergence and the existence of limit objects for submodular set functions."},{"cited_title":"Borgs, J","cited_arxiv_id":null,"evidence_quote":"Gives uniqueness of graphon limits from moment data, supporting the independence of the cycle-matroid limit on the graphon."},{"cited_title":"Borgs, J","cited_arxiv_id":null,"evidence_quote":"Establishes dense graph convergence via cut distance and subgraph densities, providing the graphon framework used throughout."},{"cited_title":"Borgs, J","cited_arxiv_id":null,"evidence_quote":"Introduces graph quotient sets and right convergence, directly parallel to the quotient sets $Q_k(\\kappa_G)$ in Section 5.2."},{"cited_title":"Edmonds and D","cited_arxiv_id":null,"evidence_quote":"Supplies the Matroid Sum Theorem used in Lemma 3.8 to construct disjoint bases of flats."},{"cited_title":"Lov´ asz.Large networks and graph limits , volume 60","cited_arxiv_id":null,"evidence_quote":"Provides the Counting Lemma, cut-distance results, and graphon convergence theorems used in Lemmas 5.5-5.7 and the proof of Theorem 5.2."},{"cited_title":"Lov´ asz and B","cited_arxiv_id":null,"evidence_quote":"Establishes that left-convergent graph sequences have essentially unique graphon limits, a prerequisite for defining the limit in Theorem 5.2 and Theorem 5.13."}],"review_version":1}