Pith. sign in

REVIEW 3 major objections 4 minor 30 references

On the forts and related parameters of the hypercube graph

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

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

Pith's one-line read The paper proves that every minimum fort of the hypercube graph Q_d is an open neighborhood of a vertex, except in dimension 4, where exactly one additional class of minimum forts appears.

desk verdict New and likely correct characterization of minimum hypercube forts, with a genuine Q4 surprise, but Proposition 3.7 has a load-bearing gap that needs referee attention. read the letter →

arxiv 2507.10826 v1 pith:4EN6MQE7 submitted 2025-07-14 math.CO

Boris Brimkov , Thomas R. Cameron , Owen Grubbs This is my paper
classification math.CO MSC 05C1505C3005C5705C76
keywords FortsHypercubegraphZeroforcingFailedCartesianproductPropagationtimeFortnumberFractional
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 a simple structural question: what are the smallest forts of the hypercube graph $Q_d$, where a fort is a nonempty set of vertices that no outside vertex meets in exactly one neighbor? It answers that question completely: for every dimension $d \ge 2$ except $d=4$, the minimum forts are exactly the open neighborhoods of single vertices, and each has size $d$. In dimension 4 there is a second family of minimum forts, all automorphic to one explicitly displayed set. From this characterization the paper derives the fractional zero forcing number $Z^*(Q_d)=2^d/d$ and bounds on the fort number that become equalities—matching the domination, total domination, and open packing numbers—when $d$ is a power of two. It also shows that minimum zero forcing sets of $Q_d$ are far from symmetric, since propagation times 1, 2, 3, and 4 can occur, and gives constructions of minimal forts in Cartesian products.

What carries the argument

The load-bearing mechanism is the hypercube's common-neighbor geometry. Proposition 3.2—two vertices whose open neighborhoods intersect share exactly two common neighbors—makes every open neighborhood $N(v)$ a fort and controls how many fort violations a new vertex can repair. Starting from a candidate pair, the proof counts the $2d$ violations contributed by $N(u) \cup N(v)$, then shows each added vertex resolves at most two of them; this counting forces a minimum fort either to be all of $N(v)$ or, in dimension 4 only, to be the exceptional Figure 2 set. The second machinery is the fort-cover linear program: Theorem 2.1 identifies zero forcing sets with fort transversals, so the characterization directly yields $Z^*(Q_d)$.

What would settle it

Enumerate all d-element subsets of V(Q_d) for d=5 (and if feasible d=6) and test the fort condition directly. Theorem 3.8 predicts that the only forts of size d are the 32 (respectively 64) open neighborhoods; any other d-element fort, especially one containing two vertices at distance 4, would disprove the characterization.

Watch

Extended reading notes

Core claim

In the paper's own terms, the discovery is Theorem 3.8: for $d \ge 2$ and $d \ne 4$, a subset $F$ of $V(Q_d)$ is a minimum fort if and only if $F = N(v)$ for some $v \in V(Q_d)$. Proposition 3.9 handles the remaining case $d=4$, where the minimum forts are exactly the open neighborhoods together with the automorphic images of the set in Figure 2. Corollary 3.10 then fixes the size of every minimum fort at $d$. The proof is a sequence of exclusions inside the hypercube: minimum forts contain no adjacent vertices, no vertices from both bipartition parts, no vertices at distance at least 6, and (for $d \ge 5$) no vertices at distance 4; what remains is a set whose vertices are pairwise at distance 2, i.e., the neighborhood of one vertex.

Load-bearing premise

The proof depends on the counting assumption that after choosing two vertices at distance 4, every further vertex added to the growing set repairs at most two of the remaining violations of the fort condition, and that for dimension at least 6 the necessary repairs force another pair of vertices at distance at least 6; if a cheaper repair existed, a minimum fort not equal to an open neighborhood could exist.

Editorial extensions

If this is right

  • For every $d \ge 2$ with $d \ne 4$, the minimum forts of $Q_d$ coincide with the open neighborhoods, and Corollary 3.10 fixes their size at $d$.
  • The fractional zero forcing number is $Z^*(Q_d)=2^d/d$ (Corollary 3.11), reproducing the known value through a complete structural description.
  • The fort number obeys $2^d/2^{\lfloor \log_2(d-1)\rfloor+1} \le ft(Q_d) \le 2^d/d$, and when $d=2^k$ the bounds coincide: $ft(Q_{2^k})$, $Z^*(Q_{2^k})$, $\gamma(Q_{2^k})$, $\gamma_t(Q_{2^k})$, and $\rho_o(Q_{2^k})$ all equal $2^{2^k-k}$ (Corollary 3.14).
  • Minimum zero forcing sets of $Q_d$ for $d \ge 4$ include examples with propagation times 1, 2, 3, and 4, which are therefore pairwise non-automorphic (Corollaries 4.2 and 4.3).
  • The Cartesian-product constructions of Theorems 5.1 and 5.3 enumerate all 14 minimal forts of $Q_3$ and produce 60 of the 348 minimal forts of $Q_4$, so a full census for higher dimensions remains open.

Reading between the lines

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

  • The same repair-counting strategy might transfer to other distance-regular bipartite graphs whose open neighborhoods have constant intersection sizes; the common-neighbor count is the only graph-specific input, so testing analogues such as folded hypercubes or grid graphs would show how far the mechanism generalizes.
  • The fort-number bounds leave a gap for dimensions that are not powers of two; one could try to construct disjoint neighborhoods meeting the lower bound more often, or search for a matching upper bound via a different dual of the fort-cover program.
  • Because the characterization makes all minimum forts explicit, the fort-cover inequalities for $Q_d$ become explicitly indexable; a natural follow-up, which the paper leaves open, is whether separating over hypercube forts can be done in polynomial time for zero-forcing integer programs.
  • The conjecture that $Q_d$ has minimum zero forcing sets realizing every propagation time from 1 to $2^{d-2}$ is checkable by search for $Q_5$ and $Q_6$; if correct, the non-automorphism phenomenon is much stronger than the four propagation times constructed here.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 4 minor

Summary. The paper studies forts in hypercube graphs and claims a complete classification of minimum forts: for every d ≠ 4 the minimum forts of Q_d are exactly the open neighborhoods of vertices, while for Q_4 they are the open neighborhoods together with the automorphic images of the set shown in Figure 2. From this characterization the paper derives that every minimum fort has cardinality d, that the fractional zero forcing number of Q_d is 2^d/d, and that for dimensions that are powers of two the fort number coincides with the domination number, total domination number, and open packing number. The paper also constructs non-automorphic minimum zero forcing sets of Q_d with propagation times 1 through 4 and gives general constructions for minimal forts of Cartesian products of graphs, with partial enumerations of minimal forts of Q_3 and Q_4.

Significance. The characterization, if correct, is a clean and structurally interesting result: in almost all hypercubes the minimum forts are exactly the open neighborhoods, with Q_4 as a single exceptional case. The paper is honest about the fact that Z*(Q_d) was already known, and it uses the fort characterization to give a new route to that value and to connect the fort number with domination-type parameters for power-of-two dimensions. The Cartesian product constructions in Section 5 are useful and are checked against explicit computational enumerations for Q_3 and Q_4. The main weakness is not the plausibility of the central theorem but the rigor of the proof: Proposition 3.7 needs an equality-case analysis before it can exclude size-d forts containing distance-4 pairs, and one lower-bound step in Corollary 3.11 is written incorrectly. I found no circular reasoning or misuse of the prior results cited in the paper.

major comments (3)
  1. [Section 3, Proposition 3.7] The proof of the strict bound |F| > d for d ≥ 5 is incomplete. After the two vertices p1 and p2 are added, there are 2d - 8 residual violations, so the lower bound |F| ≥ d follows; to obtain strictness for d ≥ 6 one must rule out the equality case in which exactly d - 4 further vertices are added, each resolving exactly two residuals. The text only analyzes the particular vertex w that is the common neighbor of two residual vertices in N(u), observes that d(w,v) = 6, and invokes Proposition 3.6. It does not classify the possible pairings of residual vertices, nor does it analyze the new violations created by the added repair vertices. For example, for d = 6 one must also rule out pairing the two residual vertices in N(v), which gives a vertex at distance 6 from u, and one must rule out mixed pairings. Without this equality-case analysis, a size-d fort containing a distance-4 pair is not excluded, and Theorem 3.8 would not be established. In the d = 5 paragraph, the statement that at least four vertices must be added is asserted without proof; the desired strict inequality would already follow from the fact that the two remaining residuals cannot be resolved by a single added vertex.
  2. [Corollary 3.11] The proof of the lower bound Z*(Q_d) ≥ 2^d/d is not valid as written. From the fact that every minimum fort has size d it does not follow that 'no weighting of less than 1/d on a vertex will suffice': weights need not be uniform, and a vertex could receive more than 1/d while another receives less. The conclusion is true, but it requires an averaging argument: summing the constraints sum_{v in N(x)} w(v) ≥ 1 over all 2^d neighborhoods N(x) counts each vertex exactly d times and yields d * sum_v w(v) ≥ 2^d. The text should replace the quoted sentence with this or an equivalent derivation.
  3. [Theorem 3.8, proof] The final step 'all vertices in F are a distance of 2 apart from each other, which means F is the neighborhood of a single vertex' is asserted without proof. This is true for a fort of size d in Q_d, but the proof needs the extra facts that a set of d pairwise-distance-2 vertices in Q_d must be a full neighborhood of some vertex, and that no proper subset of a neighborhood is itself a fort. As written, the characterization relies on an unstated lemma.
minor comments (4)
  1. [Page 5, after Proposition 3.2] The text says 'Note that Corollary 3.2 states...' but the referenced result is Proposition 3.2, not a corollary.
  2. [Section 6, conclusion] The conclusion states that 'Theorem 5.2 establishes that F x F' is a minimal fort of G box G''; this is inaccurate because Theorem 5.2 constructs a fort, not generally the Cartesian product and not minimality, while minimality is the content of Theorems 5.1 and 5.3.
  3. [Theorem 5.1, proof, Case 2] The equality N_{\hat G}((u,u')) cap \hat S = {(u,v')} is claimed for each u in V(G), but for u outside F this need not hold if u has neighbors in F. The subsequent argument only needs the displayed equality for u in F, so the statement should be restricted accordingly.
  4. [Proposition 3.9] The sentence 'All sets F of this form are automorphic to the set in Figure 2' is too terse; a brief argument that the automorphism group of Q_4 is transitive on such configurations would make the proof self-contained.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the minimum-fort characterization of Q_d is derived from definitions and independent propositions, not from its conclusion.

full rationale

The central claim (Theorem 3.8) is not assumed anywhere. Neighborhoods are shown to be forts in Proposition 3.3 by direct counting of common neighbors, and the lower-bound machinery (Propositions 3.4-3.7) is built from bipartiteness, degree, and common-neighbor facts. No parameter is fitted, and no prediction is defined in terms of the target result. The self-citations [7], [8], and [13] are used for background, for the general fort-cover model, for the known inequality ft(G) <= Z*(G) <= Z(G), and for a product-of-forts lemma; none of these inputs contains Theorem 3.8 or Corollary 3.10, and the fractional zero forcing number of Q_d is disclosed as already known in [13, Proposition 3.15] but is re-derived from the paper's own characterization in Corollary 3.11. The use of Proposition 3.6 inside Proposition 3.7 is not circular because Proposition 3.6 is proved earlier from the fact that neighborhoods are forts. The proof of Proposition 3.7 contains an unquantified equality-case argument for d >= 5, so that part may be a rigor gap, but a gap in an independent proof is a correctness issue, not circularity: no equation in the paper reduces to its own input by construction.

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

No fitted constants or ad hoc objects are introduced. The paper's claims rest on standard hypercube facts and a few cited external results ([6] and [13]); all central derivations are self-contained combinatorial counting. The only non-empirical assumptions are the cited hypercube parameters.

assumptions (6)
  • domain assumption Vertices of Q_d are binary d-vectors with adjacency by Hamming distance 1, the Boolean lattice representation.
    Used throughout Section 3 to analyze neighborhoods, distances, and bipartition.
  • standard math In Q_d, two vertices at distance k have k! distinct shortest paths (Proposition 3.1, cited to [19]).
    Used in Proposition 3.2 to show common neighbors of a pair come in pairs.
  • standard math Z(Q_d) = 2^(d-1) and pt(Q_d) = 1 (cited to [3] and [22]).
    Used in Section 4 to identify constructed sets as minimum zero forcing sets.
  • standard math Open packing number of Q_d satisfies rho_o(Q_d) >= 2^(d - floor(log2(d-1)) - 1) (cited to [6, Theorem 3.2]).
    Used in Corollary 3.12 for the lower bound on ft(Q_d).
  • standard math For k in N, rho_o(Q_{2^k}) = gamma(Q_{2^k}) = gamma_t(Q_{2^k}) = 2^(2k - k) (cited to [6]).
    Used in Corollary 3.14 for equality of five graph parameters.
  • standard math If F is a fort of G and F' is a fort of G', then F x F' is a fort of G square G' (cited to [13, Proposition 4.1]).
    Used in Theorem 5.1 and the Section 5 constructions.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On the forts and related parameters of the hypercube graph." pith.science (2026). https://pith.science/paper/4EN6MQE7

@misc{pith2026250710826,
  author       = {Pith},
  title        = {Pith review of: On the forts and related parameters of the hypercube graph},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4EN6MQE7}},
  note         = {Machine review of arXiv:2507.10826}
}
read the original abstract

In 2018, forts were defined as non-empty subsets of vertices in a graph where no vertex outside the set has exactly one neighbor in the set. Forts have since been used to characterize zero forcing sets, model zero forcing as an integer program, and provide lower bounds on the zero forcing number. In this article, we give a complete characterization of minimum forts in the hypercube graph, showing that they are automorphic to one of two sets. In contrast, non-automorphic minimum zero forcing sets are identified with distinct propagation times. We also derive the fractional zero forcing number and bounds on the fort number of the hypercube. When the hypercube's dimension is a power of two, the fort number and fractional zero forcing number are equal to the domination number, total domination number, and open packing number. Lastly, we present general constructions for minimal forts in the Cartesian product of graphs, reflecting some minimal forts of the hypercube.

Figures

Figures reproduced from arXiv: 2507.10826 by the authors.

Figure 1
Figure 1. A minimal fort (white) of Q3 that contains adjacent vertices. Proposition 3.4. Let d ≥ 2. Then, no minimum fort of Qd contains adjacent vertices. Proof. Let F = {u, v} ⊂ V (Qd), where u and v are adjacent. Note that F is not a fort of Qd. Indeed, since u and v are adjacent, Observation 2.4 implies that N(u) ∩ N(v) = ∅ and every w ∈ N(u) ∪ N(v) satisfies |N(w) ∩ F| = 1. Hence, by Observation 2.2, there are |N(u) ∪ N(… view at source ↗
Figure 2
Figure 2. A minimum fort (white) of Q4 that is not the neighborhood of a single vertex. Theorem 3.8. Let d ≥ 2, d ̸= 4, and F ⊆ V (Qd). Then, F is a minimum fort of Qd if and only if F = N(v) for some v ∈ Qd. Proof. Suppose that F is a minimum fort of Qd. Then, by Proposition 3.5, F only contains vertices that are an even distance apart from each other. By Proposition 3.6, F does not contain vertices that are a distance of 6 … view at source ↗
Figure 3
Figure 3. Minimum zero forcing sets of Q3 shown in gray, with propagation time 1 (left) and propagation time 2 (right). The following proposition shows how to construct minimum zero forcing sets of Qd+1 that have the same propagation time as a minimum zero forcing set of Qd. Proposition 4.1. Let S be a minimum zero forcing set of Qd with propagation time k. Then, there exists a minimum zero forcing set of Qd+1 with propagatio… view at source ↗
Figures from the paper (5 more)
Figure 4
Figure 4. Figure 4: Minimum zero forcing sets of Q4 shown in gray, with propagation time 1 (left) and propagation time 2 (right). 0011 1101 1001 0001 1010 0000 0100 0010 0101 1011 0111 1111 1000 1110 1100 0110 1111 1101 1001 0001 1010 0000 0100 0010 0011 0101 1011 0111 1000 1110 1100 0110…
Figure 5
Figure 5. Figure 5: Minimum zero forcing sets of Q4 shown in gray, with propagation time 3 (left) and propagation time 4 (right). In addition, Q4 has minimum zero forcing sets with propagation time 3 and 4, see [PITH_FULL_IMAGE:figures/full_fig_p012_5.png]
Figure 6
Figure 6. Figure 6: A non-minimal fort (white) of Q4 constructed from F × F ′ , where F ′ = V (Q1) and F is the minimal fort of Q3 shown in [PITH_FULL_IMAGE:figures/full_fig_p013_6.png]
Figure 7
Figure 7. Figure 7: A minimal fort (white) where each vertex in the fort has at least one neighbor in [PITH_FULL_IMAGE:figures/full_fig_p015_7.png]
Figure 8
Figure 8. Figure 8: A minimal fort of Q4 not attained via the constructions in Proposition 3.3, Theo￾rem 5.1, nor Theorem 5.3. 6 Conclusion This article provides a comprehensive characterization of the minimum forts of the hypercube graph Qd. Specifically, Theorem 3.8 establishes that for…

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

30 extracted references · 29 canonical work pages

  1. [1]

    Aazami , Hardness results and approximation algorithms for some problems on graphs, University of Waterloo, 2008

    A. Aazami , Hardness results and approximation algorithms for some problems on graphs, University of Waterloo, 2008

    work page 2008

  2. [2]

    Afzali, A.H

    F. Afzali, A.H. Ghodrati, and H.R. Maimani , Failed zero forcing numbers of Kneser graphs, Johnson graphs, and hypercubes, J. Appl. Math. Comput. , 70:2665– 2675, 2024

    work page 2024

  3. [3]

    AIM Minimum Rank – Special Graphs Work Group , Zero forcing sets and the minimum rank of graphs, Linear Algebra Appl., 428:1628–1648, 2008

    work page 2008

  4. [4]

    Azarija, M.A

    J. Azarija, M.A. Henning, and S. Klav ˇzar, (Total) Domination in Prisms, Electron. J. Combin. , 24(1):19, 2017

    work page 2017

  5. [5]

    Bertolo, P.R.J

    R. Bertolo, P.R.J. ¨Osterg˚ard, and W.D. Weakley An Updated Table of Binary/ternary Mixed Covering Codes, J. Combin. Des. , 12:157-176, 2004. 17

    work page 2004

  6. [6]

    Breˇsar, S

    B. Breˇsar, S. Klavˇzar, D.F. Rall Packings in bipartite prisms and hypercubes, Discrete Math., 347:113875, 2024

    work page 2024

  7. [7]

    Brimkov, C.C

    B. Brimkov, C.C. F ast, and I.V. Hicks, Computational approaches for zero forcing and related problems, European J. Oper. Res., 273(3):889–903, 2019

    work page 2019

  8. [8]

    Brimkov, D

    B. Brimkov, D. Mikesell, and I.V. Hicks , Improved computational approaches and heuristics for zero forcing, INFORMS J. Comput. , 33(4):1384-1399, 2021

    work page 2021

Show all 30 references
  1. [9]

    Brimkov, J

    B. Brimkov, J. Carlson, I.V. Hicks, R. Patel, and L. Smith, Power domination throttling, Theoret. Comput. Sci. , 795:142–153, 2019

    2019

  2. [10]

    Brueni and L.S

    D.J. Brueni and L.S. Heath , The PMU placement problem, SIAM J. Discrete Math., 19(3):744–761, 2005

    2005

  3. [11]

    Burgarth and V

    D. Burgarth and V. Giovannetti, Full control by locally induced relaxation, Phys. Rev. Lett., 99:100501, 2007

    2007

  4. [12]

    Butler and M

    S. Butler and M. Young, Throttling zero forcing propagation time speed on graphs, Australas J. Combin. , 57:65–71, 2013

    2013

  5. [13]

    Cameron, L

    T.R. Cameron, L. Hogben, F.H.J. Kenter, S.A. Mojallal, and H. Schuerger, Forts, (fractional) zero forcing, and Cartesian products of graphs, arXiv:2310.17904 [math.CO] , 2023

    2023

  6. [14]

    Carlson and J

    J. Carlson and J. Kritschgau , Various characterizations of throttling numbers, Discrete Appl. Math. , 294:85–97, 2021

    2021

  7. [15]

    Chilakamarri, N

    K. Chilakamarri, N. Dean, C.X. Kang, and E. Yi , Iteration index of a zero forcing set in a graph, Bull. Inst. Combin. Appl. , 64:57–72, 2012

    2012

  8. [16]

    Erd˝os and R.K

    P. Erd˝os and R.K. Guy, Crossing Number Problems, Amer. Math. Monthly, 80:52– 58, 1973

    1973

  9. [17]

    F ast and I.V

    C.C. F ast and I.V. Hicks, Effects of vertex degrees on the zero-forcing number and propogation time of a graph, Discrete Appl. Math. , 250:215–226, 2018

    2018

  10. [18]

    Fetci, B

    K. Fetci, B. Jacob, and D. Saavedra, The failed zero forcing number of a graph, Involve, 8(1):99–117, 2015

    2015

  11. [19]

    Foldes, A characterization of hypercubes, Discrete Math., 17(2):155–159, 1977

    S. Foldes, A characterization of hypercubes, Discrete Math., 17(2):155–159, 1977

    1977

  12. [20]

    Gomez, K

    L. Gomez, K. Rubi, J. Terrazas, and D.A. Narayan , All graphs with a failed zero forcing number of two, Symmetry, 13(11):2221, 2021

    2021

  13. [21]

    Gomez, K

    L. Gomez, K. Rubi, J. Terrazas, and D.A. Narayn , Failed zero forcing number of trees and circulant graphs, Theory and Applications of Graphs , 11(1):5, 2025

    2025

  14. [22]

    Hogben, M

    L. Hogben, M. Huynh, N. Kingsley, S. Meyer, S. W alker, and M. Young , Propagation time for zero forcing on a graph, Discrete Appl. Math., 160(13):1994–2005, 2012. 18

    1994

  15. [23]

    Hogben, J.C.-H

    L. Hogben, J.C.-H. Lin, and B. Shader , Inverse Problems and Zero Forcing for graphs, Mathematical Surveys and Monographs 270, American Mathematical Society, Providence, RI, 2022

    2022

  16. [24]

    Jenssen, W

    M. Jenssen, W. Perkins, and A. Potukuchi , Independent sets of a given size and structure in the hypercube, Combin. Probab. Comput. 31(4):702-720, 2022

    2022

  17. [25]

    Kaudan, R

    C. Kaudan, R. Taylor, D.A. Narayan , An inverse approach for finding graphs with a failed zero forcing number of k, Mathematics 11(19):4068, 2023

    2023

  18. [26]

    Mirafzal , On the distance-transitivity of the folded hypercube, Commun

    S.M. Mirafzal , On the distance-transitivity of the folded hypercube, Commun. Comb. Optim. 10(1):207–217, 2025

    2025

  19. [27]

    Severini, Nondiscriminatory propagation on trees, J

    S. Severini, Nondiscriminatory propagation on trees, J. Phys. A, 41(48):482002, 2008

    2008

  20. [28]

    Shitov, On the complexity of failed zero forcing, Theoret

    Y. Shitov, On the complexity of failed zero forcing, Theoret. Comput. Sci. , 660:102– 104, 2017

    2017

  21. [29]

    Swanson and E

    N. Swanson and E. Ufferman, A lower bound on the failed zero-forcing number of a graph, Involve, 16(3):493–504, 2023

    2023

  22. [30]

    West, Introduction to Graph Theory, 2nd ed

    D. West, Introduction to Graph Theory, 2nd ed. , Prentice Hall, Upper Saddle River, NJ, 2001. 19

    2001

Pith tools

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