Pith. sign in

REVIEW 1 major objections 4 minor 1 cited by

Sums along the edges of bounded degree graphs

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

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

Pith's one-line read Random d-regular graphs have edge-sum sets of size at least n^{1-2/d} over every abelian group.

desk verdict The main result is real — random d-regular graphs have sum-sets of size n^{1-2/d} for every abelian group — but the proof of Claim 3.3 contains a false lattice-volume assertion that needs a repair before the lower bound is fully rigorous. read the letter →

arxiv 2507.01138 v2 pith:6MQIP2WS submitted 2025-07-01 math.CO

Noga Alon , Itai Benjamini , Georgii Zakharov , Maksim Zhukovskii This is my paper
classification math.CO MSC 05C8005C2505C3511H06
keywords sum-setsrandomregulargraphsabeliangroupsCayleysum-graphslatticesuniversalexpanderboundeddegree
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 asks how few distinct values can appear as sums A(u)+A(v) along the edges of an n-vertex graph, where A injects the vertices into an abelian group. The authors prove that a random d-regular graph is extremely incompressible in this sense: with high probability, every injection into every abelian group produces at least c $n^{{1-2/d}}$ distinct edge sums, for constant d ≥ 3. This lower bound is tight up to a polylogarithmic factor, and it implies that for every ε > 0 there is a regular graph with O(n) edges whose edge-sum set has size at least $n^{{1-ε}}$ over all abelian groups. The result shows that the earlier logarithmic bound for expanders is far from what typical regular graphs achieve.

What carries the argument

The lower-bound proof reduces an arbitrary injection A : V(G) → H to a canonical quotient group Z^k / Span(f_1, ..., f_m), where k is the number of distinct edge sums and each generator f_t has L1 norm at most 3D for a graph of diameter D. Claim 3.3 bounds the number of distinct lattices generated by such vectors by $k^{{C k D log D}}$, which makes a union bound over all groups possible. The matching upper bound is produced by an explicit Cayley sum-graph, built as a modification of a sparse universal graph construction, that contains every n-vertex graph of maximum degree d and whose generating set has size O($n^{{1-2/d}}$ $d^{2}$ (ln n)^{2+4/d}).

What would settle it

For k=2 and D=1, the vector (1,1) spans a rank-1 lattice of volume $\sqrt$(2), violating the paper's assertion that lattice volumes are integers; checking Claim 3.3 computationally for small k and D by counting distinct spans of vectors with L1 norm at most 3D and comparing with $k^{{C k D log D}}$ would settle whether the counting bound holds as stated.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1.1: for a uniformly random d-regular graph G_n on n vertices, the quantity S(G_n), defined as the minimum, over all abelian groups, of the number of distinct edge sums under an injective vertex labeling, satisfies c $n^{{1-2/d}}$ ≤ S(G_n) ≤ $n^{{1-2/d}}$ $ln^{4}$ n with high probability, for every 3 ≤ d ≤ ln n / ln ln n and a universal constant c > 0. In particular, for every ε > 0 there exists a regular graph with O(n) edges whose sum-set has size at least $n^{{1-ε}}$ over every abelian group. The paper also proves a matching upper bound for arbitrary graphs of maximum degree d, and it determines the near-extremal behavior for large d: when d ≫ $ln^{2}$ n, S(G_n) = n(1-o(1)), and more precisely n(1 - C $ln^{2}$ n / d) ≤ S(G_n) ≤ n(1 - c/d).

Load-bearing premise

The lower-bound proof's lattice-counting step assumes that every enlargement of a lattice cuts its volume by at least half, because volumes are asserted to be integers; for lower-dimensional lattices this is false, so the counting step as written has a gap.

Editorial extensions

If this is right

  • For every ε > 0, there is a regular graph with O(n) edges whose edge-sum set has size at least n^{1-ε} over every abelian group.
  • Random d-regular graphs are essentially extremal: among all n-vertex graphs with maximum degree d, they attain the largest possible sum-set up to a polylogarithmic factor, for 3 ≤ d ≤ ln n / ln ln n.
  • For d ≫ ln^2 n, a random d-regular graph has sum-set n(1-o(1)), so almost every possible edge sum can be forced to occur.
  • The lower bound c n^{1-2/d} is matched by the universal upper bound n^{1-2/d}(log n)^4 in the stated range, so no graph with maximum degree d can do much better.
  • The logarithmic barrier for expanders is not the right order for typical regular graphs; random regular graphs exhibit polynomial-sized sum-sets.

Reading between the lines

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

  • The gap in Claim 3.3's volume-counting argument appears repairable by replacing the false assertion that every lattice volume is an integer with the fact that a proper inclusion of equal-rank lattices has integer index at least 2; the stated polynomial bounds would then survive unchanged.
  • The reduction to quotient groups Z^k / Span(f_1, ..., f_m) is a general tool that could apply to other edge-labeling problems where one must rule out all abelian groups at once.
  • The proof suggests that, among bounded-degree graphs, sum-set size may be governed primarily by n^{1-2/d} and by diameter rather than by expansion alone; comparing Ramanujan graphs with random regular graphs of the same degree would test this directly.
  • A computational check of Claim 3.3 for small k and D, counting distinct spans of integer vectors with L1 norm at most 3D, would give a concrete sanity check for the union-bound step.
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.

Referee Report

1 major / 4 minor

Summary. The paper studies, for a graph G and an abelian group H, the minimum size S_H(G) of the set of edge sums A(u)+A(v) over all injections A: V(G) -> H, and the worst-case-over-groups quantity S(G). The main result (Theorem 1.1) states that for a random d-regular graph G_{n,d}, with high probability S(G_n) = Omega(n^{1-2/d}) for every abelian group when 3 <= d <= ln n / ln ln n, and that this is tight up to a polylogarithmic factor; it also determines the asymptotics for larger d, including the near-full regime S(G_n) = n(1-o(1)) for d = omega(ln^2 n). Theorem 1.2 provides a universal Cayley sum-graph with O(n^{1-2/d} d^2 (ln n)^{2+4/d}) edges that contains every n-vertex graph of maximum degree d, and an elementary upper bound S(G) <= n - ceil(n/(2d)) + 1 for all graphs. The lower-bound proof reduces an arbitrary abelian group and injection to a canonical quotient Z^k/Span(f_1,...,f_m) with bounded L1-norm generators (Claim 3.2), then bounds the number of such lattices (Claim 3.3) and combines this with expansion and counting arguments for random regular graphs.

Significance. If the results are correct, they resolve a natural question left open by Alon--Angel--Benjamini--Lubetzky on sum-sets of sparse graphs: random d-regular graphs have polynomially large sum-sets for all abelian groups, in sharp contrast with the logarithmic worst-case for expanders, and the bounds are tight up to polylog factors. The paper also provides an explicit universal Cayley sum-graph construction and a clean second-order term for large d. The proofs are detailed and the main theorems are quantitative and falsifiable; the paper ships explicit constructions (Cayley expanders and universal graphs) and relies on standard external theorems for random regular graph counts, edge-disjoint placement, and the Hajnal--Szemerédi theorem, rather than on any fitted parameters. The central claims are likely correct, but one load-bearing lattice-counting argument in Claim 3.3 contains a flawed sentence that must be repaired before the lower bound can be considered fully justified.

major comments (1)
  1. [Section 3.1, Claim 3.3] The proof of Claim 3.3 relies on the sentence: 'It remains to recall that the volume of any lattice is an integer and that adding any element that changes the lattice reduces the volume by at least half.' Both assertions are false for the lattices considered here, which are rank-r sublattices of Z^k with r possibly less than k: the r-volume is sqrt(det(Gram)) and need not be an integer (e.g., the lattice spanned by (1,1) in Z^2 has volume sqrt(2)), and adding a vector that increases the rank can multiply the volume by a factor up to 3D rather than divide it. Because the bound |F| <= k^{C k D log D} feeds directly into the union bound over canonical groups in the proof of Theorem 3.1, this is a load-bearing gap. The claim is plausibly correct and can be repaired: a proper same-rank extension divides the volume by an integer index at least 2, a rank-increasing step increases the rank by 1 and can be charged against the initial bound Vol(L_r) <= (3D)^r, and every such lattice has volume at least 1; these facts yield the step bound t <= k(2+log D). Please replace the flawed sentence with this corrected volume/index accounting or with an equivalent citation.
minor comments (4)
  1. [Section 3.2] In the displayed chain after the union bound, the factor n!/2^n is not the number of n-cycles on [n]; the correct count is (n-1)!/2. The subsequent sufficient condition (5) uses n^n as an upper bound, so the argument survives if the equality is replaced by an inequality with n^n or by the exact count.
  2. [Section 3.2, Claim 3.5] In the proof of Claim 3.5, the text says 'the number of (d-2)-regular graphs on [n] equals gd(n)' but the displayed asymptotic formula is for g_{d-2}(n); the subscript should be corrected.
  3. [Section 2.2] There is a typo in the phrase 'Nethertheless' in the lattice background subsection; it should read 'Nevertheless'.
  4. [Section 1, Proof strategy] The proof-strategy paragraph repeats the flawed Claim 3.3 assertion ('at every step, we get a lattice with an integer volume, and every step reduces the volume by at least half'); it should be updated in tandem with the corrected Claim 3.3 argument.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the paper's bounds are proved from external random-graph, lattice, and universal-graph results, with no fitted parameter renamed as a prediction.

full rationale

The central lower bound (Theorem 3.1) is derived by a self-contained reduction (Claim 3.2) to quotient groups Z^k/Span(F), followed by a counting bound on lattices (Claim 3.3) and standard counts and probability estimates for random regular graphs, Hamiltonianity, and diameter (Theorem 2.2, Claim 2.1, and couplings from [11,14,15]). None of these inputs is defined in terms of the target quantity S(G), and no parameter is fitted to data and then reported as a prediction. The upper bound (Theorem 1.2) uses the external universal-graph theorem [2] and edge-disjoint placement results [12,26]; although [2] is authored by the first author, it is a published, parameter-free construction with its own stated assumptions, and the present contribution is the new Cayley-sum variant, so this citation is not load-bearing in a circular sense. The substantial weakness in Section 3.1 is the sentence in Claim 3.3 stating that 'the volume of any lattice is an integer' and that every lattice-changing step 'reduces the volume by at least half'; both statements are false for rank-increasing steps and non-full-rank lattices. That is a correctness gap in the proof of the counting bound, not a circular reduction: the desired step count would follow from standard lattice-index facts, namely that a proper same-rank extension divides the volume by an integer index at least 2 and that rank-increasing steps multiply the volume by at most 3D. Since no claim reduces to its own input by construction, the circularity score is 0.

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

The paper introduces no new entities and fits no numerical parameters to data. Universal constants such as c, C, α, β are existential constants chosen sufficiently large in the proofs, not free parameters. The central claim depends on the external theorems listed above as axioms.

assumptions (7)
  • standard math Enumeration of d-regular graphs and edge-avoidance probability (Claim 2.1)
    Used in Section 3.2 to estimate P(C ⊆ G_n) and the number of regular subgraphs; cited to McKay [22,23].
  • domain assumption Diameter bound O(log n / log d) for random d-regular graphs (Theorem 2.2)
    Provides the diameter parameter D needed in Claim 3.2; cited to [8,18,25].
  • standard math Hajnal-Szemeredi equitable partition theorem
    Used in Lemma 4.4 to partition V(G) into sets satisfying the distance requirement.
  • standard math Sauer-Spencer and Catlin edge-disjoint placement theorems
    Used in Section 4.2 to embed G into the complement of a sparse Cayley sum-graph; cited to [12,26].
  • domain assumption Alon-Capalbo decomposition and universal graph construction [2]
    The upper bound in Theorem 1.2 part 1 modifies this construction; the decomposition theorem [2, Theorem 3.1] is imported as a black box.
  • standard math Alon-Roichman Cayley expander construction (Lemma 4.2 from [3])
    Provides the initial Cayley expander Z(p) needed to build the universal Cayley sum-graph.
  • standard math Diaconis-Stroock spectral mixing bound
    Used in Lemma 4.4 to control the probabilities for random walks on Z.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Sums along the edges of bounded degree graphs." pith.science (2026). https://pith.science/paper/6MQIP2WS

@misc{pith2026250701138,
  author       = {Pith},
  title        = {Pith review of: Sums along the edges of bounded degree graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6MQIP2WS}},
  note         = {Machine review of arXiv:2507.01138}
}
abstract

Let $G$ be a graph on $n$ vertices and $(H,+)$ be an abelian group. What is the minimum size ${\sf S}_H(G)$ of the set of all sums $A(u)+A(v)$ over all injections $A:V(G)\to H$? In 2012, the first author, Angel, the second author, and Lubetzky proved that, for expander graphs and $H=\mathbb{Z}$, this minimum is at least $\Omega(\log n)$, and this bound is tight -- there exists a regular expander $G$ with ${\sf S}_{\mathbb{Z}}(G)=O(\log n)$. We prove that, for every constant $d\geq 3$, the random $d$-regular graph $\mathcal{G}_{n,d}$ has significantly larger sum-sets: with high probability, for every abelian group $H$, ${\sf S}_H(\mathcal{G}_{n,d})=\Omega(n^{1-2/d})$. In particular, this proves that, for every $\varepsilon>0$, there exists a regular graph with $O(n)$ edges and with sum-sets of size at least $n^{1-\varepsilon}$, for all abelian groups. The bound ${\sf S}_H(\mathcal{G}_{n,d})=\Omega(n^{1-2/d})$ is tight up to a polylogarithmic factor: We show that, for every $3\leq d\leq \ln n/ \ln \ln n$, there exists an abelian group $H$ such that, for every graph $G$ on $n$ vertices with maximum degree at most $d$, ${\sf S}_H(G) \leq n^{1-2/d}(\log n)^{O(1)}$. We also prove that, for $d\gg\ln^2 n$, with high probability, for every abelian group $H$, ${\sf S}_H(\mathcal{G}_{n,d})=n(1-o(1))$ and determine the second-order term, up to a polylogarithmic factor.

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Universality in random graphs via optimal linking systems: trees and beyond

    math.CO 2026-08 conditional novelty 8.0 of 10

    An absolute constant C suffices for bounded-degree tree universality in G(n, C ln n/n), and cycle-factor universality is optimal up to constants via depth-optimal linking systems.

Reference graph

Works this paper leans on

26 extracted references · 25 canonical work pages · cited by 1 Pith paper

  1. [1]

    N. Alon, O. Angel, I. Benjamini, E. Lubetzky, Sums and products along sparse graphs , Israel Journal of Mathematics, 188 (2012) 353–384

    work page 2012

  2. [2]

    N. Alon, M. Capalbo, Sparse universal graphs for bounded degree graphs , Random Structures and Algorithms, 31 (2007) 123–133

    work page 2007

  3. [3]

    N. Alon, Y. Roichman, Random Cayley graphs and expanders , Random Structures and Algo- rithms, 5 (1994) 271–284

    work page 1994

  4. [4]

    N. Alon, I. Ruzsa, J. Solymosi, Sums, products, and ratios along the edges of a graph , Publi- cacions matematiques 64:1 (2020) 143–155

    work page 2020

  5. [5]

    Barik, D

    S. Barik, D. Kalita, S. Pati, G. Sahoo, Spectra of graphs resulting from various graph operations and products: a survey , Spec. Matrices, 6 (2018) 323–342

    work page 2018

  6. [6]

    Bollob´ as,Random Graphs, second edition, Cambridge University Press, 2001

    B. Bollob´ as,Random Graphs, second edition, Cambridge University Press, 2001. 18

    work page 2001

  7. [7]

    Bollob´ as, W

    B. Bollob´ as, W. Fernandez de la Vega,The diameter of random regular graphs. Combinatorica 2, (1982) 125–134

    work page 1982

  8. [8]

    A. Z. Broder, A. M. Frieze, S. Suen, E. Upfal, Optimal construction of edge-disjoint paths in random graphs, SIAM J. Comput., 28: 2 (1999) 541–573

    work page 1999

Show all 26 references
  1. [9]

    Erd˝ os, E

    P. Erd˝ os, E. Szemer´ edi,On sums and products of integers , Studies in pure mathematics, Birkha¨ user, Basel (1983) 213–218

    1983

  2. [10]

    Galbraith, Mathematics of public key cryptography, Cambridge University Press, 2012

    S. Galbraith, Mathematics of public key cryptography, Cambridge University Press, 2012

    2012

  3. [11]

    Gao, The number of perfect matchings, and the nesting properties, of random regular graphs, Random Structures and Algorithms, 62:4 (2023) 935–955

    P. Gao, The number of perfect matchings, and the nesting properties, of random regular graphs, Random Structures and Algorithms, 62:4 (2023) 935–955

    2023

  4. [12]

    P. A. Catlin, Subgraphs of graphs, I , Discrete Mathematics, 10:2 (1974) 225–233

    1974

  5. [13]

    Diaconis, D

    P. Diaconis, D. Stroock, Geometric bounds for eigenvalues of Markov chains , Annals of Ap- plied Probability, 1 (1991) 36–61

    1991

  6. [14]

    P. Gao, M. Isaev, B. D. McKay, Kim–Vu’s sandwich conjecture is true for d ≫ log4 n, arXiv preprint (2023) arXiv:2011.09449v5

    2023 arXiv

  7. [15]

    P. Gao, M. Isaev, B. D. McKay, Sandwiching random regular graphs between binomial random graphs, arXiv preprint (2022) arXiv:1906.02886

    2022 arXiv

  8. [16]

    Granville, J

    A. Granville, J. Solymosi, Sum-product formulae, in Recent Trends in Combinatorics, IMA Vol. Math. Appl. 159, Springer, Cham (2016) 419–451

    2016

  9. [17]

    Hajnal, E

    A. Hajnal, E. Szemer´ edi, Proof of a conjecture of Erd˝ os, in: Combinatorial Theory and its Applications, Vol. II (P. Erd˝ os, A. R´ enyi, and V. T. S´ os, eds.), Colloq. Math Soc. J. Bolyai 4, North Holland, Amsterdam (1970) 601-–623

    1970

  10. [18]

    Hollom, L

    L. Hollom, L. Lichev, A. Mond, J. Portier, Y. Wang, Monotonicity and decompositions of random regular graphs, arXiv preprint (2025), arXiv:2505.22875

    2025 arXiv

  11. [19]

    Janson, Random regular graphs: Asymptotic distributions and contiguity , Combinatorics, Probability and Computing, 4 (1995) 369–405

    S. Janson, Random regular graphs: Asymptotic distributions and contiguity , Combinatorics, Probability and Computing, 4 (1995) 369–405

    1995

  12. [20]

    Janson, T

    S. Janson, T. Luczak, A. Ruci´ nski,Random graphs, Wiley, 2000

    2000

  13. [21]

    H. W. Lenstra, Jr., Lattices, In Algorithmic number theory: lattices, number fields, curves and cryptography, Vol. 44 of Math. Sci. Res. Inst. Publ., Cambridge Univ. Press, Cambridge (2008) 127–181

    2008

  14. [22]

    B. D. McKay, Asymptotics for symmetric 0-1 matrices with prescribed row sums , Ars Combin. 19A (1985) 15–26

    1985

  15. [23]

    B. D. McKay, Subgraphs of dense random graphs with specified degrees, Combinatorics, Prob- ability and Computing, 20:3 (2011) 413–433

    2011

  16. [24]

    M. S. O. Molloy, H. Robalewska, R. W. Robinson, N. C. Wormald, 1-factorizations of random regular graphs, Random Structures and Algorithms, 10:3 (1997) 305–321. 19

    1997

  17. [25]

    R. W. Robinson, N. C. Wormald, Almost all regular graphs are hamiltonian , Random Struc- tures Algorithms, 5 (1994) 363–374

    1994

  18. [26]

    Sauer, J

    N. Sauer, J. Spencer, Edge disjoint placement of graphs , Journal of Combinatorial Theory, Series B, 25:3 (1978) 295–302. 20

    1978

Pith tools

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