{"id":"502a0742-5d68-4656-9018-578b79d027d5","arxiv_id":"2412.20721","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":0.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"A survey of the interlacing families method and the existence proofs it gives for bipartite Ramanujan graphs of all degrees and sizes.","lead":"This paper is a survey that explains the interlacing families method and how it proves the existence of Ramanujan graphs, sparse graphs with maximal spectral gap. It collects the main theorems from the past decade in one place and connects them to random matrices, free probability, and matching polynomials.","discovery_kind":"review","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified.","rationale":"The reader correctly identified the survey's reliance on cited literature as the only plausible weak point. As a stress-tester, I attempted to find a concrete misstatement in the survey's presentation of the main theorems and proof sketches. The derivations appear faithful to the published results: the interlacing theorem is stated correctly, the matching polynomial identities are standard, and the free-convolution argument for Theorem 4.1 checks out. No internally inconsistent step or unsupported claim of new mathematics was found. The survey is a review, so novelty is zero and proofs are legitimately deferred. Therefore, no load-bearing concern exists, and the verdict should remain unchanged.","tokens_in":10845,"tokens_out":14218,"duration_ms":131710,"concrete_test":"Cross-check Theorem 3.5's hypotheses (P1) and (P2) against the original Hall–Puder–Sawin paper [28] to confirm that no condition is omitted or weakened. In particular, verify that (P2) as stated—rho(Gamma) generated by matrices of rank(A−I)=1—matches the exact interlacing condition used in [28]. If the original requires an additional hypothesis (e.g., rho being irreducible or Gamma finite), the survey's summary would be inaccurate.","verdict_should_be":"UNCHANGED","load_bearing_attack":"No load-bearing concern was found. This is an expository survey that asserts no new results; its central claims are the correctness of the cited theorems (Interlacing Families, Godsil–Gutman, Heilmann–Lieb, Hall–Puder–Sawin, and MSS IV) and the validity of the proof sketches connecting them. I checked the plausibility of the main derivations, especially the Walsh-convolution route to Theorem 4.1 and the representation-theoretic conditions in Theorem 3.5. The free convolution of d symmetric Bernoulli measures is indeed the Kesten–McKay law via the R-transform computation, and the monotonicity footnote is consistent with the published results. The only weakness is the survey's reliance on external proofs, which is expected for a survey and does not affect the correctness of the surveyed content. Minor typographical issues, such as 'd = pk + 1' likely meaning 'p^k + 1', do not change the mathematical substance. The reader's weakest assumption—the correctness of the cited literature—is real but not a reason to alter the verdict.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This survey, based on a lecture at the 2024 ICBS, explains the interlacing families method and its applications to the existence of Ramanujan graphs. It covers the spectral definition and Alon–Boppana background, the interlacing families theorem, random covers and signings of fixed graphs (with emphasis on Marcus–Spielman–Srivastava and Hall–Puder–Sawin), the construction of one-sided Ramanujan multigraphs of every size via Walsh and free convolution, and six open questions. The paper claims no new theorems; its contribution is expository, presenting proof sketches and contextualizing the cited literature.","tokens_in":11000,"tokens_out":6205,"duration_ms":62034,"significance":"If the surveyed theorems are correct, this is a valuable authoritative survey: it is written by one of the originators of the interlacing families method and gives a coherent route through a literature that spans spectral graph theory, matching polynomials, representation theory, and free probability. I checked the central statements against my knowledge: Theorem 2.1, Theorem 3.1, Theorem 3.4, and Theorem 4.1 are all stated accurately, and the Walsh-convolution/free-convolution route described in Section 4 is mathematically sound. The survey appropriately outsources full proofs to the original papers; this is normal for a survey and does not undermine the exposition. The presentation of the Hall–Puder–Sawin representation-theoretic framework is especially useful. The paper contains no code or machine-checked artifacts, but none are expected for a survey of this type.","major_comments":[],"minor_comments":[{"comment":"The statement \"Let d = pk + 1\" appears to have a missing superscript: the classical LPS–Margulis condition for these constructions is of the form d = p^k + 1 (or d = q + 1 for q a prime power). As printed, the formula reads as d = p·k + 1, which is not the intended statement.","section":"Theorem 1.4, Section 1.1"},{"comment":"\"Puder [48] proved it up to a multiplicative context\" should read \"up to a multiplicative constant\"; the current phrase is meaningless as printed.","section":"Section 1.2, paragraph on Friedman–Kohler and Puder"},{"comment":"\"a unitary representation of γ\" should be \"a unitary representation of Γ\"; the symbol γ is not defined here.","section":"Section 3.2, paragraph on group signings"},{"comment":"The monotonicity argument mentioned in footnote 6 is essential for passing from the roots of p to the roots of χ[M](z); since it is the only step beyond the cited theorem, a sentence in the main text explaining it would improve readability.","section":"Footnote 6, Section 4"}],"recommendation":"minor_revision","confidential_remarks":"The manuscript is a survey by one of the originators of the method, and its self-citation pattern is appropriate for the occasion; no circularity concern arises. The substantive mathematics is sound as far as I can verify. The recommended revision is purely local: fix the typographical/notation issues listed in the minor comments. After those corrections I would support acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my take. This is a survey, not a research paper. Srivastava claims no new results and proves no new theorems; the content is a synthesis of the interlacing families literature, mostly the author's own earlier papers with Marcus and Spielman plus Hall-Puder-Sawin, Mohanty-O'Donnell, and the recent strong-convergence work. The reader's assessment is correct on all counts: novelty zero, soundness high, circularity not an issue.\n\nWhat the paper does well: it's a clear, accurate map of a decade of work. The structure is sensible—random covers first, then random regular graphs—and the connections are honestly drawn. The Walsh-convolution-to-free-convolution route in Section 4 is nicely explained, and the open questions section is genuinely useful. The author also gives credit where it's due (Friedman, Bordenave, Puder, Huang-McKenzie-Yau, etc.). For a lecture companion, this does its job.\n\nWhere are the soft spots? First, it is a survey, so if you want proofs and new techniques, this isn't the place; every central theorem is deferred to the original papers. That's not a flaw in a survey, but it does mean the paper's value is pedagogical and organizational, not mathematical. Second, there are a few small editing issues: 'multiplicative context' in Section 1.2 should be 'multiplicative constant,' and in Theorem 1.4 'd = pk + 1' should be 'p^k + 1.' Also the sentence 'It is possible Theorem 2.1 generalizes' is a grammatical stumble. None of this affects the math.\n\nThe self-citation point: it's the author's own method, so citing Marcus-Spielman-Srivastava heavily is appropriate, and the cited results are published and peer-reviewed. The reader's weakest assumption—that the cited theorems are correct—is real but unavoidable in any survey; you can't reproduce every proof and still keep it readable. I checked the proof sketches, especially the free convolution part, and they're consistent with the literature.\n\nRecommendation: send it to peer review as an invited survey; it deserves referee time. The right referee should check attributions and the proof sketch in Section 4, not expect new results. I'd bring it to a reading group for people entering the area.","headline":"A solid, honest survey of interlacing families and Ramanujan graphs, with no new results; the value is organizational and pedagogical, and it deserves review as a survey.","tokens_in":11507,"tokens_out":2509,"would_cite":false,"duration_ms":24759,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C50","05C80","46L54"],"pacs":[],"model":"deepseek-v4-flash","headline":"The interlacing-families method proves optimal expanders exist in every degree, the survey argues.","keywords":["Ramanujan graphs","interlacing families","spectral graph theory","expected characteristic polynomials","matching polynomials","random regular graphs","free probability","graph lifts"],"falsifier":"Find a single $d$-regular bipartite graph for which exhaustive search over all signings shows that every signing has spectral norm strictly greater than $2\\sqrt{d-1}$; that would disprove Theorem 3.1 and the survey's central existence claim. For the random regular graph result, compute the second largest root of the expected characteristic polynomial for small $d$ and even $n$; if it ever exceeds $2\\sqrt{d-1}$, the proof chain in Section 4 would be broken.","tokens_in":10619,"feed_emoji":"📈","tokens_out":18092,"duration_ms":157532,"temperature":0.7,"pith_summary":"This survey argues that one technique, interlacing families of polynomials, proves the existence of the best possible sparse expander graphs: for every degree $d$, bipartite $d$-regular Ramanujan graphs exist, and random $d$-regular graphs have positive probability of being one-sided Ramanujan. The technique replaces a random adjacency matrix by its expected characteristic polynomial and shows, through real-rootedness and interlacing, that the roots of that polynomial are attained as eigenvalue bounds by at least one realization. The survey also explains how the same idea extends from 2-lifts to $n$-lifts and to signings by group representations, and how the random-regular case connects to free probability through a polynomial convolution. A sympathetic reader should come away seeing the interlacing-families method as a unified explanation for results that were previously reached by number theory or by high-probability random matrix arguments.","feed_headline":"Optimal expander graphs exist for every degree","feed_subtitle":"By averaging characteristic polynomials, interlacing families guarantee sparse graphs with maximal spectral gap.","key_machinery":"The central object is the expected characteristic polynomial of a random matrix, together with the interlacing family generated by conditioning on the random choices one at a time. An interlacing family is a collection of real-rooted polynomials whose averages remain real-rooted and whose roots bracket the roots of the average, so a root bound on the expected polynomial implies positive probability of the same bound for an individual realization. The load-bearing identities are: the matching-polynomial formula for the expected characteristic polynomial of a random signing; the matching-polynomial root bound of $2\\sqrt{d-1}$ for graphs of maximum degree $d$; and, for random regular graphs, a polynomial-convolution identity that identifies the expected characteristic polynomial (after removing the trivial eigenvalue) with a repeated convolution of a two-point polynomial. The support of the corresponding free convolution of Bernoulli measures is the limiting spectral distribution of random $d$-regular graphs, which lives in $[-2\\sqrt{d-1}, 2\\sqrt{d-1}]$.","core_discovery":"The survey's central claim is that the interlacing families method establishes eigenvalue bounds that were previously out of reach. Concretely, it reports two theorems: every $d$-regular bipartite graph has a signing whose spectral norm is at most $2\\sqrt{d-1}$ (Theorem 3.1), and a random $d$-regular graph on $n$ vertices satisfies $\\mathbb{P}[\\lambda_2(A_G) \\le 2\\sqrt{d-1}] > 0$ (Theorem 4.1). The mechanism, stated as Theorem 2.1, is that for these random matrix models the expected characteristic polynomial $p_A(z) = \\mathbb{E}\\det(zI - A)$ is real-rooted and its $i$-th root $\\lambda_i(p_A)$ satisfies $\\mathbb{P}[\\lambda_i(A) \\le \\lambda_i(p_A)] > 0$, so a root bound on the expectation becomes an existence statement for a single realization. The survey further reports that the same scheme works for $n$-covers of bipartite base graphs and for signings by group representations whose exterior powers are irreducible, and that the needed root bounds come from matching polynomials and from finite and free convolution.","pith_inferences":["The structure of the proof suggests that the main remaining gap, infinite sequences of non-bipartite Ramanujan graphs for all degrees, would close if an interlacing family could be built for non-bipartite base graphs; the survey presents no obstruction, only a missing ingredient.","The positivity conclusion is inherently non-quantitative; any future theorem giving a probability bounded away from zero for random regular graphs would need new tools, because the expected-polynomial method is designed to control one realization rather than the typical one.","The convolution identity used for random regular graphs suggests a testable program: replace the two-point measure with other finitely supported measures and check whether the interlacing root bound still holds, which would give Ramanujan-type spectral guarantees for other structured random matrix models.","One could numerically test the chain in Section 4 on small cases by computing the expected characteristic polynomial of a random $d$-regular graph and verifying that its second root stays at or below $2\\sqrt{d-1}$."],"forward_implications":["Every $d$-regular bipartite graph has a signing, equivalently a 2-lift, whose new eigenvalues all lie in the Ramanujan interval, so iterating the signing step produces infinite families of bipartite Ramanujan graphs for every $d \\ge 3$.","For every $d \\ge 3$ and every even $n$, there exists a $d$-regular multigraph whose second eigenvalue is at most $2\\sqrt{d-1}$; the bipartite version gives a two-sided Ramanujan graph of every such size.","The method yields a positive-probability guarantee rather than a high-probability one: it shows the desired graph exists inside the random model but does not by itself show that a random draw is usually Ramanujan.","The same interlacing framework, with suitable root bounds, extends to $n$-covers of bipartite base graphs and to signings by group representations whose exterior powers are irreducible, and it narrows the original existence question to the non-bipartite case."],"supporting_citations":[{"why":"Proves Theorem 3.1 on signings of every d-regular bipartite graph and introduces the interlacing-families method for 2-covers.","marker":"[40]"},{"why":"Proves Theorem 4.1 on positive probability of one-sided Ramanujan random regular graphs and supplies the convolution identity behind it.","marker":"[42]"},{"why":"Establishes the n-cover analogue and the representation-theoretic signing theorem, and provides part of the proof of Theorem 2.1.","marker":"[28]"},{"why":"Gives the matching-polynomial identity for the expected characteristic polynomial of a random signing.","marker":"[24]"},{"why":"Proves real-rootedness and the $2\\sqrt{d-1}$ root bound for matching polynomials of maximum degree $d$.","marker":"[29]"},{"why":"Develops finite free convolutions and proves the relation between the polynomial convolution and free convolution used in Theorem 4.2.","marker":"[43]"},{"why":"Identifies the limiting spectral distribution of random d-regular graphs and its support interval, which completes the random-regular proof.","marker":"[45]"},{"why":"Frames the 2-lift and signing approach and conjectures the spectral bound that Theorem 3.1 proves in the bipartite case.","marker":"[9]"}],"fun_headline_variants":["Interlacing families prove bipartite Ramanujan graphs for all degrees","Every degree has an optimal expander: interlacing families","Method guarantees optimal spectral gaps in all degrees","Bipartite Ramanujan graphs exist for every degree","Interlacing families: all-degree expander existence"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The survey assumes, without reproducing the proofs, that the cited interlacing families theorem and the cited root-bound identities for matching polynomials and their representation-theoretic generalization are correct; if any of those cited results fails, the surveyed existence theorems do not follow.","fun_headline_variants_meta":{"raw":{"variants":["Interlacing families prove bipartite Ramanujan graphs for all degrees","Every degree has an optimal expander: interlacing families","Method guarantees optimal spectral gaps in all degrees","Bipartite Ramanujan graphs exist for every degree","Interlacing families: all-degree expander existence"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000329,"raw_usage":{"total_tokens":1798,"prompt_tokens":871,"completion_tokens":927,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":487,"completion_tokens_details":{"reasoning_tokens":849}},"tokens_in":487,"tokens_out":927,"duration_ms":8987,"temperature":1.0,"reasoning_tokens":849,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T23:12:19.071589+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Find a single $d$-regular bipartite graph for which exhaustive search over all signings shows that every signing has spectral norm strictly greater than $2\\sqrt{d-1}$; that would disprove Theorem 3.1 and the survey's central existence claim. For the random regular graph result, compute the second largest root of the expected characteristic polynomial for small $d$ and even $n$; if it ever exceeds $2\\sqrt{d-1}$, the proof chain in Section 4 would be broken.","supporting_citations":[{"cited_title":"Interla cing families i: Bipartite ramanujan graphs of all degrees","cited_arxiv_id":null,"evidence_quote":"Proves Theorem 3.1 on signings of every d-regular bipartite graph and introduces the interlacing-families method for 2-covers."},{"cited_title":"Interla cing families iv: Bipartite ramanujan graphs of all sizes","cited_arxiv_id":null,"evidence_quote":"Proves Theorem 4.1 on positive probability of one-sided Ramanujan random regular graphs and supplies the convolution identity behind it."},{"cited_title":"Ramanujan coverings o f graphs","cited_arxiv_id":null,"evidence_quote":"Establishes the n-cover analogue and the representation-theoretic signing theorem, and provides part of the proof of Theorem 2.1."},{"cited_title":"On the matching polynomial of a graph","cited_arxiv_id":null,"evidence_quote":"Gives the matching-polynomial identity for the expected characteristic polynomial of a random signing."},{"cited_title":"Theory of monomer-dimer systems","cited_arxiv_id":null,"evidence_quote":"Proves real-rootedness and the $2\\sqrt{d-1}$ root bound for matching polynomials of maximum degree $d$."},{"cited_title":"Finite fr ee convolutions of polynomials","cited_arxiv_id":null,"evidence_quote":"Develops finite free convolutions and proves the relation between the polynomial convolution and free convolution used in Theorem 4.2."},{"cited_title":"The expected eigenvalue distribution of a larg e regular graph","cited_arxiv_id":null,"evidence_quote":"Identifies the limiting spectral distribution of random d-regular graphs and its support interval, which completes the random-regular proof."},{"cited_title":"Lifts, discrepancy and nearly optim al spectral gap","cited_arxiv_id":null,"evidence_quote":"Frames the 2-lift and signing approach and conjectures the spectral bound that Theorem 3.1 proves in the bipartite case."}],"review_version":1}