{"id":"dbde515e-4a81-4e0f-9798-eca7a8eaf9a5","arxiv_id":"1908.03659","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Whp, the uniform attachment graph Gn,k has a perfect matching for k>=5 and a Hamilton cycle for k>=13, improving prior bounds via new small-set expansion rates.","lead":"This paper proves that a uniform attachment graph, where each new vertex links to k randomly chosen older vertices, almost surely has a perfect matching for k at least 5 and a Hamilton cycle for k at least 13. It drastically improves earlier bounds of k=159 and k=3214 using a new expansion estimate for small vertex sets.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Hamiltonicity proof depends on uncertified numerical roots with very small margins; a tiny error in α2(10), α2(11), or α2(12) would break the chain.","rationale":"The central claim is that uniform attachment graphs are whp Hamiltonian for k ≥ 13 and have perfect matchings for k ≥ 5. The combinatorial machinery — the stochastic-dominance Lemma 3.2, the expansion bounds, and the matching/path lemmas — appears coherent; I did not find a clear counterexample to Lemma 3.2, and its bijective coupling seems plausible. The weakest point I see is the proof of Theorem 2.3 depending quantitatively on uncertified numerical roots with sub-0.001 margins. The reader's conditional verdict is appropriate, but my load-bearing concern is different from the reader's weakest_assumption: I regard Lemma 3.2 as more likely correct and the numerical thresholds as the main vulnerability. The proposed check is cheap, deterministic, and would settle the concern directly.","tokens_in":13109,"tokens_out":43915,"duration_ms":427045,"concrete_test":"Compute the unique roots in (0,1/2) and (0,1/3) of f1(x) = 2(k+1)x + H(2x) − kH(x) = 0 for k = 4 and f2(x) = log2(27/4)(k+1)x + H(3x) − kH(x) = 0 for k = 10, 11, 12, using interval arithmetic or arbitrary-precision root finding (e.g., 50-digit mpmath bisection). Then verify α1(4) > 0.172, α2(10) > 0.2209, α2(11) > 0.2349, and α2(12) > 0.2462. If all certified bounds pass, the numerical-engine concern is resolved; if any fails, Theorem 2.3's proof needs a different constant or a larger k.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The proof of Theorem 2.3 is a numerical chain. H0 = G_{n,10} is shown to have a path of length at least 0.9177n only because 1−(1−0.221)^10 > 0.9177, and each later invocation of Lemma 5.2 uses ζ = α²/2 with α2(10)>0.221, α2(11)>0.235, and α2(12)>0.247. These values are reported as MATLAB computations and are not formally certified. The margins are extremely thin: the final step needs ζ > 1−0.9697 = 0.0303, i.e. α > 0.24617, while the stated lower bound is 0.247, leaving a margin of only about 0.0008 in α. The first step needs α > 0.2209 while using 0.221, a margin near 0.0001. A rounding error at the third decimal place, or a slightly inaccurate root solve, would therefore invalidate the proof of Theorem 2.3 as written, even if the expansion method itself is sound. Since each threshold is the unique root of a one-variable analytic equation, the roots can and should be certified to several extra digits before being relied upon.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":13380,"tokens_out":30773,"duration_ms":287664,"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":[{"comment":"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":"Section 4, proof of Theorem 2.1"},{"comment":"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.","section":"Section 5, proof of Theorem 2.3, with bounds in (3.9)"}],"minor_comments":[{"comment":"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":"Section 3, proof of Corollary 3.5"},{"comment":"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.","section":"Section 4, proof of Theorem 2.1"},{"comment":"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":"Introduction and throughout"},{"comment":"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":"Section 5, proof of Lemma 5.2"},{"comment":"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.","section":"Section 3, Corollary 3.5"}],"recommendation":"major_revision","confidential_remarks":"The two major issues are fixable without changing the central approach. The numerical-bound issue is the more serious: the proof's constants have very thin margins, and the paper should be required to certify the roots of the one-variable equations, e.g., with interval arithmetic, rather than rely on unverified MATLAB output. The Theorem 2.1 statement can be repaired either by weakening the claim to o(n) or by a more careful argument. I believe the main results are likely correct and that the paper will be suitable for publication after these points are addressed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nThis 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.\n\nThe 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.\n\nSecond, 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.\n\nThe 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.","headline":"Solid threshold improvements and a nice least-expansion lemma, but the Hamiltonicity chain rests on unverified numerical roots and Theorem 2.1 overclaims.","tokens_in":13889,"tokens_out":3639,"would_cite":false,"duration_ms":35808,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C80","05C45","05C70","60C05"],"pacs":[],"model":"deepseek-v4-flash","headline":"Almost surely, five random attachments per vertex yield a perfect matching.","keywords":["uniform attachment graph","perfect matching","Hamilton cycle","random graph expansion","stochastic dominance","path rotations","threshold constants","combinatorial probability"],"falsifier":"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.","tokens_in":12880,"feed_emoji":"🔗","tokens_out":7417,"duration_ms":71090,"temperature":0.7,"pith_summary":"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.","feed_headline":"Five random edges per vertex almost surely give a perfect matching","feed_subtitle":"In the same graph model, 13 attachments per vertex force a Hamilton cycle, down from 3214.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the previous sufficient thresholds of 159 and 3214 and the two-stage matching and Hamilton cycle algorithms that this paper modifies.","marker":"[21]"},{"why":"Provides the key lemmas stating that the sets $B(v)$ and the rotation endpoints do not expand, which force these sets to be large in an expander.","marker":"[19]"},{"why":"Introduces the rotation operation on longest paths that underlies the Hamilton cycle argument.","marker":"[26]"},{"why":"Supplies the large-deviation inequality used to bound the probability that too many exposure steps fail.","marker":"[22]"},{"why":"Shows that the analogous $k$-out model is Hamiltonian at $k=3$, providing the comparison that motivates looking for small constant thresholds.","marker":"[4]"}],"fun_headline_variants":["Perfect matching in uniform attachment needs only 5 random edges per vertex","Hamilton cycle in uniform attachment: 13 random edges per vertex suffice","Expansion proof cuts Hamilton cycle threshold to 13 in attachment graphs","Bottleneck set identified: better expansion in uniform attachment models","From 3214 to 13: Hamilton cycle for random attachment graphs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Perfect matching in uniform attachment needs only 5 random edges per vertex","Hamilton cycle in uniform attachment: 13 random edges per vertex suffice","Expansion proof cuts Hamilton cycle threshold to 13 in attachment graphs","Bottleneck set identified: better expansion in uniform attachment models","From 3214 to 13: Hamilton cycle for random attachment graphs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000392,"raw_usage":{"total_tokens":2029,"prompt_tokens":884,"completion_tokens":1145,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":500,"completion_tokens_details":{"reasoning_tokens":1054}},"tokens_in":500,"tokens_out":1145,"duration_ms":10772,"temperature":1.0,"reasoning_tokens":1054,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:11:52.778664+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Frieze, X","cited_arxiv_id":null,"evidence_quote":"Supplies the previous sufficient thresholds of 159 and 3214 and the two-stage matching and Hamilton cycle algorithms that this paper modifies."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the key lemmas stating that the sets $B(v)$ and the rotation endpoints do not expand, which force these sets to be large in an expander."},{"cited_title":"P´ osa,Hamiltonian circuits in random graphs , Discrete Math","cited_arxiv_id":null,"evidence_quote":"Introduces the rotation operation on longest paths that underlies the Hamilton cycle argument."},{"cited_title":"Bohman and A","cited_arxiv_id":null,"evidence_quote":"Shows that the analogous $k$-out model is Hamiltonian at $k=3$, providing the comparison that motivates looking for small constant thresholds."}],"review_version":1}