An Extremal Problem for the Neighborhood Lights Out Game

Darren Parker; Lauren Keough

REVIEW 4 major objections 4 minor 15 references

An Extremal Problem for the Neighborhood Lights Out Game

T0 review · 4 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 1908.03649 v2 pith:KQE6VKRW submitted 2019-08-09 math.CO

Lauren Keough , Darren Parker This is my paper · ORCID

classification math.CO MSC 05C5705C3505C50

keywords LightsOutlight-switchinggamewinnabilityextremalgraphtheorylinearalgebraneighborhoodmatrixpendantgraphsgcdcondition

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

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.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Colleague,

I'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.

Now 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.

Soft 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.

Who 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.

Recommendation: send to review; expect a major revision.

Referee Report

4 major / 4 minor

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.

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 (4)

[§3, Corollary 3.6] 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.
[§3, Lemma 3.9] 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.
[§4, Proposition 4.5] 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.
[§4, Propositions 4.12–4.15] 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.

minor comments (4)

[§4, Proof of Proposition 4.4] The display 'max(n, ℓ) = (n 2) − n 2 + 1' is missing parentheses; it should read C(n,2)−(n/2+1).
[§3, Corollary 3.2] Corollary 3.2 refers to 'Lemma 3.1' when the result just proved is Theorem 3.1; the cross-reference should be updated.
[§4, beginning of Section 4.1] 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.
[§3, Lemma 3.4] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation chain; the paper's results are not equivalent to their inputs by construction.

full rationale

The paper introduces new machinery (the M-Lights Out game and toggling numbers) and derives its winnability criteria (Theorem 3.5, Lemma 3.9) from linear algebra over Z_l, independently of the extremal values being sought. The lower bounds are genuine constructions: kP4 ∪ (n/2-2k)P2 is a pendant graph whose N-winnability is computed from its size and order via toggling numbers, and the upper bounds are structural degree-sequence arguments. Citations to [GP13], co-authored by D.B. Parker, supply standard, externally checkable facts (e.g., P4 is N-AW and the characterization N(G)x = -b); these are not used to define the target quantity and are not load-bearing in a circular sense. No fitted parameter is renamed as a prediction; the parameter k in Conjecture 1.1 is defined from a gcd condition and then shown to match independent upper-bound arguments. I therefore find no step where a claimed prediction reduces by construction to its input. Separate correctness concerns, such as the apparent failure of Corollary 3.6 for P2, would be mathematical errors rather than circularity.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The paper introduces the M-Lights Out game and toggling numbers as new mathematical machinery, but no new physical entities or per-datum fitted parameters. The proofs rest on standard linear algebra over Z_l and on prior published Lights Out lemmas.

assumptions (3)

domain assumption P4 is N-AW for all l (GP13, Theorem 4.3)
Used in Corollary 3.2 and Theorem 3.1 to justify winnability manipulations on P4 components.
standard math Matrix invertibility over Z_l is equivalent to the determinant being a unit
Used throughout to convert game winnability to linear algebra (Brown 1993).
standard math Elementary row operations preserve invertibility over Z_l
Used to row-reduce neighborhood matrices into adjacency forms.

how reviews work

0 comments

Cite this review

Pith. "Pith review of An Extremal Problem for the Neighborhood Lights Out Game." pith.science (2026). https://pith.science/paper/KQE6VKRW

@misc{pith2026190803649,
  author       = {Pith},
  title        = {Pith review of: An Extremal Problem for the Neighborhood Lights Out Game},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/KQE6VKRW}},
  note         = {Machine review of arXiv:1908.03649}
}

abstract

Neighborhood Lights Out is a game played on graphs. Begin with a graph and a vertex labeling of the graph from the set $\{0,1,2,\dots, \ell-1\}$ for $\ell \in \mathbb{N}$. The game is played by toggling vertices: when a vertex is toggled, that vertex and each of its neighbors has its label increased by $1$ (modulo $\ell$). The game is won when every vertex has label 0. For any $n\in\mathbb{N}$ it is clear that one cannot win the game on $K_n$ unless the initial labeling assigns all vertices the same label. Given that the $K_n$ has the maximum number of edges of any simple graph on $n$ vertices it is natural to ask how many edges can be in a graph so that the Neighborhood Lights Out game is winnable regardless of the initial labeling. We find all such extremal graphs on $n$ vertices that have $\binom{n}{2} - c$ edges for $c\leq \lceil\frac{n}{2}\rceil +3$ and all those that have minimum degree $n-3$. The proofs of our results require us to introduce a new version of the Lights Out game that can be played given any square matrix.

Figures

Figures reproduced from arXiv: 1908.03649 by the authors.

**Figure 2.** The bowtie graph with degree sequence (4 [PITH_FULL_IMAGE:figures/full_fig_p022_2.png] view at source ↗

**Figure 3.** At left, the graph Gd9 - the non-matching component of the only graph with degree sequence d9 from Proposition 4.15 for which the two 3-vertices are not adjacent. At right, the graph G′ d9 - the non-matching component of only graph with degree sequence d9 in which the two 3-vertices are adjacent and have two neighbors in common in the proof of Proposition 4.15. complement is (N, ℓ)-AW if and only if gcd(n−7, ℓ) = 1 … view at source ↗

Figures from the paper (1 more)

**Figure 4.** Figure 4: The second possibility for a high degree component for deg [PITH_FULL_IMAGE:figures/full_fig_p025_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages

[1]

Anderson and T

M. Anderson and T. Feil, Turning lights out with linear algebra , Math. Mag. 71 (1998), 300--303

work page 1998
[2]

Arangala and M

C. Arangala and M. MacDonald, The 6 n five color Lights Out game , J. Recreat. Math. 38 (2014), 38--44

work page 2014
[3]

Arangala, M

C. Arangala, M. MacDonald, and R. Wilson, Multistate lights out , Pi Mu Epsilon J. 14 (2014), 9--18

work page 2014
[4]

Arangala, The 4 n multistate lights out game , Math

C. Arangala, The 4 n multistate lights out game , Math. Sci. Int. Res. J. 1 (2012), 10--13

work page 2012
[5]

Amin and P.J

A.T. Amin and P.J. Slater, Neighborhood domination with parity restrictions in graphs , Congr. Numer. 91 (1992), 19--30

work page 1992
[6]

Ballard, E

L. Ballard, E. Budge, and D. Stephenson, Lights out for graphs related to one another by constructions , Involve 12 (2019), 181--201

work page 2019
[7]

Brown, Matrices over Commutative Rings , Marcel Dekker, Inc., New York, 1993

W.C. Brown, Matrices over Commutative Rings , Marcel Dekker, Inc., New York, 1993

work page 1993
[8]

Craft, Z

D. Craft, Z. Miller, and D. Pritikin, A solitaire game played on 2-colored graphs , Discrete Math. 309 (2009), 188--201

work page 2009

Show all 15 references

[9]

Edwards, V

S. Edwards, V. Elandt, N. James, K. Johnson, Z. Mitchell, and D. Stephenson, Lights out on finite graphs , Involve 3 (2010), 17--32

2010
[10]

Goldwasser and W

J. Goldwasser and W. Klostermeyer, Maximization versions of ``lights out" games in grids and graphs , Congr. Numer. 126 (2007), 99--111

2007
[11]

Giffen and D.B

A. Giffen and D.B. Parker, On Generalizing the ``Lights Out'' Game and a Generalization of Parity Domination , Ars Combin. 111 (2013), 273--288

2013
[12]

87 (2014), no

Alessandra Graf, A new graceful labeling for pendant graphs, Aequationes Math. 87 (2014), no. 1-2, 135--145. 3175103

2014
[13]

Parker, and Vasily Zadorozhnyy, A Group Labeling Version of the Lights Out Game , To appear in Involve

Joseph Jones, D.B. Parker, and Vasily Zadorozhnyy, A Group Labeling Version of the Lights Out Game , To appear in Involve
[14]

Parker, The Lights Out Game on Subdivided Caterpillars , Ars Combin

D.B. Parker, The Lights Out Game on Subdivided Caterpillars , Ars Combin. 136 (2018), 347--356

2018
[15]

Sutner, The -game and cellular automata , Amer

K. Sutner, The -game and cellular automata , Amer. Math. Monthly 97 (1989), 24--34

1989

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

Anderson and T

M. Anderson and T. Feil, Turning lights out with linear algebra , Math. Mag. 71 (1998), 300--303

work page 1998

[2] [2]

Arangala and M

C. Arangala and M. MacDonald, The 6 n five color Lights Out game , J. Recreat. Math. 38 (2014), 38--44

work page 2014

[3] [3]

Arangala, M

C. Arangala, M. MacDonald, and R. Wilson, Multistate lights out , Pi Mu Epsilon J. 14 (2014), 9--18

work page 2014

[4] [4]

Arangala, The 4 n multistate lights out game , Math

C. Arangala, The 4 n multistate lights out game , Math. Sci. Int. Res. J. 1 (2012), 10--13

work page 2012

[5] [5]

Amin and P.J

A.T. Amin and P.J. Slater, Neighborhood domination with parity restrictions in graphs , Congr. Numer. 91 (1992), 19--30

work page 1992

[6] [6]

Ballard, E

L. Ballard, E. Budge, and D. Stephenson, Lights out for graphs related to one another by constructions , Involve 12 (2019), 181--201

work page 2019

[7] [7]

Brown, Matrices over Commutative Rings , Marcel Dekker, Inc., New York, 1993

W.C. Brown, Matrices over Commutative Rings , Marcel Dekker, Inc., New York, 1993

work page 1993

[8] [8]

Craft, Z

D. Craft, Z. Miller, and D. Pritikin, A solitaire game played on 2-colored graphs , Discrete Math. 309 (2009), 188--201

work page 2009