{"id":"34e577ae-5bfd-4ccf-8a90-e12361197242","arxiv_id":"2505.24577","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"The weak graph complement conjecture is resolved with a universal constant 1+1/sqrt(2) below 2, and a full Nordhaus-Gaddum characterization of graph degeneracy is given.","lead":"This paper proves a long-suspected weak bound on how large the combined minimum ranks of a graph and its complement can be, using a classical 1972 theorem about highly connected subgraphs. It also gives new partial answers to the delta conjecture and completely describes which pairs of degeneracy values a graph and its complement can have.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified.","rationale":"The reader correctly identified Theorem 1.6 as the only non-obvious external dependency of Theorem 2.3. I examined that dependency and the full derivation of Theorem 2.2. The quadratic root, the floor step, the Mader order condition, and the Cauchy application are all correct. Theorem 1.6 is a standard quoted result, and no evidence of a misstatement was found in the manuscript. Section 3 and the delta-conjecture results are conditional or auxiliary and do not affect the main unconditional resolution of the weak graph complement conjectures. Since the core argument survives scrutiny, there is no reason to change the reader's ACCEPT verdict. Agreement is marked 'partial' because the reader's weakest-assumption choice is the same spot I examined, but I do not treat it as a live objection after checking.","tokens_in":15225,"tokens_out":16200,"duration_ms":191717,"concrete_test":"Independently re-derive Theorem 1.6 from [19] and [14, Theorem 4], and then computationally verify Theorem 2.2 for all graphs of order n<=7 using exact values of nu from a brute-force PSD/SAP nullity search; if any graph violates the stated inequality, Theorem 2.3 would need revision.","verdict_should_be":"UNCHANGED","load_bearing_attack":"No significant objection identified. The central claim in Theorem 2.3 is internally consistent: applying Theorem 2.2 to both G and G^c gives mr_nu(G)+mr_nu(G^c) < n+1 + (sqrt(m(G))+sqrt(m(G^c)))/sqrt(2), and the Cauchy bound sqrt(m)+sqrt(m^c) <= sqrt(2(m+m^c)) = sqrt(n(n-1)) yields the advertised constant 1+1/sqrt(2). The root/floor manipulation in Theorem 2.2 is sound: for the positive root k0 = n/2 + 5/4 - sqrt((n^2-n-2m)/4 + 9/16), the integer k=floor(k0) satisfies k>k0-1 and k <= (n+1)/2, so Mader's order hypothesis n >= 2k-1 is not violated. The only external input is Theorem 1.6, namely nu(G) >= ceil(kappa)(G), quoted from Lovasz-Saks-Schrijver and van der Holst; this is a standard result and is exactly what is needed to convert Mader's k-connected subgraph into a lower bound on nu. No hidden assumption or algebraic slip was found in the proof of the main theorem.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies Nordhaus-Gaddum-type bounds for graph minimum rank parameters and the delta conjecture. Its main result, Theorem 2.3, proves that for every graph G of order n≥4, mr_ν(G)+mr_ν(G^c) < (1+1/sqrt(2))n+1, where mr_ν(G)=|G|-ν(G) and ν(G) is the maximum nullity among positive semidefinite matrices with the strong Arnold property. Since mr(G)≤mr_+(G)≤mr_ν(G), this gives an explicit constant below 2 and thereby resolves the Weak Graph Complement Conjecture (Conjecture 1.4) for all three key minimum rank parameters. The proof combines Mader's theorem on highly connected subgraphs with the known inequality ν(G)≥ceil(kappa)(G). The paper also proves partial results toward the delta conjecture for ν under girth and forbidden-subgraph conditions, characterizes the possible values of the degeneracy sum l(G)+l(G^c), and derives conditional improvements of the weak GCC assuming the delta conjecture.","tokens_in":15461,"tokens_out":50896,"duration_ms":560960,"significance":"The central result is significant: it settles a long-standing open weak form of the Graph Complement Conjecture with an explicit constant, using a short and transparent argument. The degeneracy characterization in Section 3 is a self-contained contribution of independent interest, and the partial delta-conjecture results are new and clearly presented. The paper does not use fitted parameters; all claimed constants are explicit where relevant, and conditional statements are carefully flagged. The main external input, ν(G)≥ceil(kappa)(G), is standard and is applied correctly. Overall the central claims are convincing and the proofs check out.","major_comments":[],"minor_comments":[{"comment":"In Algorithm 1, line 1 reads 'maxlGc(n,h)', which is never defined and is not used by the algorithm; please remove it or replace it with an explicit initialization.","section":"§3, Algorithm 1"},{"comment":"The proof applies Mader's theorem with k=1 for graphs with fewer than n edges; please clarify the convention for 1-connectivity of a single vertex, or add a one-sentence trivial argument for the k=1 case so that the lower bound is unambiguous under either convention.","section":"§2, Theorem 2.2"},{"comment":"The justification of the exceptional case in (19) is incorrect: the inequality floor(2n-1-sqrt(2n^2-2n+1)) < floor(2n-1-sqrt(2n^2-2n)) occurs when 2n^2-2n is a perfect square, not when 2n^2-2n+1 is a perfect square; the conclusion that the exceptional integer r is even remains correct, but the argument should be corrected.","section":"§3, Theorem 3.7"},{"comment":"Reference [28] is cited as 'Mitchel' in the text but appears as 'Mitchell' in the bibliography; please standardize the spelling.","section":"§3.1"}],"recommendation":"minor_revision","confidential_remarks":"The paper is strong and the main result is correct. The issues I found are local and do not affect the central claims, so I recommend minor revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper settles the weak graph complement conjecture (the b < 2 version) for all the standard minimum rank parameters, with the explicit constant 1+1/sqrt(2) ≈ 1.707. That is a genuine open problem from the 2006 AIM workshop, and the proof is short and correct. It also gives a complete characterization of which sums l(G)+l(G^c) are realizable, which is a nice Nordhaus-Gaddum result in its own right.\n\nWhat's new: the key idea is to apply Mader's theorem to force a highly connected subgraph in G and in G^c, then convert the connectivity to nu via the Lovász-Saks-Schrijver / van der Holst result (Theorem 1.6). I checked the root/floor calculation in Theorem 2.2 and the Cauchy step in Theorem 2.3; the algebra is clean. I don't find this Mader-based approach in the prior GCC literature. The degeneracy part is more involved: Algorithm 1 constructs graphs with prescribed degeneracy pair, and Theorem 3.7 shows that every integer in the interval [2n-1 - sqrt(2n^2-2n+1), n-1] is a possible sum. The induction in Theorem 3.4 is dense but I didn't find a gap.\n\nSoft spots: the main theorem relies on Theorem 1.6, an external theorem, but it is standard and published, so that is not a real weakness. The delta conjecture section is partial in the honest sense: the results require large girth or large minimum degree, and the constants r(s,s') are existential rather than explicit. That is fine. The exposition could be tightened in Section 3; the proof of Fact 1 in Theorem 3.4 is hard to follow, but the claims are plausible and the structure is right. I have no mathematical objection.\n\nThis paper is for people working in combinatorial matrix theory or graph theory with matrix invariants. It deserves a serious referee; I would accept it for review without hesitation. The main theorem is important enough that referees should check the Mader application carefully, but it holds up.","headline":"Mader's theorem gives a clean proof of the weak graph complement conjecture with constant 1+1/sqrt(2), plus a full degeneracy-pair characterization; the paper is solid and deserves refereeing.","tokens_in":15995,"tokens_out":6622,"would_cite":true,"duration_ms":71490,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C50","15A03","05C35"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves a universal bound below 1.708n for the minimum-rank sum of a graph and its complement, settling the weak graph complement conjecture for all key parameters.","keywords":["minimum rank","maximum nullity","strong Arnold property","graph complement conjecture","delta conjecture","Mader's theorem","graph degeneracy","Nordhaus-Gaddum"],"falsifier":"Any graph $G$ of order $n\\ge4$ with $\\operatorname{mr}_\\nu(G)+\\operatorname{mr}_\\nu(G^c) \\ge (1+1/\\sqrt2)n+1$ would disprove Theorem 2.3; a natural test family is the self-complementary Matula graphs of order $4s$ described in Remark 2.4, since the paper's own argument shows such graphs limit the connectivity-based method to $\\tfrac32 n$.","tokens_in":15051,"feed_emoji":"🧮","tokens_out":11754,"duration_ms":102124,"temperature":0.7,"pith_summary":"The paper proves that for every graph $G$ on $n\\ge 4$ vertices, $\\operatorname{mr}_\\nu(G)+\\operatorname{mr}_\\nu(G^c) < (1+1/\\sqrt2)n+1$, where $\\operatorname{mr}_\\nu(G)=n-\\nu(G)$ and $\\nu(G)$ is the maximum positive-semidefinite nullity with the strong Arnold property. Since the ordinary minimum rank $\\operatorname{mr}(G)$ and the positive-semidefinite minimum rank $\\operatorname{mr}_+(G)$ never exceed $\\operatorname{mr}_\\nu(G)$, this one inequality settles the weak graph complement conjecture for all three parameters with a universal constant below 2. The proof runs Mader's classical connectivity theorem through the known lower bound $\\nu(G)\\ge\\lceil\\kappa\\rceil(G)$. The paper also makes partial progress on the $\\delta$-conjecture, verifying $\\nu(G)\\ge\\delta(G)$ for several girth and minimum-degree classes, and it determines the exact set of possible values of the degeneracy sum $l(G)+l(G^c)$.","feed_headline":"Weak graph complement conjecture settled with constant below 1.708","feed_subtitle":"The sum stays below 1.708n for every graph and its complement, closing a long-open weak conjecture.","key_machinery":"Two mechanisms carry the paper. The first is Mader's 1972 theorem: a graph of average degree at least $4(k-1)$ contains a $k$-connected subgraph; combined with $\\nu(G)\\ge\\lceil\\kappa\\rceil(G)$, this converts edge density in $G$ or $G^c$ into a lower bound on $\\nu$. The second is a degeneracy-pair analysis built on a greedy algorithm that constructs, for each admissible pair $(h,k)$, a graph with $l(G)=h$ and $l(G^c)=k$; the algorithm's correctness proof yields the exact Nordhaus-Gaddum range for $l(G)+l(G^c)$.","core_discovery":"The central discovery is Theorem 2.3: for every graph $G$ of order $n\\ge4$, $\\operatorname{mr}_\\nu(G)+\\operatorname{mr}_\\nu(G^c) < (1+1/\\sqrt2)n+1$. The proof first establishes, from Mader's theorem and the inequality $\\nu(G)\\ge\\lceil\\kappa\\rceil(G)$, that $\\nu(G) > (n-1)/2 - \\sqrt{m(G^c)/2}$; applying this bound to both $G$ and $G^c$ and using $m(G)+m(G^c)=n(n-1)/2$ yields the constant $1+1/\\sqrt2$. Because $\\operatorname{mr}(G)\\le\\operatorname{mr}_+(G)\\le\\operatorname{mr}_\\nu(G)$, the same inequality resolves the weak form of the graph complement conjecture for all key minimum-rank parameters. Alongside this, the paper shows $\\nu(G) > \\lceil d\\rceil(G)/4$, proves the $\\delta$-conjecture for constrained graph classes via girth and forbidden-subgraph hypotheses, and gives the sharp interval of possible degeneracy sums $l(G)+l(G^c)$.","pith_inferences":["The unconditional constant $1+1/\\sqrt2$ is probably not final: the Matula graphs in Remark 2.4 show the connectivity-subgraph method itself cannot beat $3/2$, so any improvement toward $3/2$ would need a genuinely different argument.","If the $\\delta$-conjecture is eventually proved, the degeneracy theorem in Section 3 converts it immediately into the $\\sqrt2\\,n+1$ bound, so the exact degeneracy-sum range has a direct quantitative payoff.","The exact range of $l(G)+l(G^c)$ invites analogous exact Nordhaus-Gaddum characterizations for other minor-monotone parameters; the paper's Figure 1 already shows $\\lceil\\delta\\rceil(G)+\\lceil\\delta\\rceil(G^c)$ can exceed $n-1$, so this would require new arguments."],"forward_implications":["The inequality $\\operatorname{mr}_\\nu(G)+\\operatorname{mr}_\\nu(G^c) < (1+1/\\sqrt2)n+1$ immediately gives the same weak-GCC bound for $\\operatorname{mr}$ and $\\operatorname{mr}_+$, since $\\operatorname{mr}(G)\\le\\operatorname{mr}_+(G)\\le\\operatorname{mr}_\\nu(G)$.","A by-product of the proof is a constant $b_\\nu<2$ such that $\\operatorname{mr}_\\nu(G)+\\operatorname{mr}_\\nu(G^c) \\le b_\\nu n$ for every graph, matching the original 'Question 2' form of the weak conjecture without the additive $+2$.","If the $\\delta$-conjecture holds, the bound improves to $\\operatorname{mr}_\\nu(G)+\\operatorname{mr}_\\nu(G^c) \\le \\sqrt2\\,n + 1$ (and, more elementarily, to $\\tfrac32 n + \\tfrac12$).","The $\\delta$-conjecture for $\\nu$ is verified for graphs with girth at least 11 and minimum degree at least 4, for girth 7–10 with minimum degree at least 193, for girth 5–6 with minimum degree at least $8\\cdot10^6$, and for $K_{s,s'}$-free or $C_{2t}$-free graphs with sufficiently large minimum degree.","The degeneracy sum $l(G)+l(G^c)$ takes every integer value in the interval $[2n-1-\\sqrt{2n^2-2n+1},\\, n-1]$, and no values outside it; the endpoints are therefore best possible."],"supporting_citations":[{"why":"Mader's 1972 theorem supplies the $k$-connected subgraph in every sufficiently dense graph, the engine that turns edge counts into $\\nu$ lower bounds.","marker":"[24]"},{"why":"Establishes $M_+(G)\\ge\\kappa(G)$ through faithful orthogonal representations, the first connectivity-to-nullity bridge.","marker":"[19]"},{"why":"Shows a positive semidefinite matrix with the strong Arnold property attains the connectivity bound, giving $\\nu(G)\\ge\\kappa(G)$ and hence Theorem 1.6.","marker":"[14]"},{"why":"Poses the weak graph complement conjecture in the form that Theorem 2.3 resolves, fixing the problem and its 'Question 2' formulation.","marker":"[4]"},{"why":"Provides the self-complementary Matula graphs used in Remark 2.4 to show the connectivity-subgraph strategy cannot pass $\\tfrac32 n$.","marker":"[27]"},{"why":"Supplies the degeneracy-to-nullity inequality $\\nu(G)\\ge n-2l(G^c)-1$ used in the conditional improvements of Section 3.1.","marker":"[28]"}],"fun_headline_variants":["Graph complement sum bound lowered to 1.707n","Weak complement conjecture proven for all rank parameters","Mader's trick gives 1.707 constant for graph complement","Weak complement conjecture resolved: bound 1.707n"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is the quoted theorem that $\\nu(G)\\ge\\lceil\\kappa\\rceil(G)$: the maximum positive-semidefinite nullity with the strong Arnold property is never below the minor-monotone ceiling of vertex connectivity, and if that inequality failed, the universal constant $1+1/\\sqrt2$ would not follow.","fun_headline_variants_meta":{"raw":{"variants":["Graph complement sum bound lowered to 1.707n","Weak complement conjecture proven for all rank parameters","Mader's trick gives 1.707 constant for graph complement","Weak complement conjecture resolved: bound 1.707n"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000976,"raw_usage":{"total_tokens":4143,"prompt_tokens":941,"completion_tokens":3202,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":557,"completion_tokens_details":{"reasoning_tokens":3136}},"tokens_in":557,"tokens_out":3202,"duration_ms":22546,"temperature":1.0,"reasoning_tokens":3136,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T12:22:28.100076+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Any graph $G$ of order $n\\ge4$ with $\\operatorname{mr}_\\nu(G)+\\operatorname{mr}_\\nu(G^c) \\ge (1+1/\\sqrt2)n+1$ would disprove Theorem 2.3; a natural test family is the self-complementary Matula graphs of order $4s$ described in Remark 2.4, since the paper's own argument shows such graphs limit the connectivity-based method to $\\tfrac32 n$.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Mader's 1972 theorem supplies the $k$-connected subgraph in every sufficiently dense graph, the engine that turns edge counts into $\\nu$ lower bounds."},{"cited_title":"Lov ´asz, M","cited_arxiv_id":null,"evidence_quote":"Establishes $M_+(G)\\ge\\kappa(G)$ through faithful orthogonal representations, the first connectivity-to-nullity bridge."},{"cited_title":"van der Holst","cited_arxiv_id":null,"evidence_quote":"Shows a positive semidefinite matrix with the strong Arnold property attains the connectivity bound, giving $\\nu(G)\\ge\\kappa(G)$ and hence Theorem 1.6."},{"cited_title":"Barioli, W","cited_arxiv_id":null,"evidence_quote":"Poses the weak graph complement conjecture in the form that Theorem 2.3 resolves, fixing the problem and its 'Question 2' formulation."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the self-complementary Matula graphs used in Remark 2.4 to show the connectivity-subgraph strategy cannot pass $\\tfrac32 n$."},{"cited_title":"Mitchell","cited_arxiv_id":null,"evidence_quote":"Supplies the degeneracy-to-nullity inequality $\\nu(G)\\ge n-2l(G^c)-1$ used in the conditional improvements of Section 3.1."}],"review_version":1}