Perfect matchings and Hamilton cycles in uniform attachment graphs

Huseyin Acan

REVIEW 2 major objections 5 minor 28 references

Perfect matchings and Hamilton cycles in uniform attachment graphs

T0 review · 2 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read Almost surely, five random attachments per vertex yield a perfect matching.

desk verdict Solid threshold improvements and a nice least-expansion lemma, but the Hamiltonicity chain rests on unverified numerical roots and Theorem 2.1 overclaims. read the letter →

arxiv 1908.03659 v1 pith:RI7LDKWR submitted 2019-08-10 math.CO

Huseyin Acan This is my paper · ORCID

classification math.CO MSC 05C8005C4505C7060C05

keywords uniformattachmentgraphperfectmatchingHamiltoncyclerandomexpansionstochasticdominancepathrotationsthresholdconstantscombinatorialprobability

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

This paper studies the uniform attachment graph, in which each new vertex attaches to $k$ uniformly chosen earlier vertices. It proves that, with probability tending to 1 as $n$ grows, such a graph on $n$ vertices has a perfect matching whenever $k\ge 5$ and a Hamilton cycle whenever $k\ge 13$. These bounds improve the previous sufficient thresholds of $159$ and $3214$ and, because the graph is monotone in $k$, confine the true thresholds to the short intervals $\{2,3,4,5\}$ for matchings and $\{3,\dots,13\}$ for Hamilton cycles. The improvement comes from a sharper expansion analysis of small vertex sets.

What carries the argument

The engine is a stochastic-dominance lemma: among all $\ell$-subsets of vertices, the set $[n-\ell+1,n]$ of the $\ell$ largest vertices maximizes the probability that its neighborhood is small. The proof is a bijective swap of labels $x$ and $x+1$ in the sequence of random choices, which shows that moving a set toward larger labels can only shrink the neighborhood in distribution. This turns a union bound over exponentially many subsets into a single estimate on the largest vertices, and an entropy calculation yields the expansion rates used by both main theorems.

What would settle it

For a fixed small $n$ and $k$, enumerate all possible choice sequences and compute exactly $P(|N(X)|<\ell)$ for $X=\{1,\dots,\ell\}$ and $X=\{n-\ell+1,\dots,n\}$; if the latter probability is not the maximum over all $\ell$-sets, Lemma 3.2 is false and the main theorems lose their engine.

Watch

Extended reading notes

Core claim

The central claim is that $G_{n,k}$ is an $(\alpha,1)$-expander for $k\ge 4$ and an $(\alpha,2)$-expander for $k$ up to $13$, with explicit constants such as $\alpha_1(4)>0.172$ and $\alpha_2(13)>0.257$; that is, every small set $X$ has a neighborhood of size at least $|X|$ (or $2|X|$). The proof identifies the set of the largest vertices as the least likely to expand, so a union bound over all subsets reduces to estimating one worst-case set. These expansion properties are then fed into a two-stage exposure process: first find a matching that leaves few vertices uncovered, or a path that covers a large fraction of vertices, then add the remaining random edges one vertex at a time and show each step is likely to improve the structure until a perfect matching or Hamilton cycle is reached.

Load-bearing premise

The proof depends on the claim that among all vertex sets of a given size, the set of the largest vertices is the least likely to have a small neighborhood; if some smaller-named set were ever less likely to expand, the union bound over all subsets would fail.

Editorial extensions

If this is right

If $k\ge 5$, the graph has a perfect matching with high probability, and for odd $n$ it has a matching that leaves at most one vertex uncovered.
If $k\ge 13$, the graph is Hamiltonian with high probability, and by monotonicity the same holds for every larger $k$.
The known absence of a perfect matching for $k=1$ and of Hamilton cycles for $k=2$ leaves only finitely many open cases: the true thresholds lie in $\{2,3,4,5\}$ and $\{3,\dots,13\}$ respectively.
The expansion estimates for small sets hold for every $k\ge 3$ and can be used directly in any later argument that needs uniform attachment graphs to expand by factor 1 or 2.

Reading between the lines

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

The specific thresholds 5 and 13 are probably not the true ones; the method's bottleneck is numerical evaluation of the expansion constants, so refining those computations could push the Hamiltonicity threshold closer to 3.
The stochastic-dominance lemma may transfer to other age-biased attachment rules, where the oldest vertices are again the least expandable, giving a general recipe for expansion bounds in such models.
A direct simulation of $G_{n,12}$ and $G_{n,13}$ for large $n$ would test whether the declared threshold 13 is tight or merely an artifact of the constants.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

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

Dear colleague,

This paper brings the sufficient k-thresholds for perfect matchings and Hamilton cycles in uniform attachment graphs down from k=159 and k=3214 to 5 and 13. The genuinely new piece is Lemma 3.2: a stochastic-dominance argument showing that the top ℓ vertices [n-ℓ+1,n] are the ℓ-set least likely to have a small neighborhood. The coupling proof is clean, and the resulting expansion estimates are what drive the improvement. The two main theorems look correct. The overall framework—expansion, Pósa rotations, sequential edge exposure—is inherited from Frieze et al., but the specific improvements are real and properly cited.

The soft spots, in order of importance. First, the numerical thresholds α1(4) and α2(10..13) are reported from MATLAB without any certification. This is not cosmetic: the Hamiltonicity proof is a numerical chain with thin margins. The final step needs α > 0.24617 while the stated lower bound is 0.247, a margin of about 0.0008. The first step uses α=0.221 for α2(10), and a drop of 0.0001 would push 1-(1-α)^10 below 0.9177, breaking the long-path claim. Each α is the unique root of a one-variable analytic equation, so this is fixable with interval arithmetic or just slightly safer rounded values. As written, the proof leans on unverified digits.

Second, Theorem 2.1 overclaims. It says Gn,4 has a matching covering all but a bounded number of vertices, but the proof only gives P(κ_n ≥ ω) → 0 for any ω → ∞ slowly—that is o(n) uncovered vertices, not bounded. The weaker statement is all the rest of the paper needs, so this is an easy fix, but the current wording is not what is proven. There are also minor typos (e.g., the duplicated q2 order in Corollary 3.5), but nothing substantive.

The citation pattern is honest, and there is no circularity. The least-expansion lemma is likely to be reused by people working on k-out and related models. This paper deserves a serious referee; the main results are probably correct, but the numerical certification and Theorem 2.1 wording should be addressed before publication.

Referee Report

2 major / 5 minor

Summary. The paper studies the uniform attachment graph G_{n,k}, where each new vertex t makes k independent uniform choices from the earlier vertices. The main results are that, whp, G_{n,4} has a matching covering all but a bounded number of vertices, G_{n,5} has a perfect matching, and G_{n,13} is Hamiltonian, improving previous thresholds of k=159 and k=3214 due to Frieze, P\'erez-Gim\'enez, Pra\l at, and Reiniger. The proof strategy is to establish expansion properties of G_{n,k}: Lemma 3.2 identifies the set of the largest vertices as the one least likely to expand, and Corollary 3.5 derives expansion thresholds \alpha_1(k) and \alpha_2(k) from explicit entropy equations. These are then combined with matching-extension and P\'osa-type path-extension lemmas (Lemma 4.2 and Lemma 5.2) to prove the main theorems.

Significance. If the results are correct, they are a substantial improvement over the prior bounds and place the true thresholds in the narrow ranges {2,...,5} for perfect matchings and {3,...,13} for Hamilton cycles. The stochastic-dominance lemma identifying the worst subset for expansion is a clean and potentially reusable contribution. The paper is largely self-contained, and the central derivations are coherent; the proofs of Theorems 2.2 and 2.3 are built on explicit expansion estimates and standard P\'osa arguments. The main weaknesses are a mismatch between the statement and proof of Theorem 2.1, and the reliance on uncertified numerical root bounds with very small margins in the Hamiltonicity proof.

major comments (2)

[Section 4, proof of Theorem 2.1] Theorem 2.1 as stated claims that whp G_{n,4} has a matching that isolates only a bounded number of vertices, i.e., O(1). The proof, however, establishes only that P(kappa_n >= omega) -> 0 for any integer omega tending to infinity slowly (Eqs. (4.3)-(4.7)). For a fixed constant B, the final bound behaves like O(e^{-cB}) plus a term that does not vanish as n -> infinity, so the stated 'bounded number' conclusion does not follow. This is a load-bearing mismatch: the statement of Theorem 2.1 should be weakened (e.g., to 'o(n) unmatched vertices') or the proof must be strengthened. Since Theorem 2.2 only needs a version with o(n) unmatched vertices (or a sufficiently small gamma n), the main result on perfect matchings can likely be repaired, but the theorem as written is not proven.
[Section 5, proof of Theorem 2.3, with bounds in (3.9)] The proof of Hamiltonicity depends on the numerical lower bounds alpha_2(10)>0.221, alpha_2(11)>0.235, and alpha_2(12)>0.247, which are presented as results of MATLAB computations with no formal certification. The margins are extremely thin: the final step requires alpha_2(12)^2/2 > 1-0.9697 = 0.0303, i.e., alpha_2(12)>0.24617, while the paper uses 0.247, leaving a margin of about 0.0008 in alpha; the first step uses 0.221 when the required threshold is only about 0.2209, a margin near 0.0001. A rounding error at the third decimal place, or a slightly inaccurate root solve, would invalidate the proof of Theorem 2.3 as written. Because these constants are load-bearing, the authors should replace the stated approximations with certified interval-arithmetic bounds, or otherwise provide a rigorous justification that the reported inequalities hold.

minor comments (5)

[Section 3, proof of Corollary 3.5] The notation M is defined twice: first as M := floor(alpha n) and then as M := alpha n. Use a single consistent definition to avoid confusion.
[Section 4, proof of Theorem 2.1] The displayed subevent inequality involving '1 + sum xi_t > n-t+omega/2' appears garbled; the intended statement is likely sum_{t'=t+1}^n xi_{t'} > (n-t+omega)/2. Please rephrase and verify the rounding details.
[Introduction and throughout] Several occurrences of the surname 'Pra\l at' appear as 'Pra/suppress lat' due to a LaTeX/OCR issue. Ensure all author names are rendered correctly.
[Section 5, proof of Lemma 5.2] The proof of Lemma 5.2 is sketched with a reference to the proof of Lemma 4.2, but the case (i) (where a Hamilton cycle, not just a longer path, is obtained) relies on the 'Claim' about adding an edge between an endpoint and END(P,a). I recommend spelling out this final step more explicitly, since Lemma 5.2 is essential for Theorem 2.3.
[Section 3, Corollary 3.5] The proof uses the assertion that the function f(x)=2(k+1)x+H(2x)-kH(x) is negative on (0, alpha_1(k)) and that alpha_1(k) and alpha_2(k) are unique roots in the stated intervals. This should be justified briefly, for example by a monotonicity/sign-change argument, since the expansion sums rely on it.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: expander constants are fixed points of independent entropy equations, and the main theorems follow from direct expansion estimates and borrowed prior-work lemmas.

full rationale

The paper's central claims (Theorems 2.2 and 2.3) are derived from expansion estimates, not from the target properties. Corollary 3.5 defines alpha1(k) and alpha2(k) as unique roots of explicit equations 2(k+1)x+H(2x)-kH(x)=0 and log2(27/4)(k+1)x+H(3x)-kH(x)=0; these constants are computed once from the model's degree-choice distribution and then applied uniformly, so the perfect-matching and Hamiltonicity conclusions are not baked into the definitions. Lemma 3.2 establishes the extremal set by a self-contained coupling/bijection on the choice sequences, and Lemma 3.4 bounds the failure probability directly from the model definition. Lemmas 4.2 and 5.2 are attributed to, and adapted from, Frieze et al. [21], which is ordinary building on prior work, not circular self-citation; Lemmas 4.1 and 5.1 are quoted from the external textbook [19]. The only self-citation, [1] in the introduction, is contextual and not load-bearing. The numerical MATLAB lower bounds in (3.8)-(3.9) are not formally certified and some margins are very thin (e.g., 0.247^2/2 > 1-0.9697 leaves only about 0.0008 in alpha), but this is a correctness/verification risk, not circularity: the claimed results would still not be equivalent to their inputs. No step renames a known result, fits a parameter to a target, or imports a uniqueness theorem from the author's own prior work.

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

The central claim rests on standard probabilistic tools, two cited matching/Pósa lemmas, and numerically computed roots of explicit equations. There are no fitted data parameters and no new postulated entities. The only non-standard input is the MATLAB evaluation of the alpha thresholds, listed as an ad hoc assumption.

assumptions (4)

standard math Standard Chernoff bounds for sums of independent Bernoulli variables (Theorem 4.3, from [22]).
Used in Lemma 4.2, Theorem 2.1, and the Hamilton claims to convert expected success counts into high-probability statements.
standard math Lemma 4.1 ([19, Lemma 6.3]): if G lacks a perfect matching, then for v in A(G), |N(B(v))|<|B(v)|.
The basis for showing that non-expanding sets force large A in Gn,k; cited from the textbook rather than proved.
standard math Lemma 5.1 ([19, Corollary 6.7]): for any longest path P with endpoint a, |N(END(P,a))|<2|END(P,a)|.
The Pósa-rotation tool used to build long paths and Hamilton cycles; cited from the textbook.
ad hoc to paper Numerical evaluation of the roots alpha1(k), alpha2(k) of the entropy equations in Corollary 3.5 is correct to the stated precision.
The inequalities alpha1(4)>0.172, alpha2(12)>0.247, alpha2(13)>0.257 are load-bearing for the specific constants 5 and 13; they are reported from MATLAB without formal certification in the paper.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Perfect matchings and Hamilton cycles in uniform attachment graphs." pith.science (2026). https://pith.science/paper/RI7LDKWR

@misc{pith2026190803659,
  author       = {Pith},
  title        = {Pith review of: Perfect matchings and Hamilton cycles in uniform attachment graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RI7LDKWR}},
  note         = {Machine review of arXiv:1908.03659}
}

abstract

We study Hamilton cycles and perfect matchings in a uniform attachment graph. In this random graph, vertices are added sequentially, and when a vertex $t$ is created, it makes $k$ independent and uniform choices from $\{1,\dots,t-1\}$ and attaches itself to these vertices. Improving the results of Frieze, P\'erez-Gim\'enez, Pra\l{}at and Reiniger (2019), we show that, with probability approaching 1 as $n$ tends to infinity, a uniform attachment graph on $n$ vertices has a perfect matching for $k \ge 5$ and a Hamilton cycle for $k\ge 13$. One of the ingredients in our proofs is the identification of a subset of vertices that is least likely to expand, which provides us with better expansion rates than the existing ones.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

28 extracted references · 26 canonical work pages

[1]

Acan and B

H. Acan and B. Pittel, On connectivity, conductance and bootstrap percolation fo r a random k-out, age-biased graph , Random Structures Algorithms. 2019; 1–26

work page 2019
[2]

Ajtai, J

M. Ajtai, J. Koml´ os, and E. Szemer´ edi,First occurrence of Hamilton cycles in random graphs , Ann. Discrete Math. 27 (1985), 173–178

work page 1985
[3]

Barab´ asi and R

A.L. Barab´ asi and R. Albert, Emergence of scaling in random networks, Science 286 (1999), 509–512. 14

work page 1999
[4]

Bohman and A

T. Bohman and A. M. Frieze, Hamilton cycles in 3-out , Random Structures Algorithms 35 (2009), 393–417

work page 2009
[5]

Bollob´ as,Random Graphs, 2nd Edition Cambridge University Press, Cambridge, 2001

B. Bollob´ as,Random Graphs, 2nd Edition Cambridge University Press, Cambridge, 2001

work page 2001
[6]

Bollob´ as,Almost all regular graphs are Hamiltonian , European J

B. Bollob´ as,Almost all regular graphs are Hamiltonian , European J. Combin. 4 (1983), no. 2, 97–106

work page 1983
[7]

Bollob´ as and A

B. Bollob´ as and A. Frieze, On matchings and Hamiltonian cycles in random graphs , Ann. Discrete Math. 28 (1985) 23–46

work page 1985
[8]

Bollob´ as and A

B. Bollob´ as and A. Thomason,Random graphs of small order , Ann. Discrete Math. 28 (1985) 47–97

work page 1985

Show all 28 references

[9]

Bollob´ as, O

B. Bollob´ as, O. Riordan, J. Spencer, G. Tusn´ ady,The degree sequence of a scale-free random graph process, Random Structures Algorithms 18 (2001), no. 3, 279–290

2001
[10]

Bollob´ as and O

B. Bollob´ as and O. Riordan,The diameter of a scale-free random graph , Combinatorica 4 (1) (2004) 5–34

2004
[11]

Cooper and A.M

C. Cooper and A.M. Frieze, Hamilton cycles in random graphs and directed graphs , Random Structures Algorithms 16 (2000) 369–401

2000
[12]

Erd˝ os and A

P. Erd˝ os and A. R´ enyi,On the evolution of random graphs , Magyar Tud. Akad. Mat. Kutat´ o Int. Kzl. 5 1960, 17–61

1960
[13]

Erd˝ os and A

P. Erd˝ os and A. R´ enyi,On the existence of a factor of degree one of a connected rando m graph, Acta Math. Acad. Sci. Hung. 17 (1966), 359–368

1966
[14]

Fenner and A.M

T. Fenner and A.M. Frieze, On the existence of hamiltonian cycles in a class of random gr aphs, Discrete Mathematics 45 (1983) 301–305

1983
[15]

Fenner and A.M

T. Fenner and A.M. Frieze, Hamiltonian cycles in random regular graphs , J. Combin. Theory Ser. B 37 (1984), no. 2, 103–112

1984
[16]

Frieze, Maximum matchings in a class of random graphs , J

A. Frieze, Maximum matchings in a class of random graphs , J. Combin. Theory Ser. B 40 (1986), no. 2, 196–212

1986
[17]

A. M. Frieze, Finding hamilton cycles in sparse random graphs , J. Combin. Theory Ser. B 44 (1988), no. 2, 230–250

1988
[18]

Frieze, Hamilton Cycles in Random Graphs: a bibliography , preprint, arXiv:1901.07139

A. Frieze, Hamilton Cycles in Random Graphs: a bibliography , preprint, arXiv:1901.07139

1901 arXiv
[19]

A. M. Frieze and M. Kar´ onski, Introduction to Random Graphs , Cambridge University Press (2015)

2015
[20]

A. M. Frieze and T. /suppress Luczak,Hamiltonian cycles in a class of random graphs: one step furt her, Random graphs ’87 (Pozna´ n, 1987), 53–59, Wiley, Chichester, 1990. 15

1987
[21]

Frieze, X

A. Frieze, X. P´ erez-Gim´ enez, P. Pra/suppress lat and B. Reiniger, Perfect matchings and Hamiltonian cycles in the preferential attachment model, Random Structures Algorithms , 54 (2019), no. 2, 258–288

2019
[22]

Janson, T

S. Janson, T. /suppress Luczak and A. Ruci´ nski,Random Graphs, Wiley, New York, 2000

2000
[23]

Koml´ os and E

J. Koml´ os and E. Szemer´ edi,Limit distribution for the existence of Hamilton circuits in a random graph, Discrete Math. 43 (1983), 55–63

1983
[24]

A. D. Korˇ sunov,Solution of a problem of P. Erd˝ os and A. R´ enyi on Hamiltonia n cycles in undirected graphs, Dokl. Akad. Nauk SSSR 228 (1976), no. 3, 529–532

1976
[25]

Magner, S

A. Magner, S. Janson, G. Kollias and W. Szpankowski, On s ymmetry of uniform and prefer- ential attachment graphs, Electron. J. Combin. 21 (2014), Paper 3.32, 24 pp

2014
[26]

P´ osa,Hamiltonian circuits in random graphs , Discrete Math

L. P´ osa,Hamiltonian circuits in random graphs , Discrete Math. 14 (1976), no. 4, 359–364

1976
[27]

R. W. Robinson, and N. C. Wormald, Almost all regular graphs are Hamiltonian , Random Structures Algorithms 5 (1994), no. 2, 363–374

1994
[28]

van der Hofstad, Random graphs and complex networks, Vol

R. van der Hofstad, Random graphs and complex networks, Vol. 1 , Cambridge University Press, Cambridge, 2017. 16

2017

Pith tools

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

[1] [1]

Acan and B

H. Acan and B. Pittel, On connectivity, conductance and bootstrap percolation fo r a random k-out, age-biased graph , Random Structures Algorithms. 2019; 1–26

work page 2019

[2] [2]

Ajtai, J

M. Ajtai, J. Koml´ os, and E. Szemer´ edi,First occurrence of Hamilton cycles in random graphs , Ann. Discrete Math. 27 (1985), 173–178

work page 1985

[3] [3]

Barab´ asi and R

A.L. Barab´ asi and R. Albert, Emergence of scaling in random networks, Science 286 (1999), 509–512. 14

work page 1999

[4] [4]

Bohman and A

T. Bohman and A. M. Frieze, Hamilton cycles in 3-out , Random Structures Algorithms 35 (2009), 393–417

work page 2009

[5] [5]

Bollob´ as,Random Graphs, 2nd Edition Cambridge University Press, Cambridge, 2001

B. Bollob´ as,Random Graphs, 2nd Edition Cambridge University Press, Cambridge, 2001

work page 2001

[6] [6]

Bollob´ as,Almost all regular graphs are Hamiltonian , European J

B. Bollob´ as,Almost all regular graphs are Hamiltonian , European J. Combin. 4 (1983), no. 2, 97–106

work page 1983

[7] [7]

Bollob´ as and A

B. Bollob´ as and A. Frieze, On matchings and Hamiltonian cycles in random graphs , Ann. Discrete Math. 28 (1985) 23–46

work page 1985

[8] [8]

Bollob´ as and A

B. Bollob´ as and A. Thomason,Random graphs of small order , Ann. Discrete Math. 28 (1985) 47–97

work page 1985