{"id":"5d93025a-b682-414f-bd80-83e47234e8d1","arxiv_id":"1908.03954","paper_version":3,"verdict":"REJECT","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"Every threshold graph is sandwiched between anti-regular graphs, and this sandwich yields eigenvalue-free intervals, inertia formulas, and partial results on the anti-regular optimality conjecture.","lead":"This paper shows that every threshold graph contains a largest anti-regular graph and sits inside a smallest anti-regular graph, and uses eigenvalue interlacing to extract spectral consequences. It rederives known results, proves some cases of a conjecture about extreme eigenvalues, and gives bounds on the largest and smallest eigenvalues.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The strong induction in Theorems 4.2(iii) and 4.3(iii) applies the induction hypothesis to subgraphs whose order is precisely the critical size the theorems exclude; the main \"partial proof\" of Conjecture 4.1 is therefore circular, not merely incomplete.","rationale":"The reader's weakest assumption and my concern coincide. The paper's most novel advertised contribution is the near-optimality of the anti-regular extreme eigenvalues, expressed in Theorems 4.2(iii) and 4.3(iii). Both proofs are strong inductions, but the subgraph to which the induction hypothesis is applied has the critical order that the theorem statement explicitly excludes. For the even case, the first nontrivial use at n=6 requires the excluded 4-vertex graphs with s1>=2; for the odd case, the first use at n=5 requires the excluded 3-vertex graph with s1=1. No base case handles these families, so the argument assumes exactly the unproved cases of Conjecture 4.1. This is not a cosmetic gap: without those critical cases the claimed \"all but n-2 critical cases\" result is unproved. I credit the paper for the clean structural observations (Theorems 3.1 and 3.2), the inertia derivation (Theorem 4.1), the strengthened eigenvalue-free interval (Corollary 4.1), and the Section 5 estimates, which appear correct and are supported by explicit interlacing arguments. There is also a displayed sign reversal in Theorem 4.3(ii) and (iii): the inequalities are stated as mu_+(G) <= mu_+(A_n), whereas the conjecture, and the proof's own final inequalities, require mu_+(A_n) <= mu_+(G). This should be fixed in any revision. Given the central claim is not established, the appropriate verdict is REJECT as it stands; a corrected version could be reconsidered if the finite critical families are proved or a sound induction is supplied.","tokens_in":10423,"tokens_out":9749,"duration_ms":92040,"concrete_test":"Formalize the induction on the smallest instance where Theorem 4.2(iii) actually invokes it: n=6, k=1. The proof requires the induction hypothesis for a subgraph G~ of order 4 with s1-tilde>=2 and k=1. Check the theorem: the hypothesis reads 2k+2<n, i.e., 4<4, which fails. Enumerate the two connected threshold graphs on 4 vertices with s1>=2 (binary strings 0001 and 0011) and verify that they are precisely the critical cases excluded from the theorem; hence there is no valid base case or induction hypothesis covering them. Repeat the same check for Theorem 4.3(iii) at n=5, k=1, where the required subgraph has order 3 with s1-tilde=1 and fails the condition 2k+1<n. This logical check settles the circularity; a separate numerical computation of these small critical spectra would test the truth of the conjecture, not repair the proof.","verdict_should_be":"REJECT","load_bearing_attack":"The load-bearing defect is the induction in Theorem 4.2(iii) and Theorem 4.3(iii). In Theorem 4.2(iii), for G with s1>=2 and 2k+2<n, the proof chooses a threshold subgraph G~ with s1-tilde>=2 and |G~|=2k+2 and invokes \"by induction\" to get mu_-(G~) <= mu_-(A_{2k+2}). But Theorem 4.2(iii) is stated only under the condition 2k+2<n; for G~ the condition 2k+2<|G~| is false, so G~ belongs to the excluded critical family. Theorem 4.3(iii) has the identical structure: its subgraph has order 2k+1 with s1-tilde=1, exactly the odd critical case that the theorem excludes. Thus the induction hypothesis is unavailable unless one already assumes the unproved cases of Conjecture 4.1; the proof of the paper's central new result is circular. A separate, more superficial defect is that the displayed inequalities in Theorem 4.3(ii) and (iii) state mu_+(G) <= mu_+(A_n), the reverse of both the conjecture and of the inequalities the proofs actually derive. The interlacing-based results (Theorems 4.1, 4.2(i,ii), 4.3(i), and Section 5) appear sound, but they do not establish the optimality conjecture.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies spectral properties of threshold graphs by exploiting the fact that every connected threshold graph contains a maximal induced anti-regular subgraph. The authors show how eigenvalue interlacing with these anti-regular subgraphs yields the inertia of a threshold graph, an eigenvalue-free interval for all threshold graphs, and estimates for extreme eigenvalues. The main new claimed contribution is a partial resolution of a conjecture from [1]: that the anti-regular graph A_n has the smallest positive eigenvalue and the largest eigenvalue below -1 among all threshold graphs on n vertices, with only n-2 identified critical exceptions. The paper also proves a universality-type statement for anti-regular supergraphs and subgraphs of threshold graphs.","tokens_in":10621,"tokens_out":6311,"duration_ms":64924,"significance":"The interlacing framework in Sections 3-4 is attractive and does give a unified derivation of the inertia and of the eigenvalue-free interval, and the extreme-eigenvalue bounds in Section 5 are reasonable. Those parts of the paper are useful, though the inertia and the eigenvalue-free interval were already known by other methods. The genuinely new claim, the near-optimality of the anti-regular graph formulated in Theorems 4.2 and 4.3, is not established: the inductive proofs apply the induction hypothesis to subgraphs of exactly the critical sizes that the theorem statements explicitly exclude, so the argument is circular. In addition, the displayed conclusions of Theorem 4.3(ii) and (iii) state the reverse of the inequalities that the proofs actually derive, and the reverse statement is incompatible with the conjecture being addressed. Since the central new result rests on this defective induction, the paper's main claim should not be accepted in its current form.","major_comments":[{"comment":"The strong induction is circular. After choosing a threshold subgraph G~ with |G~| = 2k+2 and s1~ >= 2, the proof invokes the induction hypothesis to obtain mu_-(G~) <= mu_-(A_{2k+2}). However, the statement being proved by induction, Theorem 4.2(iii), is restricted to graphs satisfying 2k+2 < n. For G~ we have 2k+2 = |G~|, so G~ is precisely one of the critical graphs excluded from the statement. The induction hypothesis is therefore unavailable unless one already assumes the unproved critical cases of Conjecture 4.1, which is exactly what the theorem is supposed to establish.","section":"Theorem 4.2(iii)"},{"comment":"The same circularity occurs in the odd case. The proof chooses a threshold subgraph G~ of order 2k+1 with s1~ = 1 and uses induction to assert mu_+(A_{2k+1}) <= mu_+(G~). But Theorem 4.3(iii) is stated only under the condition 2k+1 < n, and for G~ the equality 2k+1 = |G~| holds. Thus G~ belongs to the family of critical graphs that the theorem excludes, and the induction step assumes the very cases that remain unproved. Consequently the proof does not establish the claimed near-optimality for the remaining graphs.","section":"Theorem 4.3(iii)"},{"comment":"The displayed conclusions of Theorem 4.3(ii) and (iii) state mu_+(G) <= mu_+(A_n), which is the reverse of Conjecture 4.1 and of the inequalities that the proofs actually derive. In part (ii) the chain of inequalities ends with mu_+(G), giving mu_+(A_n) <= mu_+(G), and part (iii) concludes 'mu_+(A_n) <= mu_+(G) as desired'. As printed, the theorem contradicts the conjecture it is meant to support. This is not merely a typo in the conclusion: the corrected statement mu_+(A_n) <= mu_+(G) is still not proved for the excluded families because of the induction problems in the previous comments.","section":"Theorem 4.3(ii)-(iii)"}],"minor_comments":[{"comment":"In the proof of part (i), the case split reads 'If on the other hand s2 >= 2', but from the context this should be 's1 >= 2'. The corrected statement is needed for the argument to match the case division of the theorem.","section":"Theorem 4.3(i), proof"},{"comment":"The caption of Figure 2 refers to 'Example 5.2', but the example defining G, G', and G'' is numbered Example 5.1 in the text.","section":"Figure 2"},{"comment":"The statements of Theorems 4.2 and 4.3 are phrased for every threshold graph, but the proofs use the binary-string representation of a connected threshold graph and do not explicitly address disconnected graphs. Since eigenvalues of a disconnected graph include additional zeros, the disconnected cases should be treated or the statements should be restricted.","section":"Theorems 4.2-4.3"}],"recommendation":"reject","confidential_remarks":"The valid parts of the paper, especially the inertia derivation and the eigenvalue-free interval via anti-regular interlacing, overlap substantially with known results. The novel contribution is the claimed near-optimality of the anti-regular eigenvalues, and that claim is not proven: the induction is circular in both the even and odd cases, and the statements of Theorem 4.3(ii)-(iii) are reversed. This is a load-bearing defect rather than a local presentation issue, so I recommend rejection rather than major revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper splits into two parts. The structural part is genuinely good: Theorem 3.1 and 3.2 show that every connected threshold graph has a largest anti-regular induced subgraph (and sits inside a smallest anti-regular supergraph), with the size determined by the binary-string parameter k. These facts, combined with interlacing, give a clean unified proof of known results: the inertia formula (Corollary 4.1 and Theorem 4.1) and the Omega eigenvalue-free interval (Corollary 4.2). Section 5's extremal eigenvalue bounds are new and appear correct. The writing is clear, and the survey of prior work is honest—the paper explicitly credits Ghorbani for Corollary 4.2 and Bapat/Lou-Wang-Huang for the inertia computation.\n\nThe soft spot is the paper's central advertised new result, the partial proof of Conjecture 4.1. Theorems 4.2(iii) and 4.3(iii) both use strong induction, and in both cases the induction hypothesis is applied to an induced subgraph whose order is exactly the critical size the theorem excludes. In Theorem 4.2(iii), the chosen subgraph has order 2k+2 and satisfies the hypothesis of the theorem only if 2k+2 < n, but for the subgraph its own n equals 2k+2, so the hypothesis is false. The situation is identical in the odd case with 2k+1. Thus the proof implicitly assumes the unproved critical cases of Conjecture 4.1—the very cases the paper says it cannot handle. This is a load-bearing circular step, not a minor gap. The displayed inequalities in Theorem 4.3(ii) and (iii) also have the direction reversed relative to the conjecture and to what the proofs actually show; that looks like a typo, but it is a confusing one.\n\nSo what survives is the structural core and the interlacing consequences that rederive known results. The conjecture remains open, and the paper as it stands should not be accepted as proof of even the partial cases. A revised version could either prove the finitely many critical cases directly or restate the theorems with a sound induction that avoids the excluded sizes, and must fix the inequality signs.\n\nWho is this for? People working on threshold graph spectra who might use the subgraph theorems or the Section 5 estimates. It deserves a serious referee—not because the main proof is correct, but because the structural results are true and the conjecture is natural. My recommendation: send to review, and expect the referee to reject or demand a major revision that addresses the circular induction.","headline":"The structural results on anti-regular subgraphs are clean and useful, but the paper's main advertised partial proof of the optimality conjecture is circular and leaves the conjecture unproved.","tokens_in":11286,"tokens_out":2549,"would_cite":false,"duration_ms":30090,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C50","15B05","05C75","15A18"],"pacs":[],"model":"deepseek-v4-flash","headline":"Every connected threshold graph is spectrally governed by the largest anti-regular graph it contains, and interlacing with that subgraph determines its inertia, forces a universal eigenvalue-free interval, and nearly settles the…","keywords":["threshold graph","anti-regular graph","eigenvalue interlacing","graph spectrum","inertia","eigenvalue-free interval","extremal eigenvalues","binary string representation"],"falsifier":"For each of the finitely many critical binary strings identified in Section 4 (six are listed for $n=8$), compute the eigenvalues of the corresponding threshold graph and compare $\\mu_-(G)$ and $\\mu_+(G)$ with $\\mu_-(A_n)$ and $\\mu_+(A_n)$. A single critical $G$ with $\\mu_+(G)<\\mu_+(A_n)$ or $\\mu_-(G)>\\mu_-(A_n)$ would refute Conjecture 4.1 and the induction assumption used in Theorems 4.2(iii) and 4.3(iii).","tokens_in":10095,"feed_emoji":"📊","tokens_out":8316,"duration_ms":79342,"temperature":0.7,"pith_summary":"The paper tries to show that the anti-regular graph, the unique graph with n−1 distinct degrees, is the spectral backbone of the entire class of threshold graphs. Every connected threshold graph contains a largest anti-regular induced subgraph, and the paper argues that eigenvalue interlacing from that subgraph is enough to reconstruct the graph's inertia, to exclude a universal eigenvalue-free interval, and to show the anti-regular graph has extremal extreme eigenvalues among all threshold graphs of the same order. The positive-eigenvalue half of the extremal claim is proved for all graphs and the negative half for all but an explicit family of 'almost anti-regular' graphs; the remaining cases coincide exactly with where the induction method cannot close.","feed_headline":"Anti-regular graph fixes the spectrum of every threshold graph","feed_subtitle":"One extremal subgraph determines inertia, an eigenvalue-free interval, and nearly all extreme-eigenvalue optimality.","key_machinery":"The anti-regular graph $A_n$ is the unique connected $n$-vertex graph whose degree sequence has $n-1$ distinct entries; equivalently it has alternating binary string $0101\\cdots01$ for even $n$ and $00101\\cdots01$ for odd $n$. The paper's machinery is the pair (largest anti-regular induced subgraph $A_m$, eigenvalue interlacing): Theorem 3.2 identifies $A_m$ in every connected threshold graph from its binary string, interlacing converts the known spectrum of $A_m$ into inequalities on the spectrum of $G$, and the Parity Principle (monotone convergence of $\\mu_-(A_n)$ and $\\mu_+(A_n)$ within the even and odd subsequences) converts these bounds into global statements comparing any threshold graph with $A_n$.","core_discovery":"The central discovery is that threshold-graph spectra are governed by the anti-regular subgraph. For a connected threshold graph $G$ with binary string $0^{s_1}1^{t_1}\\cdots 0^{s_k}1^{t_k}$, the largest anti-regular induced subgraph is $A_{2k+1}$ if $s_1\\ge 2$ and $A_{2k}$ if $s_1=1$. Interlacing gives, for example, when $s_1\\ge 2$: $\\lambda_i(G)\\le \\lambda_i(A_{2k+1})<-1$ for $i=1,\\dots,k$ and $0<\\lambda_{k+1+i}(A_{2k+1})\\le \\lambda_{n-k+i}(G)$ for $i=1,\\dots,k$. From these bounds the paper derives the multiplicities $m_{-1}(G)=t-k$ and $m_0(G)=s-k$, so the inertia is $(t,s-k,k)$, and no non-trivial eigenvalue lies in $[\\mu_-(A_m),\\mu_+(A_m)]$. A limiting argument from anti-regular spectra then gives the global eigenvalue-free interval $\\Omega=[\\frac{-1-\\sqrt{2}}{2},\\frac{-1+\\sqrt{2}}{2}]$ for every threshold graph, except possibly the trivial eigenvalues $-1$ and $0$. For the extremal conjecture, Theorems 4.2 and 4.3 prove the desired inequalities except for $n-2$ critical almost-anti-regular graphs in each parity, with the critical sizes exactly those where the induction step falls back on what the theorems exclude.","pith_inferences":["Because the critical graphs are finite in number and explicitly described by their binary strings, a direct computation of their extreme non-trivial eigenvalues would settle Conjecture 4.1 completely; this goes beyond the paper's partial result but is a natural next step.","The sandwiching of every threshold graph between an anti-regular subgraph and an anti-regular supergraph suggests a fast spectral-localization method: approximate the spectrum of $G$ by the spectra of two anti-regular graphs, with interlacing controlling the error.","The same skeleton idea may transfer to cographs, which the paper raises as a question; if a canonical 'largest structured induced subgraph' exists for cographs, interlacing could yield analogous inertia and eigenvalue-free results."],"forward_implications":["For any connected threshold graph, the inertia is read directly from its binary string: $(t,s-k,k)$, where $s=\\sum_i s_i$ is the number of isolated-type vertices and $t=\\sum_i t_i$ is the number of dominating-type vertices.","No threshold graph has a non-trivial eigenvalue in the interval $\\Omega=[\\frac{-1-\\sqrt{2}}{2},\\frac{-1+\\sqrt{2}}{2}]$; the only possible eigenvalues there are $-1$ and $0$.","Every threshold graph has a wider eigenvalue-free gap than the global one: its non-trivial eigenvalues avoid $[\\mu_-(A_m),\\mu_+(A_m)]$, where $A_m$ is its largest anti-regular induced subgraph.","Among all $n$-vertex threshold graphs, $A_n$ has the smallest positive eigenvalue in all cases and the largest eigenvalue below $-1$ in all but the $n-2$ critical cases identified in Section 4.","The largest and smallest eigenvalues of a threshold graph are bounded by closed-form expressions computed from initial and terminal blocks of its binary string."],"supporting_citations":[{"why":"Establishes the spectral characterization of anti-regular graphs, the Parity Principle for their extreme eigenvalues, and the two conjectures that the paper attacks.","marker":"[1]"},{"why":"Supplies the binary-string characterization and degree-partition structure of threshold graphs used throughout the proofs.","marker":"[17]"},{"why":"Derives the characteristic polynomial of anti-regular graphs and proves their eigenvalues are simple with the stated inertia.","marker":"[18]"},{"why":"First proved the $\\Omega$ eigenvalue-free interval for threshold graphs by interlacing; the present paper refines and re-derives it.","marker":"[9]"},{"why":"Provides the quotient-graph and eigenvalue-location method for threshold graphs, plus the known optimal minimum-eigenvalue result used in the estimates.","marker":"[11]"},{"why":"Contains the earlier version of the largest-anti-regular-induced-subgraph statement that Theorem 3.2 refines and proves directly from binary strings.","marker":"[19]"}],"fun_headline_variants":["Anti-regular core dictates threshold spectra","One subgraph fixes all threshold eigenvalues","Anti-regular graph pins down threshold spectra","Threshold spectra follow from anti-regular core"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the extremal eigenvalue inequality already holds for certain smaller threshold graphs, specifically those whose size is exactly the 'critical' size the theorems exclude; that premise is precisely the unproved part of Conjecture 4.1, so both optimality proofs depend on it.","fun_headline_variants_meta":{"raw":{"variants":["Anti-regular core dictates threshold spectra","One subgraph fixes all threshold eigenvalues","Anti-regular graph pins down threshold spectra","Threshold spectra follow from anti-regular core"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000163,"raw_usage":{"total_tokens":1305,"prompt_tokens":1066,"completion_tokens":239,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":682,"completion_tokens_details":{"reasoning_tokens":186}},"tokens_in":682,"tokens_out":239,"duration_ms":2902,"temperature":1.0,"reasoning_tokens":186,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:59:01.434538+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For each of the finitely many critical binary strings identified in Section 4 (six are listed for $n=8$), compute the eigenvalues of the corresponding threshold graph and compare $\\mu_-(G)$ and $\\mu_+(G)$ with $\\mu_-(A_n)$ and $\\mu_+(A_n)$. A single critical $G$ with $\\mu_+(G)<\\mu_+(A_n)$ or $\\mu_-(G)>\\mu_-(A_n)$ would refute Conjecture 4.1 and the induction assumption used in Theorems 4.2(iii) and 4.3(iii).","supporting_citations":[{"cited_title":"Aguilar and J","cited_arxiv_id":null,"evidence_quote":"Establishes the spectral characterization of anti-regular graphs, the Parity Principle for their extreme eigenvalues, and the two conjectures that the paper attacks."},{"cited_title":"Mahadev and U.N","cited_arxiv_id":null,"evidence_quote":"Supplies the binary-string characterization and degree-partition structure of threshold graphs used throughout the proofs."},{"cited_title":"Munarini","cited_arxiv_id":null,"evidence_quote":"Derives the characteristic polynomial of anti-regular graphs and proves their eigenvalues are simple with the stated inertia."},{"cited_title":"Ghorbani","cited_arxiv_id":null,"evidence_quote":"First proved the $\\Omega$ eigenvalue-free interval for threshold graphs by interlacing; the present paper refines and re-derives it."},{"cited_title":"Jacobs, V","cited_arxiv_id":null,"evidence_quote":"Provides the quotient-graph and eigenvalue-location method for threshold graphs, plus the known optimal minimum-eigenvalue result used in the estimates."},{"cited_title":"Sciriha and S","cited_arxiv_id":null,"evidence_quote":"Contains the earlier version of the largest-anti-regular-induced-subgraph statement that Theorem 3.2 refines and proves directly from binary strings."}],"review_version":1}