{"id":"0b169155-4c7a-4b77-aca2-6675da2bf77a","arxiv_id":"1908.03649","paper_version":2,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"For the Neighborhood Lights Out game, the paper finds the maximum edge count of n-vertex graphs that are winnable from every labeling, for all odd-parity cases and partial even-even cases.","lead":"This math paper asks how many edges a graph can have while the Neighborhood Lights Out game is winnable from every starting label pattern. It gives exact extremal numbers for all cases where at least one of n and the label count is odd, and partial results for the even-even case.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Corollary 3.6 and Lemma 3.9 are false for P2, so the lower-bound and classification proofs for the main theorems collapse.","rationale":"The reader's weakest assumption identifies exactly the load-bearing fault: Corollary 3.6 is false, and the concrete counterexample P2 is decisive. Because Lemma 3.9 is derived from Corollary 3.6 and is then used in the extremal lower-bound and classification arguments, the main theorems are not supported by the written proof. I see no need to manufacture a different concern. The review should remain a rejection of the paper in its current form, while acknowledging that a corrected version excluding P2 or fixing the complement-bar omissions might rescue some results.","tokens_in":25383,"tokens_out":8570,"duration_ms":83747,"concrete_test":"Compute N(P2) over Z_2 (or any Z_ℓ) and verify that its determinant is 0, while the criterion in Lemma 3.9 gives gcd(2(2-1)-1,ℓ)=1. Also check the n=4, ℓ=2 lower-bound graph from Proposition 4.5: the sparse graph 2P2 has block-diagonal neighborhood matrix with two J2 blocks, hence is singular, although Lemma 3.9 predicts it is N-AW. This directly localizes the failing step.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central results depend on Corollary 3.6 and Lemma 3.9, which assert a criterion for when a pendant graph is N-winnable. The criterion fails already for P2. P2 is the pendant graph K1⊙K1, with n=2 and m=1; Lemma 3.8 gives T_A(G)_V(G)(1)={-2}, so Lemma 3.9 predicts P2 is N-AW because gcd(2(2-1)-1,ℓ)=gcd(1,ℓ)=1. But N(P2)=[[1,1],[1,1]] has determinant 0 over every Z_ℓ, so P2 is never N-AW. The same contradiction invalidates Corollary 3.6. This is not a peripheral slip: Lemma 3.9 is used to prove the lower bound in Proposition 4.5 and to certify the extremal examples in Propositions 4.12, 4.14, and 4.15, and hence Theorem 4.10. The proof also drops complement bars throughout: for example, Proposition 4.5 describes kP4∪(n/2-2k)P2 as having size C(n,2)-(n/2+k), which is false for that sparse graph; the intended statement must be about its complement. As written, the submitted argument does not establish the claimed theorems, even though a repaired version might salvage some of them.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the Neighborhood Lights Out game on n-vertex graphs with labels in Z_l. It introduces max(n,l), the maximum number of edges of an n-vertex graph that is N-always-winnable, and aims to classify the extremal graphs. The main results are: for odd n, max(n,l)=C(n,2)-floor(n/2) for all l with unique extremal graph the complement of a near-perfect matching; for even n and odd l, max(n,l) is C(n,2)-n/2 when gcd(n-1,l)=1 and C(n,2)-(n/2+1) otherwise; for n and l both even, a conjecture asserts max(n,l)=C(n,2)-(n/2+k) where k is the least nonnegative integer with gcd(n-2k-1,l)=1, and the paper proves this for k=0,1,2,3. The proofs introduce an M-Lights Out game for arbitrary matrices, and develop criteria for winnability of pendant graphs in terms of toggling numbers.","tokens_in":75,"tokens_out":6523,"duration_ms":130105,"significance":"If the main theorem were correct, the paper would give a clean extremal classification for a natural variant of Lights Out and would provide strong evidence for Conjecture 1.1. The matrix-game framework and the systematic use of toggling numbers are attractive and potentially reusable. The paper is self-contained, carefully introduces its notation, and contains many explicit extremal examples. However, the central proof chain rests on a winnability criterion that is false, already for the smallest pendant graph P2. Because that false criterion is used to certify the lower-bound constructions and the extremal examples, the main theorems are not established by the submitted argument. The paper also systematically conflates a sparse pendant forest with its complement, so several size computations and winnability claims are not even internally coherent as written. A repaired version might salvage parts of the classification, but the present manuscript does not support its claims.","major_comments":[{"comment":"Corollary 3.6 is false. Let G=P2, which has a pendant vertex and is A-always-winnable for every l because its adjacency matrix [[0,1],[1,0]] is invertible over Z_l. Lemma 3.8(2) with H=K1 gives T_A(G)_V(G)(1)={-2}, so 1+t=-1 and gcd(1+t,l)=1. Corollary 3.6 therefore predicts that P2 is N-always-winnable. But N(P2)=[[1,1],[1,1]] has determinant 0 over every Z_l, so P2 has no winning strategy for labelings with distinct labels. The error lies in applying Theorem 3.5(2) with the implicit assumption that the conditions (2a) and (2b) are equivalent to N-winnability for all pendant graphs; the P2 example shows that the theorem as used, or its application in Corollary 3.6, is not valid.","section":"§3, Corollary 3.6"},{"comment":"Lemma 3.9 is false for the same reason. For G=P2, n=2 and m=1, the asserted criterion gives gcd(2[n-m]-1,l)=gcd(1,l)=1, so the lemma claims P2 is N-always-winnable; this is contradicted by the singular neighborhood matrix of P2. Since Lemma 3.9 is used directly in Proposition 4.5 to establish the lower bound in the even-even case, and in Propositions 4.12, 4.14, and 4.15 to certify the proposed extremal graphs, the proof chain leading to Theorem 4.10 collapses. The lemma cannot be repaired by excluding P2 alone, because the statement is also used for pendant forests containing P2 components throughout Section 4.","section":"§3, Lemma 3.9"},{"comment":"Proposition 4.5, as written, defines G = kP4 ∪ (n/2−2k)P2 and claims that G has size C(n,2)−(n/2+k). This is false: the disjoint union has size n/2, not a number near C(n,2). The proof appears to intend the complement of this pendant forest, but no complement operation is written. The same missing-complement pattern occurs in Proposition 4.12, where H = P4 ∪ (n/2−2)P2 is said to have n/2+1 edges even though the literal graph has n−1 edges. These are not cosmetic typos: the size computations are load-bearing for the claimed lower bounds and for the announced extremal sizes.","section":"§4, Proposition 4.5"},{"comment":"The extremal classifications in Propositions 4.12, 4.14, and 4.15 depend on Lemma 3.9 to assert that the proposed graphs are N-always-winnable exactly under the stated gcd conditions. Since Lemma 3.9 is false, these assertions are unsupported. In addition, the statements describe the extremal graphs as 'pendant graphs of order n and size n/2+k' while the theorem in which they are used concerns complements of pendant graphs; the missing complements make the propositions internally inconsistent. A correct proof would need to re-derive the winnability of the dense complements without relying on the false criterion.","section":"§4, Propositions 4.12–4.15"}],"minor_comments":[{"comment":"The display 'max(n, ℓ) = (n 2) − n 2 + 1' is missing parentheses; it should read C(n,2)−(n/2+1).","section":"§4, Proof of Proposition 4.4"},{"comment":"Corollary 3.2 refers to 'Lemma 3.1' when the result just proved is Theorem 3.1; the cross-reference should be updated.","section":"§3, Corollary 3.2"},{"comment":"The sentence 'Recall we can assume n and ℓ are even' is not justified at that point; the parity cases are handled earlier by Propositions 4.2–4.4, but the reader has to reconstruct that this paragraph is restricted to the remaining case.","section":"§4, beginning of Section 4.1"},{"comment":"In the proof of Lemma 3.4(1), the phrase 'we begin toggling the vertices as we would to win the adjacency game on G′ with labeling π′' is clear, but the following sentence 'This leaves each vertex in V(G′)−U with label 0 and each vertex in U with label π(p)' depends on the toggles from U being applied; the wording is slightly compressed and could be clarified.","section":"§3, Lemma 3.4"}],"recommendation":"reject","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nI'd want to know one thing immediately: the central criterion for N-winnability of pendant graphs is false, and the counterexample is the simplest possible graph, P2. Corollary 3.6 says that if G is A-AW with a pendant vertex and t in T^A_V(G)(1), then G is N-AW exactly when gcd(1+t, ell)=1. For P2, t=-2, so 1+t ≡ -1, gcd is 1 for every ell; the corollary predicts P2 is N-AW for all ell. But N(P2)=[[1,1],[1,1]], determinant 0 over every Z_ell, so by the paper's own Lemma 2.2 P2 is never N-AW. Lemma 3.9, which converts size and order into this criterion, carries the same error. That invalidates Proposition 4.5's lower bound and the extremal certifications in Propositions 4.12, 4.14, and 4.15, which are the engine of Theorem 4.10. The misstatement isn't peripheral; the main classifications rest on it.\n\nNow the credit. The extremal problem itself is new and natural: how many edges can a graph have and still be N-AW for all labelings? The M-Lights Out framework, playing the game for an arbitrary matrix and using row equivalence, is a clean generalization that should be useful elsewhere. The odd-n result and the perfect/near-perfect matching cases use Theorem 2.4 (one dominating vertex reduces N-winnability to A-winnability) and might survive without Lemma 3.9. The linear algebra over Z_ell is careful, and the citations to prior Lights Out work look appropriate.\n\nSoft spots beyond the false lemma: the paper repeatedly drops complement bars. Proposition 4.5 defines G as kP4 ∪ (n/2-2k)P2 and claims it has size binom(n,2)-(n/2+k); that sparse graph actually has size n/2+k. The intended graph is its complement. This isn't a typo in one line; it is the same argument that leans on Lemma 3.9, so the proof chain as written doesn't establish the claimed theorems. There are also smaller slips (e.g., a sign error in the displayed formula in Proposition 4.4's proof), but those aren't load-bearing.\n\nWho should read this? Anyone working on light-switching games or extremal graph theory with linear-algebra constraints. The framework is worth borrowing; the results are plausible and may be repairable. As submitted, though, it doesn't support its conclusions. It deserves a serious referee, not a desk reject, because the core question and machinery are legitimate and the flaw is specific enough to fix.\n\nRecommendation: send to review; expect a major revision.","headline":"The paper asks a good new extremal question and builds a useful framework, but a false lemma about pendant graphs (P2 is the counterexample) breaks the lower-bound and classification proofs.","tokens_in":68,"tokens_out":5600,"would_cite":false,"duration_ms":54459,"reading_group":"maybe","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C57","05C35","05C50"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper determines how many edges an $n$-vertex graph can have while still guaranteeing a win in the neighborhood Lights Out game for every initial labeling, and classifies the extremal graphs.","keywords":["Lights Out","light-switching game","winnability","extremal graph theory","linear algebra","neighborhood matrix","pendant graphs","gcd condition"],"falsifier":"Apply the criterion to the single-edge graph $P_2$: its neighborhood matrix is the all-ones $2\\times 2$ matrix, which is singular over every $\\mathbb{Z}_\\ell$, so $P_2$ is never N-winnable, yet the criterion with $t=-2$ gives $\\gcd(1+t,\\ell)=\\gcd(-1,\\ell)=1$; checking this mismatch settles whether the pendant-vertex criterion is valid as stated.","tokens_in":25060,"feed_emoji":"💡","tokens_out":19437,"duration_ms":175674,"temperature":0.7,"pith_summary":"The paper asks how many edges an $n$-vertex graph can have while still guaranteeing a win in the neighborhood Lights Out game under every initial labeling, and identifies the graphs that achieve this maximum. It gives the full answer when $n$ is odd and when $n$ is even and the label modulus $\\ell$ is odd. For $n$ and $\\ell$ both even it proves the conjectured formula in the first four cases, namely for $k=0,1,2,3$ where $k$ is the smallest nonnegative integer with $\\gcd(n-2k-1,\\ell)=1$. The extremal value is governed by a gcd condition, and the classification runs through complements of pendant graphs, with one exceptional extremal family when $n$ is even and $\\ell$ is odd.","feed_headline":"Odd-n Lights Out: densest winning graph is a near-perfect matching","feed_subtitle":"Even orders add a gcd condition; the sole exception is a triangle with disjoint edges.","key_machinery":"The central mechanism is a matrix version of Lights Out: for any square matrix $M$ over $\\mathbb{Z}_\\ell$, toggling $v_j$ adds column $j$ to the label vector, and 'always winnable' is exactly invertibility of $M$. The paper turns a dense graph's neighborhood matrix into a sparse adjacency matrix by row operations, then studies graphs with pendant vertices through toggling numbers $T_U^A(r)$, the set of total toggles from $U$ needed to win the adjacency game on the constant labeling $0_{U,r}$. For a pendant graph of size $m$ and order $n$, this reduces N-winnability to the gcd condition $\\gcd(2(n-m)-1,\\ell)=1$, which becomes $\\gcd(n-2k-1,\\ell)=1$ for the complements at the conjectured extremal sizes.","core_discovery":"On the paper's own terms, the central discovery is a classification of the densest graphs that are winnable for every initial labeling. For odd $n$, every such extremal graph is the complement of a near-perfect matching and $\\max(n,\\ell)=\\binom{n}{2}-\\lfloor n/2\\rfloor$. For even $n$ and odd $\\ell$, the maximum is $\\binom{n}{2}-n/2$ when $\\gcd(n-1,\\ell)=1$, and otherwise $\\binom{n}{2}-(n/2+1)$, with $C_3\\cup \\frac{n-4}{2}P_2\\cup K_1$ as an extremal graph. For $n$ and $\\ell$ both even, the paper proves that $\\max(n,\\ell)=\\binom{n}{2}-(n/2+k)$, where $k$ is the smallest nonnegative integer with $\\gcd(n-2k-1,\\ell)=1$, for $0\\le k\\le 3$, and that the extremal graphs in those cases are exactly the complements of pendant graphs of the corresponding size.","pith_inferences":["The matrix game introduced here does not require $M$ to be symmetric, so the same row-reduction strategy could be carried over to the adjacency (open-neighborhood) Lights Out game and to directed graphs without changing the formalism.","If Conjecture 1.1 holds for all $k$, the extremal problem for even $n$ and $\\ell$ reduces to a number-theory question: the answer is the smallest $k$ for which $n-2k-1$ is coprime to $\\ell$.","The replacement principle in Corollary 3.11 is a general compression rule—any component can be swapped for another with the same order and toggling number—so it could serve as a pruning step in computational searches for extremal graphs."],"forward_implications":["For odd $n$, the maximum edge count is exactly $\\binom{n}{2}-\\lfloor n/2\\rfloor$, and the complement of a near-perfect matching is the unique graph attaining it.","For even $n$ and odd $\\ell$, the extremal value is determined entirely by whether $\\gcd(n-1,\\ell)=1$; when it is not, a triangle with disjoint edges and an isolated vertex is extremal.","For even $n$ and $\\ell$, the conjectured formula is confirmed for $k=0,1,2,3$, so in those ranges the only extremal graphs are complements of pendant graphs such as $P_4\\cup\\frac{n-4}{2}P_2$, $(P_3\\odot K_1)\\cup\\frac{n-6}{2}P_2$, and their counterparts from the classification.","The same graph can be winnable for one modulus $\\ell$ and unwinnable for another, because winnability turns on coprimality with $\\ell$ rather than on the graph alone."],"supporting_citations":[{"why":"Supplies the linear-algebra model of Lights Out winnability and the fact that $P_4$ is N-always-winnable, which the density-leap argument uses.","marker":"[GP13]"},{"why":"Gives the basic matrix equation $N(G)x=-b$ that turns the game into an invertibility question.","marker":"[AF98]"},{"why":"Defines the sigma-game/adjacency game whose winnability the paper reduces neighborhood winnability to.","marker":"[Sut89]"},{"why":"Provides the criterion that a matrix over $\\mathbb{Z}_\\ell$ is invertible exactly when its determinant is a unit, justifying row-reduction arguments.","marker":"[Bro93]"},{"why":"Introduces the $H\\odot K_1$ pendant graph construction and terminology used for the extremal candidates.","marker":"[Gra14]"}],"fun_headline_variants":["Odd n Lights Out: densest winning graphs are complements of near-perfect matchings","Lights Out densest graphs: odd n near-perfect matchings, even n gcd condition","Max edges for always-winnable Lights Out: near-complete graphs found","New matrix Lights Out game solves extremal graph problem","Even n Lights Out max edges depend on gcd conditions"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is the pendant-vertex criterion in Theorem 3.5(2) and Corollary 3.6, which says a graph with a pendant vertex is N-winnable exactly when its adjacency-game toggling numbers satisfy the stated gcd condition; the extremal classifications inherit any exception to that criterion.","fun_headline_variants_meta":{"raw":{"variants":["Odd n Lights Out: densest winning graphs are complements of near-perfect matchings","Lights Out densest graphs: odd n near-perfect matchings, even n gcd condition","Max edges for always-winnable Lights Out: near-complete graphs found","New matrix Lights Out game solves extremal graph problem","Even n Lights Out max edges depend on gcd conditions"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001294,"raw_usage":{"total_tokens":5311,"prompt_tokens":1005,"completion_tokens":4306,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":621,"completion_tokens_details":{"reasoning_tokens":4209}},"tokens_in":621,"tokens_out":4306,"duration_ms":33607,"temperature":1.0,"reasoning_tokens":4209,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:12:23.911655+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Apply the criterion to the single-edge graph $P_2$: its neighborhood matrix is the all-ones $2\\times 2$ matrix, which is singular over every $\\mathbb{Z}_\\ell$, so $P_2$ is never N-winnable, yet the criterion with $t=-2$ gives $\\gcd(1+t,\\ell)=\\gcd(-1,\\ell)=1$; checking this mismatch settles whether the pendant-vertex criterion is valid as stated.","supporting_citations":[],"review_version":1}