is_zero_forcing_set
def
A set of vertices S is a zero forcing set of G if its zero forcing closure contains all vertices of G.
Statement
def is_zero_forcing_set {V : Type*} (G : SimpleGraph V) (S : Set V) : Prop
- Defined in
- arXiv:2611.11352 Section 1
- Verified
- 10 Nov 2026
- Axioms
- none listed
- Built on 1
- ZeroForcedThe zero forcing closure of an initial set S of blue vertices in G under the color change rule.
- Used by 30
- univ_is_zero_forcing_setThe full set of vertices of any graph G is a zero forcing set.
- tree_zero_forcing_complements_not_two_extendibleThere is a tree on nine vertices whose complements of zero forcing sets are not two-extendible.
- is_total_forcing_setA total forcing set is a zero forcing set that induces a subgraph with no isolated vertices.
- root_exposed_fort_iff_new_white_leaf_breaks_forcingIf the complement of W is a zero forcing set of G, then W contains a root-exposed fort exactly when the same originally blue vertices fail…
- gt_total_forcing_poly_eqFor every integer t ≥ 24, the total forcing polynomial of gt_graph t is equal to the zero forcing polynomial of gt_graph t.
- star_graph_zero_forcing_poly_unimodalFor every natural number n, the complete bipartite graph K_{1, n} on Unit ⊕ Fin n has a unimodal zero forcing polynomial.
- zero_forcing_complements_two_extendibleComplements of zero forcing sets have the two-extendibility property: whenever A is contained in B, x is outside B, and A, B and A union…
- tree_zero_forcing_poly_lower_half_monotoneFor any finite tree $T$ on a finite vertex set $V$, the coefficient of $X^i$ in the zero forcing polynomial of $T$ is less than or equal…
- tree_fort_free_nonpure_counterexampleA four-vertex tree has a maximal fort-free two-set and also a fort-free three-set.
- is_zero_forcing_set_monoIf S is a zero forcing set of a simple graph G and S is a subset of S', then S' is also a zero forcing set of G.
- zero_forcing_root_exposed_unique_neighborIf W is fort-free and contains a root-exposed fort, there is exactly one root neighbor belonging to any root-exposed fort contained in W.
- zero_forcing_poly_ulc_implies_log_concaveFor any finite graph, ultra-log-concavity of its zero forcing coefficients implies ordinary log-concavity.
- gt_connected_forcing_poly_eqFor every integer t ≥ 24, the connected forcing polynomial of gt_graph t is equal to the zero forcing polynomial of gt_graph t.
- zfs_compl_iff_no_stuckFor any finite graph G and finite T, the complement V\T is a zero forcing set precisely when T contains no nonempty "stuck" subset W, i.e.…
- is_connected_forcing_setA connected forcing set is a zero forcing set that induces a connected subgraph.
- leaf_rich_except_zero_forcing_iffIn a graph leaf-rich away from r, a set is zero forcing exactly when it contains all but at most one leaf at each support, and either…
- tree_exposure_plain_partial_sync_counterexampleFor a rooted three-vertex path the unexposed counts at ranks zero and one are one and three, while the exposed counts at ranks zero, one…
- tree_zero_forcing_conditional_antipodal_counterexampleThere is a nine-vertex tree and disjoint fixed-white and four-element free sets for which at least one 1–3 partition gives two fort-free…
- zero_forcing_white_weighted_countThe total product weight of k-element white sets whose complement is a zero forcing set.
- op_1400_counterexample_order_le_eightyOpen Problem OP-1400: there exists a natural number n ≤ 80 and a simple graph G on Fin n with decidable adjacency whose zero forcing…
- tree_four_zf_white_rank_sequence_counterexampleThere exists a four-vertex tree for which no matroid on its vertex set has the same numbers of independent sets of each size as the…
- zero_forcing_finset_iter_decidesA blue set is zero forcing exactly when the executable parallel forcing process colors every vertex after at most the number of vertices…
- zero_forcing_complements_three_extendibleThe complements of zero forcing sets form a three-extendible independence system.
- zero_forcing_root_exposure_countThe number of k-element white vertex sets whose complement is zero forcing and whose root-exposed-fort status equals the given Boolean.
- zero_forcing_finset_iter_of_stableIf a finite parallel forcing iteration has stabilized, the original blue set is zero forcing exactly when the stabilized set is all…
- zero_forcing_polyGiven a finite type V and a simple graph G on V, zero_forcing_poly G is the polynomial in Polynomial ℕ defined as the sum over all subsets…
- zero_forcing_pair_obstruction_transitiveFor three distinct vertices each of whose singleton white sets is fort-free, the relation that a two-vertex white set is not fort-free is…
- zero_forcing_poly_coeffThe coefficient of x^k in the zero forcing polynomial of G is the number of k-element vertex subsets that are zero forcing sets.
- tree_zf_white_rank_pair_positive_correlationThere is a six-vertex tree and two vertices such that, among the four-element white sets whose complements are zero forcing, the events…
- zero_forcing_poly_positive_coeff_intervalFor any finite graph the positive coefficients of its zero forcing polynomial form an interval.
Read back from the Lean
For a type V, a simple graph G on V, and a subset S : Set V, is_zero_forcing_set G S asserts that every vertex v : V satisfies ZeroForced G S v.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- A zero forcing set is one whose closure is the entire vertex set. -/ def is_zero_forcing_set {V : Type*} (G : SimpleGraph V) (S : Set V) : Prop := ∀ v, ZeroForced G S v