{"id":"f786fab9-0856-43f3-b91f-6993f4d5199c","arxiv_id":"1908.02628","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Random bipartite graphs G(k,n,p) have the normalized matching property with a sharp threshold at p = log n / k, and Thomason pseudorandom bipartite graphs admit the property after deletion of a vanishingly small vertex set.","lead":"This paper finds the exact probability threshold at which a random bipartite graph with parts of sizes k and n satisfies the normalized matching property: p = (log n) / k. It also proves that random-like pseudorandom bipartite graphs can be made to satisfy this property after deleting only a tiny fraction of vertices.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proof of Theorem 1.2 has an algebraic error in Case Y: the displayed bound on M1 is invalid, so the sharp threshold is not proven as written in the bounded n/k regime.","rationale":"The paper's central claim is Theorem 1.2, the sharp threshold for NMP in G(k,n,p). The reader's strongest claim is this theorem, but the reader's weakest assumption was in the pseudorandom part (the unproved asymmetric extension of Thomason's expander-mixing lemma used in Lemma 4.1). A careful reading of the proof of Theorem 1.2 shows a more serious and concrete problem: in Case Y, the chain of inequalities bounding M1 mismatches signs and then makes an algebraic transition that is false when k/n is bounded away from 0. Concretely, the factor (1-p)^{s k(1-s/n)} cannot become exp(+p k(1-s/n)) in the bracket, and even after correcting the sign, the claimed denominator n^{1+epsilon/2} requires k/n <= epsilon log n/(1+epsilon), which fails for k=n. This is not a disagreement with consensus; it is an internal algebraic inconsistency in the proof of the main theorem. The theorem is plausibly true and the error appears fixable by retaining the exact exponential factor and using the lower bound s >= s_min to make the sum o(1), so a reject verdict is too strong. However, as printed, the sharp threshold is not proven, and the authors must rewrite Case Y. The pseudorandom extension of Theorem 1.3 also remains unproved in the text, so the paper needs two repairs: a corrected Case Y estimate and a proof or precise citation for the asymmetric expander-mixing bound. For these reasons the appropriate verdict is CONDITIONAL, consistent with the reader's overall assessment but with a different and more directly load-bearing concern identified.","tokens_in":25819,"tokens_out":37961,"duration_ms":381906,"concrete_test":"Set k=n and fix epsilon in (0,1). Re-derive the Case Y chain with the correct sign for (1-p)^{s k(1-s/n)}: it contributes exp(-p k(1-s/n)) inside the bracket, and with s <= k/(2 log n) this is at most exp(-(1+epsilon) log n + (1+epsilon)k/(2n)). Take s = ceil(12/epsilon) and n large, and check whether the right-hand side claimed in (12), with denominator n^{1+epsilon/2}, is actually an upper bound for the corrected left-hand side. It is not when k=n. Then verify whether the corrected sum, using the exact factor n^{-(1+epsilon)(1-s/n)} and summing from s_min, still yields o(1) for all 1 <= k/n <= log n. If the corrected sum is o(1), the theorem survives with a rewritten estimate; if not, the sharp threshold statement requires a substantially new argument.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"In the proof of Theorem 1.2, Case Y (Section 3) bounds M1, the probability of a small minimal witness T subset of Y. The displayed chain (9)-(13) is not a valid upper bound. From (9), the factor (1-p)^{s k(1-s/n)} is at most exp(-p s k(1-s/n)) = [exp(-p k(1-s/n))]^s. Thus when it is absorbed into a bracket raised to s, it should appear as exp(-p k(1-s/n)). Equation (10) instead has exp(p k(1-s/n)), the reciprocal. Consequently (10) does not follow from (9). Even if this sign error is corrected, the next step still fails: the corrected factor is at most exp(-(1+epsilon) log n + (1+epsilon)k/(2n)) by s <= k/(2 log n), and the passage to the denominator n^{1+epsilon/2} in (12) requires exp((1+epsilon)k/(2n)) <= n^{epsilon/2}, i.e., k/n <= epsilon log n/(1+epsilon). This is false in the regime k about n covered by this case: for k=n the left side is a constant exp((1+epsilon)/2) while the right side grows as n^{epsilon/2}. Hence the displayed proof that M1 = o(1) collapses exactly in the bounded n/k regime, which is one of the two regimes needed for the sharp threshold in Theorem 1.2. The gap is likely repairable by keeping the exact factor n^{-(1+epsilon)(1-s/n)} and using s >= s_min to make the sum o(1), but as printed the central claim is not established. The reader's concern about the unproved asymmetric extension of Thomason's expander-mixing lemma (Theorem 1.3) is also legitimate, but this algebraic error in the random-graph proof is more immediately load-bearing.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the Normalized Matching Property (NMP) in bipartite graphs, where a graph G(X,Y) satisfies NMP if every S⊆X has |N(S)|/|Y| ≥ |S|/|X|. The first main result, Theorem 1.2, establishes that p = log(n)/k is a sharp threshold for NMP in the unbalanced random bipartite graph G(k,n,p) under the assumption k ≤ n ≤ exp(o(k)). The second main result, Theorem 1.4, shows that any sufficiently dense Thomason-pseudorandom bipartite graph is NMP-approximable: after deleting a vanishingly small fraction of vertices, the remaining graph has NMP. The proof of Theorem 1.4 is built around a decomposition of the graph into Euclidean trees, which are recursively defined trees that individually have NMP. The paper also includes an appendix proving robustness of the Thomason pseudorandomness condition under deletion of vertices.","tokens_in":26148,"tokens_out":9417,"duration_ms":106056,"significance":"If the results hold, the paper gives a natural generalization of the Erdős–Rényi perfect-matching threshold to the unbalanced setting, and it provides a new sufficient condition for approximate NMP under a weak, easily checkable pseudorandomness assumption. The Euclidean-tree decomposition is an attractive and apparently new structural tool, and the proof strategy of Theorem 1.4 is modular, with Lemma 4.1 as a black-box that could be adapted to other pseudorandomness notions. The paper does not rely on fitted parameters or circular reasoning; the main arguments use standard external ingredients such as Kleitman's equivalence, Chernoff bounds, and the expander-mixing principle. The central claims are significant, but the written proof of Theorem 1.2 contains a concrete algebraic error, and a key pseudorandomness estimate is asserted without proof; these issues need to be fixed before the results can be considered established.","major_comments":[{"comment":"The displayed estimate of M1 is not valid as written because of a sign error. From (1-p)^{s k(1-s/n)} ≤ exp(-p s k(1-s/n)), the factor entering the bracket in (10) must be exp(-p k(1-s/n)), with a negative sign, not exp(p k(1-s/n)). The subsequent inequalities (11)-(13) use the positive exponent, so the claimed bound M1 = o(1) does not follow from the displayed chain. This is load-bearing because Case Y is one of the two cases needed for the sharp threshold in Theorem 1.2. The error appears repairable: with the corrected negative exponent one obtains exp(-(1+ε) log n + (1+ε)k/(2n)) in the bounded n/k regime, and the factor exp((1+ε)k/(2n)) is O(1) when k = O(n), so the sum over s ≥ s_min can still be made o(1) with a sufficient polynomial decay in n. The authors should rewrite this chain carefully and state explicitly how the bounded n/k regime is handled.","section":"Section 3, Case Y, Eqs. (9)-(14)"},{"comment":"Theorem 1.3 states an asymmetric version of Thomason's expander-mixing lemma for |X|=k ≤ n=|Y| with the error term sqrt(p n a b (1+ε p a)), but the proof is not given and no precise reference for this exact asymmetric statement is supplied. The sentence 'a glance at the proof there immediately tells us that the same proof works in our general setup' is not sufficient, because Lemma 4.1 and hence Theorem 1.4 depend on this estimate in an essential way. The authors should either include a full proof of the asymmetric expander-mixing inequality under the stated codegree hypothesis, or provide a reference that proves exactly this statement with the same hypotheses and error term.","section":"Section 4, after Theorem 1.3"},{"comment":"In the paragraph bounding the probability of a small minimal witness S⊆X, the claim that every U⊆N(S) of size ceil(n/k) has at least two neighbors in S is supported by the displayed inequality 'n/k |S| - ceil(n/k) > |N(S')|'. This inequality has the wrong direction. From |N(S)| < n|S|/k and U⊆N(S) with |U|=ceil(n/k), one gets |N(S')| ≤ |N(S)| - |U| < n|S|/k - ceil(n/k) ≤ n/k (|S|-1), which is the needed contradiction with minimality. The displayed inequality should be corrected, and the argument phrased as a strict inequality in the last step. This is a local but necessary fix in the proof of the main random-graph theorem.","section":"Section 3, Case X, minimal-witness argument"}],"minor_comments":[{"comment":"The proof of Lemma 2.1 is correct but terse; it would help to explicitly state that the second characterization in Theorem 1.1 is symmetric in X and Y when passing to witnesses in G(Y,X).","section":"Section 2, Lemma 2.1"},{"comment":"The definitions of 'spanned by an X q-thrill' and 'admits a T_{l,L}-factor' are used before being formally defined; a sentence clarifying that these mean a spanning subgraph consisting of vertex-disjoint copies would improve readability.","section":"Section 2, Euclidean tree process"},{"comment":"In the small and large cases of Lemma 3.2, the bounds involving binomial coefficients are stated with the convention (N,K) ≤ (eN/K)^K, but the intermediate case uses a different bound; a uniform notational remark would help the reader follow the estimates.","section":"Section 3, Lemma 3.2"},{"comment":"When choosing K and N as multiples of floor(α n), the argument should explicitly note that all inequalities are asymptotic and require k large enough relative to ε; as written, the interval endpoints depend on quantities that may not be integers.","section":"Section 4, Proof of Theorem 1.4 part (b)"},{"comment":"The appendix proves robustness of Thomason pseudorandomness under vertex deletion, but it does not address the asymmetric expander-mixing estimate. Adding a cross-reference to the missing proof of Theorem 1.3 would clarify the logical dependencies.","section":"Appendix"}],"recommendation":"major_revision","confidential_remarks":"The sign error in Section 3 appears to be a genuine typo that breaks the printed proof, but the intended estimate is very likely recoverable, so I do not recommend rejection. The asymmetric expander-mixing lemma is the more serious missing piece: it is the engine of the pseudorandom part, and it must be proved or precisely referenced. I suggest asking the authors to supply a full proof of the asymmetric version, not merely a citation to Thomason's paper, because the codegree hypothesis is asymmetric and the error term has a specific form used later."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a real paper with two genuinely new results, but the proof of Theorem 1.2 has a sign error in Case Y that, as printed, invalidates the bounded n/k regime. The theorem is probably true and the gap looks repairable, but I would not accept the manuscript without seeing the fix.\n\nWhat is new: the sharp threshold log n / k for NMP in G(k,n,p), generalizing the Erdős–Rényi perfect matching threshold to unbalanced bipartite graphs, and the deletion theorem for Thomason pseudorandom graphs with explicit approximation rates. The Euclidean tree decomposition via the GCD algorithm is an elegant idea, and the paper gives credit to the earlier graphic matroid appearance. The random graph proof in the n/k → ∞ case (Lemma 3.2) is detailed and appears sound: the union bound over independent sets is handled carefully, and the intermediate case via Kleitman's equivalence is clean.\n\nThe pseudorandom part is more delicate. Lemma 4.1, the engine of Theorem 1.4, relies on an unproved extension of Thomason's expander-mixing lemma (Theorem 1.3) from equal part sizes to the asymmetric setup with k ≤ n and the relaxed codegree bound. The reader's concern here is legitimate: the paper says \"a glance at the proof\" is enough, but does not give the proof or a precise citation. This should be fixed. The inductive decomposition in Lemma 4.2 also has a few implicit size inequalities; they look minor but deserve spelling out.\n\nNow the load-bearing problem. In Section 3, Case Y, the displayed chain (9)–(13) is not a valid upper bound on M1. From (1−p)^{s k(1−s/n)} ≤ exp(−p k(1−s/n)), the bracket in (10) should contain exp(−p k(1−s/n)); the text has the reciprocal, exp(+p k(1−s/n)). That sign error alone is fatal to the displayed bound. Even with the sign corrected, the passage to (12) as printed still does not work: the factor n^{-(1+ε)} coming from the corrected exponential has to be kept, and one needs s ≥ s_min to make the sum o(1). As written, the proof does not establish the sharp threshold when n/k is bounded, which is one of the two regimes in Theorem 1.2. This is not a cosmetic typo; that displayed algebra is the only thing carrying the regime. I believe the gap is repairable—keeping the exact factor n^{-(1+ε)(1−s/n)} and using s ≥ s_min seems a plausible route—but I would need to see it written out.\n\nWho this is for: probabilists and extremal combinatorists working on thresholds and pseudorandomness. The paper deserves a serious referee, but only after the authors fix the Case Y estimate and either prove or properly cite the asymmetric expander-mixing lemma. I would not cite the threshold theorem in its current form.","headline":"Genuinely new results and a mostly sound random-graph argument, but the proof of the sharp threshold has a load-bearing sign error in Case Y that as printed invalidates the bounded n/k regime.","tokens_in":26719,"tokens_out":7806,"would_cite":false,"duration_ms":78040,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C80","05C70"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that the scaled Hall condition known as the normalized matching property turns on sharply at p = (log n)/k in random bipartite graphs, and that pseudorandom graphs gain it after deleting a negligible fraction of vertices.","keywords":["normalized matching property","sharp threshold","random bipartite graphs","pseudorandom graphs","expander-mixing lemma","Euclidean tree","Hall's condition","vertex decomposition"],"falsifier":"A counterexample to that transfer would settle the question: build any bipartite graph with $|X|=k$, $|Y|=n\\gg k$ where each $x$ has degree at least $pn$ and each pair of $X$-vertices has at most $(1+\\varepsilon)p^2n$ common neighbors, but some $A\\subseteq X$ of size about $1/p$ and $B\\subseteq Y$ violate $|e(A,B)-p|A||B||\\le \\sqrt{pn|A||B|(1+\\varepsilon p|A|)}$. If such a graph exists, the bound on leftover vertices in the $q$-thrill lemma fails and the deletion-size conclusion of the pseudorandom theorem does not follow.","tokens_in":25561,"feed_emoji":"🎲","tokens_out":19322,"duration_ms":182586,"temperature":0.7,"pith_summary":"The paper establishes a sharp density threshold for the normalized matching property (NMP) in random bipartite graphs, and shows that pseudorandom bipartite graphs almost have the property. For $G(k,n,p)$ with $k\\le n\\le \\exp(o(k))$, the critical probability is $p=(\\log n)/k$: above it every subset of the $k$-side has proportionally enough neighbors with probability arbitrarily close to 1, and below it an isolated vertex on the $n$-side destroys the property. For pseudorandom graphs with $p\\gg 1/k$, the paper proves that deleting a negligible fraction of vertices leaves a subgraph with NMP, and the proof does this by decomposing almost all vertices into disjoint copies of a Euclidean tree built from the Euclidean algorithm. These results matter because they turn the motivating balance problems—equal row and column sums in star-arrays and equal-frequency labelling in finite fields—into quantitative density statements.","feed_headline":"Normalized matching has a sharp threshold in random graphs","feed_subtitle":"The threshold is p=(log n)/k; above it the scaled Hall condition holds, below it isolated vertices ruin the property.","key_machinery":"The load-bearing object is the Euclidean $(\\ell,L)$-tree $T_{\\ell,L}$, a left-right tree with $\\ell$ left and $L$ right vertices defined recursively: subtract the smaller count from the larger, add a matching of size $\\min(\\ell,L)$ between the two sides, and repeat until only a star remains. These trees have NMP, and so do vertex-disjoint unions of copies of one Euclidean tree. Lemma 4.1 is the engine that produces them in pseudorandom graphs: using the expander-mixing estimate it shows that any large enough equal-ratio pair of vertex sets can be spanned by a $q$-thrill—a vertex-disjoint union of $q$-fans, each a star with one center and $q$ leaves—up to $O(\\varepsilon n)$ leftover vertices. Running this extraction at each step of the Euclidean algorithm gives an almost-factorization of the pseudorandom graph into Euclidean trees, and the leftover vertices are exactly the deleted sets $\\mathrm{Del}_X$ and $\\mathrm{Del}_Y$.","core_discovery":"The central claim is that the normalized matching property has a sharp threshold in random bipartite graphs: for $G(k,n,p)$ with $k\\le n\\le \\exp(o(k))$, the critical probability is $p=(\\log n)/k$. Above $(1+\\varepsilon)$ times this value the graph has NMP with probability at least $1-\\delta$; below $(1-\\varepsilon)$ times it, NMP fails with probability at most $\\delta$, the failure witnessed by an isolated vertex in $Y$. For pseudorandom graphs, the central claim is that if every $x\\in X$ has degree at least $pn$ and every pair of vertices in $X$ has at most $(1+\\varepsilon)p^2n$ common neighbors, and $p\\gg 1/k$, then there are tiny sets $\\mathrm{Del}_X$ and $\\mathrm{Del}_Y$ whose removal leaves a subgraph with NMP; the deletion bounds are $O(\\varepsilon)$ from $X$ and $O(\\sqrt{\\varepsilon})$ from $Y$ when $n\\gg k$, and $O(\\varepsilon^{1/4}\\log(1/\\varepsilon))$ from each side in general. The pseudorandom proof is constructive: it partitions almost all vertices into Euclidean trees, small left-right trees defined recursively by the Euclidean algorithm, and Euclidean trees have NMP by construction.","pith_inferences":["Editorial inference: the threshold proof indicates that above $(1+\\varepsilon)\\log n/k$ the only possible NMP violations come from tiny subsets of $X$ or isolated vertices of $Y$, while medium-sized violations are exponentially rare; this suggests a simpler certificate for NMP in dense-enough random graphs than checking all subsets.","Editorial extension: because Lemma 4.1 is used as a black box, any pseudorandomness notion that supplies a similar discrepancy bound should yield an analogous NMP-approximability theorem; one test is to run the Euclidean-tree process on eigenvalue-based pseudorandom bipartite graphs and compare the required deletion fraction with the paper's bounds.","Editorial question: the asymmetric deletion rates in the $n\\gg k$ case—$O(\\varepsilon)$ from $X$ but $O(\\sqrt{\\varepsilon})$ from $Y$—raise the question of whether that asymmetry is forced; a construction built from isolated vertices shows some asymmetry is natural, but the exact tradeoff is not settled by the paper."],"forward_implications":["For any $k\\le n\\le \\exp(o(k))$, the random bipartite graph $G(k,n,p)$ has NMP with probability at least $1-\\delta$ when $p\\ge (1+\\varepsilon)\\log n/k$, and fails NMP with probability at most $\\delta$ when $p\\le (1-\\varepsilon)\\log n/k$.","Below the threshold the obstruction is concrete: some vertex of $Y$ is isolated, so the normalized Hall condition cannot hold.","Every sufficiently large pseudorandom bipartite graph satisfying the paper's degree and codegree bounds, with $p\\gg 1/k$, is NMP-approximable: deleting $O(\\varepsilon)|X|$ and $O(\\sqrt{\\varepsilon})|Y|$ vertices when $n\\gg k$, or $O(\\varepsilon^{1/4}\\log(1/\\varepsilon))$ from each side in general, leaves a subgraph with NMP.","The surviving subgraph comes with an explicit decomposition into vertex-disjoint Euclidean trees, each of which has NMP, so the decomposition certifies the property.","Approximate versions of the motivating problems—filling a star-array with equal row and column sums, and labelling most elements of a finite field so that labelled pairs land in a prescribed multiplicative subgroup—have affirmative answers for random-like or pseudorandom inputs."],"supporting_citations":[{"why":"Supplies the three equivalent characterizations of NMP—neighborhood ratios, independent-set inequalities, and equal-sum multiplicity functions—that connect NMP to Hall's condition and drive both the random-graph union bound and the Euclidean-tree argument.","marker":"[16]"},{"why":"Supplies the balanced random bipartite perfect-matching sharp threshold at log n/n that Theorem 1.2 generalizes to unequal parts and to the normalized condition.","marker":"[10]"},{"why":"Supplies the pseudorandom expander-mixing estimate (Theorem 1.3) that Lemma 4.1 uses to bound leftover vertices when extracting q-thrills.","marker":"[21]"},{"why":"Supplies the whp minimum-degree facts used to force any minimal NMP witness to be large in the hard regime where n/k is at most logarithmic.","marker":"[5]"},{"why":"Supplies the Chernoff bounds used throughout the threshold proof, in particular to show that medium-sized independent-set violations are exponentially unlikely.","marker":"[15]"},{"why":"Supplies the bound on the number of Euclidean-algorithm steps, which controls the deleted vertex counts in Lemma 4.2 and hence in Theorem 1.4(b).","marker":"[17]"}],"fun_headline_variants":["Random bipartite graphs: sharp threshold for normalized matching","NMP hits sharp threshold at p=(log n)/k","Pseudorandom graphs need only tiny deletions for NMP","Euclidean trees help prove normalized matching","After tiny pruning, pseudorandom graphs match proportionally"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The pseudorandom result rests on assuming that the edge-counting estimate at its core remains valid when the two sides of the bipartite graph have different sizes and only one side's pair overlaps are controlled; the paper says the original proof carries over but does not show it.","fun_headline_variants_meta":{"raw":{"variants":["Random bipartite graphs: sharp threshold for normalized matching","NMP hits sharp threshold at p=(log n)/k","Pseudorandom graphs need only tiny deletions for NMP","Euclidean trees help prove normalized matching","After tiny pruning, pseudorandom graphs match proportionally"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000958,"raw_usage":{"total_tokens":4265,"prompt_tokens":1314,"completion_tokens":2951,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":930,"completion_tokens_details":{"reasoning_tokens":2873}},"tokens_in":930,"tokens_out":2951,"duration_ms":24435,"temperature":1.0,"reasoning_tokens":2873,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:42:16.095490+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A counterexample to that transfer would settle the question: build any bipartite graph with $|X|=k$, $|Y|=n\\gg k$ where each $x$ has degree at least $pn$ and each pair of $X$-vertices has at most $(1+\\varepsilon)p^2n$ common neighbors, but some $A\\subseteq X$ of size about $1/p$ and $B\\subseteq Y$ violate $|e(A,B)-p|A||B||\\le \\sqrt{pn|A||B|(1+\\varepsilon p|A|)}$. If such a graph exists, the bound on leftover vertices in the $q$-thrill lemma fails and the deletion-size conclusion of the pseudorandom theorem does not follow.","supporting_citations":[{"cited_title":"Kleitman, On an extremal property of antichains in partial orders, Combinatorics (eds","cited_arxiv_id":null,"evidence_quote":"Supplies the three equivalent characterizations of NMP—neighborhood ratios, independent-set inequalities, and equal-sum multiplicity functions—that connect NMP to Hall's condition and drive both the random-graph union bound and the Euclidean-tree argument."},{"cited_title":"Erd˝ os, A","cited_arxiv_id":null,"evidence_quote":"Supplies the balanced random bipartite perfect-matching sharp threshold at log n/n that Theorem 1.2 generalizes to unequal parts and to the normalized condition."},{"cited_title":"Thomason, Dense Expanders and Pseudo-Random Bipartite graphs, Discrete Math","cited_arxiv_id":null,"evidence_quote":"Supplies the pseudorandom expander-mixing estimate (Theorem 1.3) that Lemma 4.1 uses to bound leftover vertices when extracting q-thrills."},{"cited_title":"Bollob´ as,Random Graphs, 2nd ed., Cambridge University Press (2001)","cited_arxiv_id":null,"evidence_quote":"Supplies the whp minimum-degree facts used to force any minimal NMP witness to be large in the hard regime where n/k is at most logarithmic."},{"cited_title":"Janson, T","cited_arxiv_id":null,"evidence_quote":"Supplies the Chernoff bounds used throughout the threshold proof, in particular to show that medium-sized independent-set violations are exponentially unlikely."},{"cited_title":"Knuth, The Art of Computer Programming, Vol II: Seminumerical Algorithms , 3rd ed., Addison-Wesley (1998)","cited_arxiv_id":null,"evidence_quote":"Supplies the bound on the number of Euclidean-algorithm steps, which controls the deleted vertex counts in Lemma 4.2 and hence in Theorem 1.4(b)."}],"review_version":1}