Pith. sign in

REVIEW 2 major objections 2 minor 42 references

The effect of adding randomly weighted edges

T0 review · 2 major / 2 minor · reviewed 2026-05-24 · grok-4.3

Challenge this review Download PDF Read on arXiv ↗

Pith's one-line read Adding o(n²) random edges to an α-regular graph makes minimum weights for spanning trees, shortest paths, and bipartite matchings equal to the complete-graph values scaled by 1/α.

desk verdict Extends complete-graph min-weight asymptotics to dense regular graphs plus o(n²) random edges with 1/α scaling, but shortest-path claim looks exposed if the base graph can have cuts. read the letter →

arxiv 2004.12986 v6 submitted 2020-04-27 math.CO

Alan Frieze This is my paper
classification math.CO
keywords minimumweightspanningtreesshortestpathsperfectmatchingsrandomedgesregulargraphsgraphaugmentationasymptotics
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 studies the minimum weight of combinatorial structures in a graph formed by taking a dense regular graph of degree αn and adding a small number of random edges. It establishes that for spanning trees, shortest paths, and perfect matchings in pseudo-random bipartite graphs, the minimum weight is the same as in the complete graph but multiplied by the factor 1/α. This matters because it shows the asymptotic behavior of these optimization problems is determined by the dense regular component even after random augmentation. The result applies when edge weights are independent and the number of added edges is o(n²).

What carries the argument

The α^{-1} scaling applied to known minimum-weight estimates from the complete graph.

What would settle it

A calculation or simulation showing that the minimum spanning tree weight in the augmented graph deviates from the scaled complete-graph value by more than a (1+o(1)) factor.

Watch

Extended reading notes

Core claim

We consider a dense regular graph G with degree αn where α>0 is constant. We add m=o(n²) random edges. The edges of the augmented graph G(m) are given independent edge weights X(e). We show that in certain cases, we can obtain the same estimate as is known for the complete graph, but scaled by a factor α^{-1}. We consider spanning trees, shortest paths, perfect matchings in (pseudo-random) bipartite graphs.

Load-bearing premise

The dense regular part of the graph continues to determine the minimum weights without the added random edges introducing qualitatively different bottlenecks.

Editorial extensions

If this is right

  • The minimum spanning tree weight matches the complete-graph minimum scaled by 1/α.
  • Shortest path weights follow the same scaled estimate.
  • Perfect matching weights in the bipartite setting are scaled by 1/α.
  • This holds provided the original graph is regular of degree αn and added edges are random with independent weights.

Reading between the lines

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

  • The scaling suggests that the random edges do not create new minimum bottlenecks in these structures.
  • Similar scaling might apply to other min-weight problems if the base graph remains dominant.
  • Network models with a dense core plus sparse random links would inherit these scaled optima.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 2 minor

Summary. The manuscript considers a dense regular graph G on n vertices with degree αn (α>0 constant), augments it with m=o(n²) uniformly random edges to form G(m), and assigns i.i.d. weights to all edges. It claims that for spanning trees, shortest paths, and perfect matchings in pseudo-random bipartite graphs, the minimum weight in G(m) asymptotically matches the known complete-graph value scaled by α^{-1}.

Significance. If the scaling result holds under suitable conditions on G, the work would usefully extend complete-graph estimates for minimum-weight combinatorial structures to a broader class of dense regular graphs with sparse random perturbations. The approach of leveraging the dense regular part while controlling the effect of the added edges could apply to other optimization problems on perturbed graphs.

major comments (2)
  1. [Abstract / shortest paths] Abstract and the section on shortest paths: the claimed α^{-1} scaling of the complete-graph shortest-path distance does not hold for arbitrary α-regular G. The disjoint union of two K_{n/2} is (α≈1/2)-regular yet disconnected; inter-component shortest paths must traverse one of the m random edges. For i.i.d. uniform[0,1] weights this distance is Θ(m^{-1/3}), which for m=n^{3/2} is n^{-1/2} and differs asymptotically from α^{-1}·Θ((log n)/n). The manuscript requires pseudo-randomness only for the matching case, leaving the shortest-path claim exposed.
  2. [Abstract / spanning trees] Abstract and the section on spanning trees: the same disconnected example has no spanning tree in G itself. Any spanning tree in G(m) must incorporate at least one random edge to connect the components, so its minimum weight is governed by the random edges rather than by an α^{-1} scaling of the complete-graph minimum spanning tree weight. This contradicts the central claim unless additional assumptions (e.g., connectivity or expansion of G) are imposed.
minor comments (2)
  1. [Abstract] The abstract should explicitly list the precise conditions on G (beyond regularity) under which each of the three results is asserted.
  2. Notation for the weight distribution and the precise asymptotic regime for m should be stated uniformly across all three applications.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and for identifying the need for explicit connectivity assumptions in the spanning-tree and shortest-path claims. The counterexamples are valid, and we agree that the α^{-1} scaling requires G to be connected (or to satisfy suitable expansion properties) so that the relevant structures can be realized primarily within the dense regular part. We will revise the abstract, introduction, and the relevant sections to state these assumptions clearly and to restrict the claims to the cases where they hold. The pseudo-randomness condition already present for matchings will be referenced for consistency.

read point-by-point responses

  1. Referee: [Abstract / shortest paths] Abstract and the section on shortest paths: the claimed α^{-1} scaling of the complete-graph shortest-path distance does not hold for arbitrary α-regular G. The disjoint union of two K_{n/2} is (α≈1/2)-regular yet disconnected; inter-component shortest paths must traverse one of the m random edges. For i.i.d. uniform[0,1] weights this distance is Θ(m^{-1/3}), which for m=n^{3/2} is n^{-1/2} and differs asymptotically from α^{-1}·Θ((log n)/n). The manuscript requires pseudo-randomness only for the matching case, leaving the shortest-path claim exposed.

    Authors: We agree with the referee that the scaling fails for disconnected G. The manuscript's phrasing 'in certain cases' was intended to cover graphs where the dense part already supports short paths, but connectivity was not stated explicitly. We will add the assumption that G is connected (or an expander) in the abstract and shortest-paths section, and we will note that under this condition the minimum-weight shortest paths continue to be governed by the αn-regular edges, yielding the claimed α^{-1} scaling. The added random edges then contribute only lower-order effects. revision: yes

  2. Referee: [Abstract / spanning trees] Abstract and the section on spanning trees: the same disconnected example has no spanning tree in G itself. Any spanning tree in G(m) must incorporate at least one random edge to connect the components, so its minimum weight is governed by the random edges rather than by an α^{-1} scaling of the complete-graph minimum spanning tree weight. This contradicts the central claim unless additional assumptions (e.g., connectivity or expansion of G) are imposed.

    Authors: The referee's counterexample is correct. Without connectivity of G, spanning trees in G(m) must use at least one random edge, altering the asymptotic weight. We will revise the abstract and spanning-trees section to require that G itself is connected, ensuring that a spanning tree exists entirely within the dense regular graph and that its minimum weight is asymptotically α^{-1} times the complete-graph value. We will also indicate that the result extends to graphs with suitable expansion properties. revision: yes

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity detected; scaling extends external complete-graph results without self-referential reduction

full rationale

The paper states it obtains the same estimate as known for the complete graph, scaled by α^{-1}, for spanning trees, shortest paths, and perfect matchings in pseudo-random bipartite graphs. No equations, fitted parameters, or derivations are shown that reduce this scaling to a self-defined quantity or input by construction. The abstract and description cite external complete-graph estimates as the base, with the scaling presented as an extension rather than a fit or renaming. No self-citation chains or ansatz smuggling are quoted. The derivation chain remains self-contained against external benchmarks.

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

The claim rests on the modeling assumptions stated in the abstract; no free parameters, invented entities, or additional axioms are extractable from the provided text.

assumptions (2)
  • domain assumption G is a dense regular graph of degree αn with α constant
    Stated as the starting graph in the abstract.
  • domain assumption Added edges are chosen randomly and all weights X(e) are independent
    Explicitly part of the model definition.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The effect of adding randomly weighted edges." pith.science (2026). https://pith.science/paper/2004.12986

@misc{pith2026200412986,
  author       = {Pith},
  title        = {Pith review of: The effect of adding randomly weighted edges},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2004.12986}},
  note         = {Machine review of arXiv:2004.12986}
}
abstract

We consider the following question. We have a dense regular graph $G$ with degree $\alpha n$, where $\alpha>0$ is a constant. We add $m=o(n^2)$ random edges. The edges of the augmented graph $G(m)$ are given independent edge weights $X(e)$, $e\in E(G(m))$. We estimate the minimum weight of some specified combinatorial structures. We show that in certain cases, we can obtain the same estimate as is known for the complete graph, but scaled by a factor $\alpha^{-1}$. We consider spanning trees, shortest paths, perfect matchings in (pseudo-random) bipartite graphs.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

42 extracted references · 42 canonical work pages

  1. [1]

    Aigner-Horev and D

    E. Aigner-Horev and D. Hefetz, Rainbow Hamilton cycles in random ly coloured randomly perturbed dense graphs

    work page

  2. [2]

    Aldous, Asymptotics in the random assignment problem, Probability Theory and Related Fields 93 (1992) 507-534

    D. Aldous, Asymptotics in the random assignment problem, Probability Theory and Related Fields 93 (1992) 507-534

    work page 1992

  3. [3]

    Aldous, The ζ(2) limit in the random assignment problem, Random Structures and Algorithms 4 (2001) 381-418

    D. Aldous, The ζ(2) limit in the random assignment problem, Random Structures and Algorithms 4 (2001) 381-418

    work page 2001

  4. [4]

    Anastos and A.M

    M. Anastos and A.M. Frieze, How many randomly colored edges mak e a randomly colored dense graph rainbow Hamiltonian or rainbow connected?, Journal of Graph Theory 92 (2019) 405-414

    work page 2019

  5. [5]

    Balogh, A

    J. Balogh, A. Treglown and A. Wagner, Tilings in randomly perturbe d dense graphs, Combinatorics, Probability and Computing 28 (2019) 159-176

    work page 2019

  6. [6]

    Beveridge, A.M

    A. Beveridge, A.M. Frieze and C. McDiarmid, Random minimum length s panning trees in regular graphs, Combinatorica 18 (1998) 311-333

    work page 1998

  7. [7]

    Bhamidi and R

    S. Bhamidi and R. van der Hofstadt, Weak disorder in the stocha stic mean field model of distance, Annals of Applied Probability 22 (2012) 29-69

    work page 2012

  8. [8]

    Bhamidi, R

    S. Bhamidi, R. van der Hofstadt and G. Hooghiemstra, First pass age percolation on random graphs with finite mean degrees, Annals of Probability 20 (2010) 1907-1965

    work page 2010

Show all 42 references
  1. [9]

    Bedenknecht, J

    W. Bedenknecht, J. Han and Y. Kohayakawa, Powers of tight Ha milton cycles in randomly perturbed hypergraphs, Random Structures and Algorithms 55 (2019) 795-807

    2019

  2. [10]

    Bohman, A.M

    T. Bohman, A.M. Frieze and R. Martin, How many random edges ma ke a dense graph Hamiltonian?, Random Structures and Algorithms 22 (2003) 33-42

    2003

  3. [11]

    Bohman, A.M

    T. Bohman, A.M. Frieze, M. Krivelevich and R. Martin, Adding rand om edges to dense graphs, Random Structures and Algorithms 24 (2004) 105-117

    2004

  4. [12]

    B¨ ottcher, R

    J. B¨ ottcher, R. Montgomery, O. Parczyk and Y. Person, Em bedding spanning bounded degree graphs in randomly perturbed graphs, Electronic Notes in Discrete Mathematics 61 (2017) 155-161. 16

    2017

  5. [13]

    Dadush and S

    D. Dadush and S. Huiberts, A friendly smoothed analysis of the s implex method, Proceedings of STOC 2018

    2018

  6. [14]

    Das and A

    S. Das and A. Treglown, Ramsey properties of randomly pertur bed graphs: cliques and cycles, to appear in Combinatorics, Probability and Computing

  7. [15]

    Dijkstra, A note on two problems in connexion with graphs, Numerische Mathematik 1 (1959) 269-271

    E. Dijkstra, A note on two problems in connexion with graphs, Numerische Mathematik 1 (1959) 269-271

    1959

  8. [16]

    Dudek, C

    A. Dudek, C. Reiher, A. Ruci´ nski and M. Schacht, Powers of Hamiltonian cycles in randomly augmented graphs, Random Structures and Algorithms 56 (2020) 122-141

    2020

  9. [17]

    Fortuin, P.W

    C.M. Fortuin, P.W. Kasteleyn and J. Ginibre, Correlation inequalitie s on some partially ordered sets, Communications in Mathematical Physics 22 (1971) 89-103,

    1971

  10. [18]

    Frieze and T

    A.M. Frieze and T. Johansson, Minimum-cost matching in a random graph with random costs, SIAM Journal on Discrete Mathematics 31 (2017) 489-510

    2017

  11. [19]

    Frieze and M

    A.M. Frieze and M. Karo´ nski, Introduction to Random Graphs, Cambridge University Press, 2015

    2015

  12. [20]

    Frieze, M

    A.M. Frieze, M. Ruszinko and L. Thoma, A note on random minimum le ngth spanning trees, Electronic Journal of Combinatorics 7 (2000)

    2000

  13. [21]

    Han and Y

    J. Han and Y. Zhao, Hamiltonicity in randomly perturbed hypergr aphs, Journal of Combinatorial The- ory, Series B (2020) 14-31

    2020

  14. [22]

    Janson, Poisson approximation for large deviations, Random Structures and Algorithms 1 (1990) 221- 230

    S. Janson, Poisson approximation for large deviations, Random Structures and Algorithms 1 (1990) 221- 230

    1990

  15. [23]

    Janson, One, two and three times log n/n for paths in a complete graph with random weights, Com- binatorics, Probability and Computing 8 (1999) 347-361

    S. Janson, One, two and three times log n/n for paths in a complete graph with random weights, Com- binatorics, Probability and Computing 8 (1999) 347-361

    1999

  16. [24]

    Karp, An upper bound on the expected cost of an optimal a ssignment, Discrete Algorithms and Complexity: Proceedings of the Japan-US Joint Seminar (D

    R.M. Karp, An upper bound on the expected cost of an optimal a ssignment, Discrete Algorithms and Complexity: Proceedings of the Japan-US Joint Seminar (D. J ohnson et al., eds.) , Academic Press, New York, 1987, 1-4

    1987

  17. [25]

    Krivelevich, M

    M. Krivelevich, M. Kwan and B. Sudakov, Cycles and matchings in r andomly perturbed digraphs and hypergraphs, Combinatorics, Probability and Computing 25 (2016) 909-927

    2016

  18. [26]

    Krivelevich, M

    M. Krivelevich, M. Kwan and B. Sudakov, Bounded-degree span ning trees in randomly perturbed graphs,

  19. [27]

    Linusson and J

    S. Linusson and J. W¨ astlund, A proof of Parisi’s conjecture on the random assignment problem, Proba- bility Theory and Related Fields 128 (2004) 419-440

    2004

  20. [28]

    McDowell and R

    A. McDowell and R. Mycroft, Hamilton ℓ-cycles in randomly-perturbed hypergraphs, The electronic journal of combinatorics 25 (2018)

    2018

  21. [29]

    Krivelevich, B

    M. Krivelevich, B. Sudakov and P. Tetali, On smoothed analysis in d ense graphs and formulas, Random Structures and Algorithms 29 (2006) 180-193

    2006

  22. [30]

    C. Nair, B. Prabhakar and M. Sharma, Proofs of the Parisi and Coppersmith-Sorkin random assignment conjectures, Random Structures and Algorithms 27 (2005) 413-444

    2005

  23. [31]

    Parczyk, 2-universality in randomly perturbed graphs, European Journal of Combinatorics 87 (2020) 103-118

    O. Parczyk, 2-universality in randomly perturbed graphs, European Journal of Combinatorics 87 (2020) 103-118

    2020

  24. [32]

    Parisi, A conjecture on Random Bipartite Matching, Physics e -Print archive (1998)

    G. Parisi, A conjecture on Random Bipartite Matching, Physics e -Print archive (1998). 17

    1998

  25. [33]

    Powierski, Ramsey properties of randomly perturbed dense graphs

    E. Powierski, Ramsey properties of randomly perturbed dense graphs

  26. [34]

    Spielman and S

    D. Spielman and S. Teng, Smoothed Analysis of the Simplex Algorith m, Journal of the ACM 51 (2004) 385-463

    2004

  27. [35]

    Sudakov and J

    B. Sudakov and J. Vondrak, How many random edges make a den se hypergraph non-2-colorable?,

  28. [36]

    Thomason, Dense expanders and pseudo-random bipartite graphs, Discrete Mathematics 75 (1989) 381-386

    A. Thomason, Dense expanders and pseudo-random bipartite graphs, Discrete Mathematics 75 (1989) 381-386

    1989

  29. [37]

    Vershynin, Beyond Hirsch Conjecture: Walks on Random Poly topes and Smoothed Complexity of the Simplex Method, SIAM Journal on Computing 39 (2009) 646–678

    R. Vershynin, Beyond Hirsch Conjecture: Walks on Random Poly topes and Smoothed Complexity of the Simplex Method, SIAM Journal on Computing 39 (2009) 646–678

    2009

  30. [38]

    Walkup, On the expected value of a random asignment proble m, SIAM Journal on Computing 8 (1979) 440-442

    D.W. Walkup, On the expected value of a random asignment proble m, SIAM Journal on Computing 8 (1979) 440-442

    1979

  31. [39]

    W¨ astlund, Random matching problems on the complete graph , Electronic Communications in Proba- bility (2008) 258-265

    J. W¨ astlund, Random matching problems on the complete graph , Electronic Communications in Proba- bility (2008) 258-265

    2008

  32. [40]

    W¨ astlund, A simple proof of the Parisi and Coppersmith-Sor kin formulas for the random assignment problem, Link¨ oping Studies in Mathematics6 (2005)

    J. W¨ astlund, A simple proof of the Parisi and Coppersmith-Sor kin formulas for the random assignment problem, Link¨ oping Studies in Mathematics6 (2005)

    2005

  33. [41]

    W¨ astlund, An easy proof of the ζ(2) limit in the random assignment problem, Electronic Communi- cations in Probability 14 (2009) 261-269

    J. W¨ astlund, An easy proof of the ζ(2) limit in the random assignment problem, Electronic Communi- cations in Probability 14 (2009) 261-269

    2009

  34. [42]

    Young, Euler’s constant, Mathematical Gazette 75 (1991) 187-190

    R.M. Young, Euler’s constant, Mathematical Gazette 75 (1991) 187-190. A Proof of final estimate from (38) We use the following expression from Young [42]. n∑ i=1 1 i = log n + γ + 1 2n + O(n− 2), where γ is Euler’s constant. (52) n− r0∑ r=r0 1 r r∑ j=1 1 n − j + 1 n− r0∑ j=r0 1...

    1991

Pith tools

Reviewed May 24, 2026 · model on record in the stance chip above.