{"id":"4b2b3b86-4909-4fac-bca6-886610de86d9","arxiv_id":"2411.16143","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The extremal edge count and spectral radius for graphs and bipartite graphs with no [a,b]-factor are determined exactly, with all extremal graphs characterized.","lead":"This paper determines the largest possible edge count and spectral radius of graphs that avoid any spanning subgraph with all degrees between a and b, and it identifies the extremal examples for ordinary and bipartite graphs. The results settle a family of Turán-type problems and support a conjecture that edge-maximal and spectral-maximal forbidden-subgraph graphs coincide.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The non-bipartite main theorems hinge entirely on the imported threshold lemma (Lemma 8), which is not re-proved here, so a mis-stated threshold or parity condition would invalidate Theorems 1 and 2.","rationale":"The paper is carefully organized, and the proof chain after Lemma 8 is internally consistent: the edge bound, the reduction to spectral radius via Lemma 4, and the bipartite arguments using the Folkman-Fulkerson criterion all check out. The genuinely load-bearing unverified element is Lemma 8, exactly as the reader identified. It is a published theorem, so relying on it is methodologically acceptable, but because the entire sharp threshold for graphs with delta(G) >= a depends on its exact statement, the conditional verdict with moderate confidence is appropriate. My stress-test found no internal inconsistency or counterexample, so I do not recommend moving the verdict; rather, the concrete computational and re-derivation check would settle the remaining verification risk.","tokens_in":24736,"tokens_out":45198,"duration_ms":399755,"concrete_test":"Exhaustively verify Lemma 8 for all n <= 9 and all 1 <= a <= b with n >= a+1 (and na even when a=b): enumerate all n-vertex graphs with delta(G) >= a and e(G) >= binom(n-1,2)+(a+1)/2, and test each for an [a,b]-factor using the Folkman-Fulkerson criterion or a flow-based subroutine. If every such graph has a factor, the threshold is supported; then independently re-derive Lemma 8 from Wei-Zhang's proof, checking the parity clause, to confirm the lemma is quoted exactly.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 1's Case 2 (delta(G) >= a) is the only step excluding [a,b]-factors in the high-edge regime: it invokes Lemma 8's contrapositive to conclude e(G) <= binom(n-1,2) + a/2. The equality cases then rely on Lemmas 9 and 10, and Theorem 2's spectral bound reduces to Theorem 1 via Lemma 4. Lemma 8 is imported from [44] without proof, without a proof sketch, and without any internal verification; the sharp threshold binom(n-1,2)+(a+1)/2 and the parity clause 'na even when a=b' are exactly what force the claimed bound binom(n-1,2)+a-1. If the published lemma has an additional hidden hypothesis, or if the threshold should be binom(n-1,2)+a instead of binom(n-1,2)+(a+1)/2, then the edge extremal theorem needs revision and Theorem 2 collapses with it. This is a verification concern rather than a demonstrated error: I found no counterexample in the manuscript, but the paper's central claim is only as secure as Lemma 8.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies Turán-type problems for graphs with no [a,b]-factor, i.e., no spanning subgraph whose degrees all lie in the interval [a,b]. It determines, for n-vertex graphs, the maximum number of edges ex(n,F_{a,b}) and the maximum adjacency spectral radius ex_sp(n,F_{a,b}), together with the complete lists of extremal graphs, under the parity condition na≡0 (mod 2) when a=b. It also obtains the bipartite analogues, both with fixed partite sizes and with fixed total order, again with full extremal characterizations. As a byproduct, it shows that the spectral extremal graphs lie inside the edge-extremal graphs, contributing to a problem of Liu and Ning, and it deduces a main result of Fan and Lin on spectral conditions for k-factors in balanced bipartite graphs. The proofs use the Folkman-Fulkerson (g,f)-factor criterion, Ore's Hamiltonian theorems, Rowlinson's spectral bound, Liu-Weng's bound for dense bipartite graphs, and detailed case analyses.","tokens_in":6,"tokens_out":36571,"duration_ms":407823,"significance":"If correct, these results completely settle the edge and spectral extremal problems for the family of [a,b]-factors, a natural and broad class of spanning subgraphs. The explicit identification of all extremal graphs, including the bipartite double nested graphs, is valuable, and the inclusion Ex_sp⊆Ex is a nontrivial positive contribution to Problem 1 of Liu and Ning. The paper also unifies and extends earlier results on k-factors and [a,b]-factors. The proofs are largely self-contained apart from the imported Lemma 8, and the case analyses in the bipartite proofs are detailed and checkable. The spectral comparisons via equitable partitions and characteristic polynomials are concrete and avoid black-box extremal arguments.","major_comments":[{"comment":"As printed, Theorem 1(ii) and Lemma 10 state the exceptional graph as K2∨K3. Since K2∨K3 is the complete graph K5, it contains a Hamiltonian cycle and hence a [2,2]-factor; it therefore cannot be an extremal graph for [2,2]-factor-free graphs. The intended graph is evidently K2∨\\overline{K3}, the join of K2 with the complement of K3. Please correct this typographical error in Theorem 1(ii), Lemma 10, and any subsequent references (e.g., the discussion in Section 6). This is not merely cosmetic: as written, Theorem 1 is false for n=5, a=b=2.","section":"Theorem 1(ii) and Lemma 10"},{"comment":"The proof of Theorem 1 in the case δ(G)≥a rests entirely on Lemma 8, which is quoted from [44] without proof and without a precise reference (theorem number or page). The exact threshold binom(n-1,2)+(a+1)/2 and the parity condition na≡0 (mod 2) when a=b are load-bearing: the contrapositive gives e(G)≤binom(n-1,2)+a/2, which in turn yields the claimed bound binom(n-1,2)+a-1 for a≥3. If the lemma as quoted from [44] has any additional hidden hypothesis (e.g., a lower bound on n, or a connectedness assumption), Theorems 1 and 2 would require revision. Please either provide a proof of Lemma 8 in the paper or give the exact statement and theorem number in [44], and confirm that the statement is correctly reproduced.","section":"Section 3, Lemma 8"}],"minor_comments":[{"comment":"In the displayed characteristic polynomials Φ2(x) and Φ3(x), the symbol \"t2\" should be \"x^2\"; the current rendering makes the algebra difficult to follow.","section":"Section 5, equations (5.2) and (5.3)"},{"comment":"When u∈X, the graph D(p−1,1; a−1,q−a+1) is isomorphic to D(a−1,p−a+1;q−1,1) by interchanging the bipartition and reversing the order of the parts; stating this explicitly would remove the apparent mismatch with the theorem's equality case.","section":"Section 4, proof of Theorem 3, Case 1"},{"comment":"The sentence \"by Theorem 3(iii), G contains a [1,b]-factor\" is a non-sequitur in isolation; the intended argument is the contrapositive: if G had no [1,b]-factor, then equality in Theorem 3(iii) would force G≅G1, contradicting the assumption. Please rephrase this step.","section":"Section 5, proof of Theorem 5(iii)"},{"comment":"The exceptional graphs K1,3 and K2∨\\overline{K3} have orders 4 and 5 respectively; a remark noting that these graphs can appear as equality cases only for those orders would prevent the reader from thinking they occur for all n.","section":"Theorems 1 and 4"},{"comment":"The equality analysis concludes that G≅K_{n/2−1,n/2+1}; it would help to note that this graph coincides with D(a−1,n/2−a;n/2,1) when a=n/2, which is already in the list of extremal graphs.","section":"Section 4, proof of Theorem 4, Case 2"},{"comment":"The proof uses \"by a direct computation\" for the characteristic polynomials in (5.1)–(5.3); since these computations are central to the spectral comparison, adding the intermediate simplification steps would improve verifiability.","section":"Section 5, proof of Theorem 7"}],"recommendation":"major_revision","confidential_remarks":"The manuscript makes a solid contribution if the typographical issue with the missing complement bar is fixed and the status of Lemma 8 is clarified. The reliance on [44] without proof is acceptable in principle, but given that the main theorem hinges on the exact threshold, a precise citation or a brief proof sketch is warranted. No concerns about novelty or citation practices beyond the above."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my take. The real contribution is the bipartite part: Theorems 3, 4, 5, and 7 determine the [a,b]-factor Turán and spectral Turán numbers for bipartite graphs with given part sizes and with given order, including extremal graphs. Those results are new, and the proofs go through Folkman-Fulkerson factor criteria plus careful double-nested graph comparisons. The spectral deductions via equitable quotient matrices and characteristic polynomials are legitimate and detailed enough to check. The inclusion Ex_sp ⊆ Ex is a nice dividend, and the connection to Liu-Ning's problem is real.\n\nThe non-bipartite theorems (1 and 2) are also plausible, but they are built on an imported lemma: Lemma 8 from Wei-Zhang supplies the sharp threshold that does the work in the δ ≥ a case. It isn't re-proved or even sketched here, so the central bound for general graphs is only as secure as that external result. A referee should verify Lemma 8's statement and parity condition before trusting Theorems 1 and 2. That's not a demonstrated error, just a load-bearing dependency.\n\nPresentation issues are real but fixable. Theorem 1(ii) and Lemma 10 are garbled in the rendering: the exceptional graph should be K2 joined to the complement of K3, not K2 ∨ K3. The complement bars are missing, and as printed the statement is wrong. Section 6 also misattributes to O [34] a Turán result for perfect matchings; O's paper is about spectral radius and matchings, so that bullet needs correcting. Those slips make me want to see a revision before publication.\n\nSo: I'd send it to a serious referee. The bipartite theorems alone justify that. The referee should focus on Lemma 8 and the exact statements of the exceptions. I'd also suggest the authors add a short proof or at least a precise statement of Lemma 8 to make the paper more self-contained. My own verdict would be conditional acceptance; the math core looks sound, but the presentation and citations need work.","headline":"Genuinely new bipartite results underpin a solid paper; the general-graph theorems lean on an imported lemma and the text has fixable rendering and citation slips.","tokens_in":25515,"tokens_out":2174,"would_cite":true,"duration_ms":20327,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C35","05C50","05C70"],"pacs":[],"model":"deepseek-v4-flash","headline":"Graphs with no $[a,b]$-factor have at most $\\binom{n-1}{2}+a-1$ edges, and the same extremal graph wins for spectral radius.","keywords":["[a,b]-factor","Turán number","spectral Turán number","extremal graph","double nested graph","bipartite graph","spectral radius","k-factor"],"falsifier":"Run an exhaustive search at the smallest nontrivial parameters, e.g., $a=1$, $b=1$, $n=6$: the imported lemma predicts that every 6-vertex graph with $\\delta(G)\\ge 1$ and at least $\\binom{5}{2}+1=11$ edges contains a perfect matching, so any such graph without one would refute the engine behind Theorems 1 and 2. For the bipartite results, check whether any graph with part sizes $p\\le q$, $a\\le p$, $aq\\le bp$, and $e(G)=p(q-1)+a$ fails to have an $[a,b]$-factor; Theorem 3 predicts none, and a single violation would break the $(g,f)$-criterion argument used in the bipartite proofs.","tokens_in":24535,"feed_emoji":"📈","tokens_out":14465,"duration_ms":124812,"temperature":0.7,"pith_summary":"The paper settles the extremal question for graphs that contain no $[a,b]$-factor, meaning no spanning subgraph in which every vertex degree lies between $a$ and $b$. It proves that every $n$-vertex graph without such a factor has at most $\\binom{n-1}{2}+a-1$ edges, with the extremal graph $K_{a-1}\\vee(K_{n-a}\\cup K_1)$, apart from two small exceptional graphs in low-parameter cases. The same graph is shown to maximize the adjacency spectral radius, so the spectral extremal set is contained in the ordinary extremal set, giving a positive answer to the containment problem posed in [29] for this family. The bipartite analogues are also determined, with the extremal graph being either a complete bipartite graph or a double nested graph $D(a-1,p-a+1;q-1,1)$ depending on the parameters. As a corollary, the results recover the known spectral condition for $k$-factors in balanced bipartite graphs, stated in the paper as [15, Theorem 1.3].","feed_headline":"No [a,b]-factor? Max edges is binom(n-1,2)+a-1","feed_subtitle":"The same extremal graph also maximizes spectral radius, and bipartite analogues are pinned down.","key_machinery":"The proof runs a two-tier degree argument. If $\\delta(G)\\le a-1$, the graph embeds in $K_{a-1}\\vee(K_{n-a}\\cup K_1)$, which immediately yields the edge bound; if $\\delta(G)\\ge a$, an imported threshold lemma [44] says that $e(G)\\ge \\binom{n-1}{2}+\\frac{a+1}{2}$ forces an $[a,b]$-factor when $na$ is even in the case $a=b$, so a factor-free graph must fall strictly below this threshold. The bipartite arguments use the $(g,f)$-factor criterion of [17]: a bipartite graph has an $[a,b]$-factor if and only if $b|S|+\\sum_{v\\in T}d_G(v)-a|T|-e(S,T)\\ge 0$ and its mirror inequality hold for all subsets $S\\subseteq X$ and $T\\subseteq Y$; violating this criterion supplies the inequalities that bound the edge count. The extremal bipartite shapes are double nested graphs, in which the $i$-th block of one part is joined to the first several blocks of the other part, and their spectral radii are compared through equitable quotient matrices and the associated characteristic polynomials.","core_discovery":"The central discovery is a sharp phase transition: an $n$-vertex graph contains an $[a,b]$-factor as soon as its edge count reaches $\\binom{n-1}{2}+a$, provided $n\\ge a+1$ and, when $a=b$, $na$ is even. The unique obstruction below that threshold is the join $K_{a-1}\\vee(K_{n-a}\\cup K_1)$, consisting of a clique on $a-1$ universal vertices joined to a clique on $n-a$ vertices plus one isolated vertex; the exceptional graphs $K_{1,3}$ and $K_2\\vee K_3$ cover the cases $ab\\le 2$ and $a=b=2$ respectively. The same join is the unique spectral extremal graph, so a graph whose spectral radius reaches $\\rho(K_{a-1}\\vee(K_{n-a}\\cup K_1))$ must contain an $[a,b]$-factor unless it is exactly that graph. In the bipartite setting with parts of sizes $p\\le q$, the extremal graph is the complete bipartite graph $K_{p,q}$ when $aq>bp$ or $a>p$, and otherwise the double nested graph $D(a-1,p-a+1;q-1,1)$; for a fixed total number of vertices the answer is whichever of the corresponding complete bipartite graph and nested graph has more edges or larger spectral radius.","pith_inferences":["The same equitable-quotient technique used for $D(a-1,p-a+1;q-1,1)$ should transfer to other bipartite spectral extremal problems whose candidates are a complete bipartite graph and a nested chain graph; the deciding comparison is a single polynomial inequality.","The bipartite proof is driven entirely by the $(g,f)$-factor criterion, so the results should extend to $(g,f)$-factors with non-constant degree intervals by replacing the constants $a,b$ with vertex-dependent functions in the extremal inequalities.","With $\\delta(G)\\ge a$ imposed, the extremal join has an isolated vertex and cannot be extremal; determining the true extremal graphs for that minimum-degree variant, posed as Problem 2 in the paper, would require new arguments and could be explored computationally for small $a,b$."],"forward_implications":["Every $n$-vertex graph with more than $\\binom{n-1}{2}+a-1$ edges contains an $[a,b]$-factor, and the graphs listed in Theorem 1 are the only factor-free graphs attaining the bound.","Every $n$-vertex graph whose spectral radius is at least $\\rho(K_{a-1}\\vee(K_{n-a}\\cup K_1))$ contains an $[a,b]$-factor unless it is exactly that join, giving a spectral analogue of the edge threshold.","Directly, $\\mathrm{Ex}_{sp}(n,\\mathcal{F}_{a,b})\\subseteq \\mathrm{Ex}(n,\\mathcal{F}_{a,b})$ for all admissible $a,b,n$, and the same containment holds for bipartite graphs, resolving the containment problem of [29] for these families.","In the balanced bipartite case $a=b=k$, the spectral bound recovers the $k$-factor theorem of [15]."],"supporting_citations":[{"why":"Supplies the threshold lemma used to rule out the $\\delta(G)\\ge a$ case in Theorems 1 and 2; without it the main non-bipartite bounds do not go through.","marker":"[44]"},{"why":"Provides the $(g,f)$-factor criterion that drives the bipartite edge and spectral proofs in Theorems 3 and 5.","marker":"[17]"},{"why":"Supplies the Hamilton path and cycle lemmas that identify the exceptional graphs $K_{1,3}$ and $K_2\\vee K_3$ in the low-parameter cases of Theorem 1.","marker":"[35]"},{"why":"Gives the maximal-spectral-radius graph among graphs with a prescribed number of edges, used in Theorem 2 to force the edge count upward.","marker":"[37]"},{"why":"Gives the bound $\\rho(G)\\le \\sqrt{2e(G)-n+1}$ that converts the spectral assumption in Theorem 2 into an edge-count assumption.","marker":"[22]"},{"why":"Gives the spectral bound for bipartite graphs with fixed part sizes and edge count, used to identify the double nested extremal graphs in Theorem 5.","marker":"[28]"},{"why":"The bipartite $k$-factor spectral theorem that Theorem 5 deduces when $a=b=k$, providing the comparison target for the balanced case.","marker":"[15]"},{"why":"Raises the containment problem $\\mathrm{Ex}_{sp}\\subseteq\\mathrm{Ex}$ solved here for $[a,b]$-factor-free graphs and bipartite graphs.","marker":"[29]"}],"fun_headline_variants":["Max edges without [a,b]-factor: binom(n-1,2)+a-1","Spectral extremal for [a,b]-factors also maximizes edges","Bipartite [a,b]-factor Turán: two extremal shapes","One edge below threshold: unique [a,b]-factor-free graph","Exact Turán and spectral numbers for [a,b]-factors"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is the imported lemma [44] asserting that every $n$-vertex graph with $\\delta(G)\\ge a$ and $e(G)\\ge \\binom{n-1}{2}+\\frac{a+1}{2}$ contains an $[a,b]$-factor, with $na$ even when $a=b$; the paper does not reprove this lemma, so a failure in any degree or parity range would require revising Theorems 1 and 2.","fun_headline_variants_meta":{"raw":{"variants":["Max edges without [a,b]-factor: binom(n-1,2)+a-1","Spectral extremal for [a,b]-factors also maximizes edges","Bipartite [a,b]-factor Turán: two extremal shapes","One edge below threshold: unique [a,b]-factor-free graph","Exact Turán and spectral numbers for [a,b]-factors"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.003505,"raw_usage":{"total_tokens":13359,"prompt_tokens":1309,"completion_tokens":12050,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":925,"completion_tokens_details":{"reasoning_tokens":11950}},"tokens_in":925,"tokens_out":12050,"duration_ms":83791,"temperature":1.0,"reasoning_tokens":11950,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T13:34:01.704465+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run an exhaustive search at the smallest nontrivial parameters, e.g., $a=1$, $b=1$, $n=6$: the imported lemma predicts that every 6-vertex graph with $\\delta(G)\\ge 1$ and at least $\\binom{5}{2}+1=11$ edges contains a perfect matching, so any such graph without one would refute the engine behind Theorems 1 and 2. For the bipartite results, check whether any graph with part sizes $p\\le q$, $a\\le p$, $aq\\le bp$, and $e(G)=p(q-1)+a$ fails to have an $[a,b]$-factor; Theorem 3 predicts none, and a single violation would break the $(g,f)$-criterion argument used in the bipartite proofs.","supporting_citations":[{"cited_title":"Wei, S.G","cited_arxiv_id":null,"evidence_quote":"Supplies the threshold lemma used to rule out the $\\delta(G)\\ge a$ case in Theorems 1 and 2; without it the main non-bipartite bounds do not go through."},{"cited_title":"Folkman, D.R","cited_arxiv_id":null,"evidence_quote":"Provides the $(g,f)$-factor criterion that drives the bipartite edge and spectral proofs in Theorems 3 and 5."},{"cited_title":"Ore, Arc coverings of graphs, Ann","cited_arxiv_id":null,"evidence_quote":"Supplies the Hamilton path and cycle lemmas that identify the exceptional graphs $K_{1,3}$ and $K_2\\vee K_3$ in the low-parameter cases of Theorem 1."},{"cited_title":"Rowlinson, On the maximal index of graphs with a prescribed nu mber of edges, Linear Algebra Appl","cited_arxiv_id":null,"evidence_quote":"Gives the maximal-spectral-radius graph among graphs with a prescribed number of edges, used in Theorem 2 to force the edge count upward."},{"cited_title":"Hong, A bound on the spectral radius of graphs, Linear Alge bra Appl","cited_arxiv_id":null,"evidence_quote":"Gives the bound $\\rho(G)\\le \\sqrt{2e(G)-n+1}$ that converts the spectral assumption in Theorem 2 into an edge-count assumption."},{"cited_title":"Liu, C.-W","cited_arxiv_id":null,"evidence_quote":"Gives the spectral bound for bipartite graphs with fixed part sizes and edge count, used to identify the double nested extremal graphs in Theorem 5."}],"review_version":1}