tree_zf_white_rank_pair_positive_correlation
There is a six-vertex tree and two vertices such that, among the four-element white sets whose complements are zero forcing, the events that these vertices are white have positive correlation.
Statement
theorem tree_zf_white_rank_pair_positive_correlation : ∃ (T : SimpleGraph (Fin 6)) (i j : Fin 6), T.IsTree ∧ i ≠ j ∧ (let family : Set (Finset (Fin 6)) := {W | W.card = 4 ∧ is_zero_forcing_set T ((Finset.univ \ W : Finset (Fin 6)) : Set (Fin 6))}; {W ∈ family | i ∈ W ∧ j ∈ W}.ncard * family.ncard > {W ∈ family | i ∈ W}.ncard * {W ∈ family | j ∈ W}.ncard)
- Source
- Filed by the prover as a step towards another result
- Verified
- 13 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- is_zero_forcing_setA set of vertices S is a zero forcing set of G if its zero forcing closure contains all vertices of G.
- 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.…
- Arena.Reachable.transReachability is transitive.
The proof, explained
The theorem is established by an explicit witness: the graph G on six vertices {0, 1, 2, 3, 4, 5} with edges {0,1}, {1,2}, {0,3}, {0,5}, {3,4}, together with vertices 1 and 4. First, G is verified to be a tree by showing all vertices are reachable from 0 and checking that |E| + 1 = |V| = 6. Next, complement zero forcing sets of size 2 (corresponding to 4-element white sets) are characterized by avoiding forts, which makes membership decidable by finite exhaustive search. Exhaustive computation determines that the family contains 7 sets, with 5 containing vertex 1, 4 containing vertex 4, and 3 containing both. Finally, positive correlation is verified by the numerical inequality 3 * 7 = 21 > 20 = 5 * 4.
The graph G on vertex set {0, 1, 2, 3, 4, 5} with edges {0,1}, {1,2}, {0,3}, {0,5}, and {3,4} is a well-defined simple graph with decidable adjacency.
The edge relation is defined symmetrically from the explicit list of five pairs. Symmetry is proved by commuting the disjunction, looplessness is verified by exhaustive check over all six vertices using `decide`, and decidability of adjacency follows by typeclass inference.
def edges : List (Fin 6 × Fin 6) := [(0,1),(1,2),(0,3),(0,5),(3,4)] def G : SimpleGraph (Fin 6) where Adj u v := (u,v) ∈ edges ∨ (v,u) ∈ edges symm := ⟨by intro u v h; exact h.symm⟩ loopless := ⟨by intro v; fin_cases v <;> decide⟩ instance : DecidableRel G.Adj := by intro u v change Decidable ((u,v) ∈ edges ∨ (v,u) ∈ edges) infer_instance
Whether a subset W ⊆ {0, 1, 2, 3, 4, 5} contains no fort is decidable.
The property `noFort W` asserts the non-existence of a nonempty subset F ⊆ W where every vertex outside F has either zero or at least two neighbors in F. Because the vertex set and the powerset are finite, unfolding `noFort` yields a bounded first-order statement, allowing typeclass resolution to synthesize a decision procedure via `infer_instance`.
def noFort (W : Finset (Fin 6)) : Prop := ¬ ∃ fortSet : Finset (Fin 6), fortSet.Nonempty ∧ fortSet ⊆ W ∧ ∀ u : Fin 6, u ∉ fortSet → ∀ w : Fin 6, w ∈ fortSet → G.Adj u w → ∃ x : Fin 6, x ∈ fortSet ∧ G.Adj u x ∧ x ≠ w instance (W : Finset (Fin 6)) : Decidable (noFort W) := by unfold noFort infer_instance
There are 7 fort-free 4-element subsets of vertices in total, with 5 containing vertex 1, 4 containing vertex 4, and 3 containing both. automation
The set `level 4` collects all 4-element subsets W satisfying `noFort W`. For each count—the total (`level_four`), those containing vertex 1 (`level_four_one`), those containing vertex 4 (`level_four_four`), and those containing both (`level_four_both`)—the `decide` tactic checks every subset among the 15 four-element subsets of `Fin 6` by computation.
def level (k : ℕ) : Finset (Finset (Fin 6)) := Finset.univ.filter fun W => W.card = k ∧ noFort W theorem level_four : (level 4).card = 7 := by decide theorem level_four_one : (level 4 |>.filter (fun W => (1 : Fin 6) ∈ W)).card = 5 := by decide theorem level_four_four : (level 4 |>.filter (fun W => (4 : Fin 6) ∈ W)).card = 4 := by decide theorem level_four_both : (level 4 |>.filter (fun W => (1 : Fin 6) ∈ W ∧ (4 : Fin 6) ∈ W)).card = 3 := by decide
The graph G is a tree.
By `SimpleGraph.isTree_iff_connected_and_card.mpr`, a finite graph is a tree if it is connected and its number of edges plus 1 equals its number of vertices. Connectivity is proved by showing that every vertex is reachable from 0: vertices 1, 3, and 5 are direct neighbors, vertex 2 is reached via 1, vertex 4 via 3, and 0 is reachable to itself by `SimpleGraph.Reachable.rfl`. An exhaustive case split (`fin_cases`) covers all six vertices. Finally, `Nat.card_eq_fintype_card` converts set cardinalities to finite type sizes, and `decide` confirms that 5 + 1 = 6.
uses
SimpleGraph.isTree_iff_connected_and_card.mpr,SimpleGraph.Reachable.rfl,Nat.card_eq_fintype_cardtheorem tree : G.IsTree := by apply SimpleGraph.isTree_iff_connected_and_card.mpr constructor · apply (G.connected_iff_exists_forall_reachable).mpr refine ⟨0, ?_⟩ have h01 : G.Reachable 0 1 := (show G.Adj 0 1 by decide).reachable have h02 : G.Reachable 0 2 := h01.trans (show G.Adj 1 2 by decide).reachable have h03 : G.Reachable 0 3 := (show G.Adj 0 3 by decide).reachable have h04 : G.Reachable 0 4 := h03.trans (show G.Adj 3 4 by decide).reachable have h05 : G.Reachable 0 5 := (show G.Adj 0 5 by decide).reachable intro v fin_cases v · exact SimpleGraph.Reachable.rfl · exact h01 · exact h02 · exact h03 · exact h04 · exact h05 · rw [Nat.card_eq_fintype_card, Nat.card_eq_fintype_card] decide
For any predicate P, the number of sets in `family` satisfying P equals the number in `level 4` satisfying P.
The set `family` consists of 4-element sets W whose complement is a zero forcing set. By `Set.ncard_eq_toFinset_card'`, the set cardinality equals the finset cardinality. Extensionality and simplification using `noFort_iff` (which equates the zero forcing complement property to `noFort W`) show that W ∈ family if and only if W ∈ level 4, matching the filtered counts.
uses
Set.ncard_eq_toFinset_card',noFort_iffdef family : Set (Finset (Fin 6)) := {W | W.card = 4 ∧ is_zero_forcing_set G ((Finset.univ \ W : Finset (Fin 6)) : Set (Fin 6))} theorem family_count (P : Finset (Fin 6) → Prop) [DecidablePred P] : {W ∈ family | P W}.ncard = ((level 4).filter P).card := by classical rw [Set.ncard_eq_toFinset_card'] congr 1 ext W simp [family, level, noFort_iff]
The total number of sets in `family` is 7.
Specializing `family_count` to the trivial predicate `fun _ => True` equates `family.ncard` to `(level 4).card`, which was evaluated to be 7 in `level_four`.
uses
family_count,level_fourtheorem total_count : family.ncard = 7 := by have h := family_count (fun _ => True) have hfamily : {W ∈ family | True} = family := by ext W; simp have hfilter : (level 4).filter (fun _ => True) = level 4 := by simp rw [hfamily, hfilter, level_four] at h exact h
In the tree G, the events that vertices 1 and 4 belong to a 4-element white set with zero forcing complement are positively correlated.
We instantiate the existential claim with G, vertex 1, and vertex 4. G is a tree by `tree`, and 1 ≠ 4 is verified by `decide`. The positive correlation condition asserts that the joint count times the total count exceeds the product of the marginal counts. Rewriting the set cardinalities using `family_count`, `total_count`, `level_four_both`, `level_four_one`, and `level_four_four` transforms the inequality into 3 * 7 > 5 * 4, which holds since 21 > 20 (verified by `decide`).
uses
tree,family_count,total_count,level_four_both,level_four_one,level_four_fourtheorem positive_corr : ∃ (T : SimpleGraph (Fin 6)) (i j : Fin 6), T.IsTree ∧ i ≠ j ∧ (let fortSet : Set (Finset (Fin 6)) := {W | W.card = 4 ∧ is_zero_forcing_set T ((Finset.univ \ W : Finset (Fin 6)) : Set (Fin 6))}; {W ∈ fortSet | i ∈ W ∧ j ∈ W}.ncard * fortSet.ncard > {W ∈ fortSet | i ∈ W}.ncard * {W ∈ fortSet | j ∈ W}.ncard) := by refine ⟨G, 1, 4, tree, by decide, ?_⟩ change {W ∈ family | (1 : Fin 6) ∈ W ∧ (4 : Fin 6) ∈ W}.ncard * family.ncard > {W ∈ family | (1 : Fin 6) ∈ W}.ncard * {W ∈ family | (4 : Fin 6) ∈ W}.ncard rw [family_count, family_count, family_count, total_count, level_four_both, level_four_one, level_four_four] decide
There exists a six-vertex tree and two vertices whose events of being white in 4-element sets with zero forcing complements have positive correlation.
This concludes the main theorem directly from `In800.positive_corr`.
uses
In800.positive_corrtheorem tree_zf_white_rank_pair_positive_correlation : ∃ (T : SimpleGraph (Fin 6)) (i j : Fin 6), T.IsTree ∧ i ≠ j ∧ (let family : Set (Finset (Fin 6)) := {W | W.card = 4 ∧ is_zero_forcing_set T ((Finset.univ \ W : Finset (Fin 6)) : Set (Fin 6))}; {W ∈ family | i ∈ W ∧ j ∈ W}.ncard * family.ncard > {W ∈ family | i ∈ W}.ncard * {W ∈ family | j ∈ W}.ncard) := by exact In800.positive_corr
In800.positive_corr- There exists a tree on 6 vertices and two distinct vertices with positive correlation between their memberships in 4-element white sets whose complements are zero forcing.
Nat.card_eq_fintype_card- For any finite type, the general cardinality `Nat.card` equals the finite-type cardinality `Fintype.card`.
Set.ncard_eq_toFinset_card'- The cardinality of a finite set as a natural number (`Set.ncard`) equals the cardinality of its coercion to a `Finset`.
SimpleGraph.Reachable.rfl- Every vertex in a graph is reachable from itself.
SimpleGraph.isTree_iff_connected_and_card.mpr- A simple graph on a finite vertex set is a tree if it is connected and the number of edges plus 1 equals the number of vertices.
family_count- For any decidable predicate P on vertex subsets, the number of sets in `family` satisfying P equals the number of sets in `level 4` satisfying P.
level_four- There are exactly 7 subsets of size 4 on `Fin 6` that contain no fort.
level_four_both- There are exactly 3 subsets of size 4 containing no fort that contain both vertex 1 and vertex 4.
level_four_four- There are exactly 4 subsets of size 4 containing no fort that contain vertex 4.
level_four_one- There are exactly 5 subsets of size 4 containing no fort that contain vertex 1.
noFort_iff- A vertex subset W contains no fort if and only if its complement is a zero forcing set.
total_count- The total number of 4-element white sets with zero forcing complements in G is 7.
tree- The constructed 6-vertex graph G is a tree.
- The cardinalities of the fort-free sets (overall and restricted to vertices 1 and/or 4) are computed by the `decide` tactic, which exhaustively checks all 15 subsets of size 4 on a 6-element set.
- The equivalence between a complement being zero forcing and the white set avoiding forts (`noFort_iff`) relies on the knowledge base theorem `zfs_compl_iff_no_stuck`.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
set_option maxRecDepth 8192set_option maxHeartbeats 8000000namespace In800def edges : List (Fin 6 × Fin 6) := [(0,1),(1,2),(0,3),(0,5),(3,4)]def G : SimpleGraph (Fin 6) where Adj u v := (u,v) ∈ edges ∨ (v,u) ∈ edges symm := ⟨by intro u v h; exact h.symm⟩ loopless := ⟨by intro v; fin_cases v <;> decide⟩instance : DecidableRel G.Adj := by intro u v change Decidable ((u,v) ∈ edges ∨ (v,u) ∈ edges) infer_instancedef noFort (W : Finset (Fin 6)) : Prop := ¬ ∃ fortSet : Finset (Fin 6), fortSet.Nonempty ∧ fortSet ⊆ W ∧ ∀ u : Fin 6, u ∉ fortSet → ∀ w : Fin 6, w ∈ fortSet → G.Adj u w → ∃ x : Fin 6, x ∈ fortSet ∧ G.Adj u x ∧ x ≠ winstance (W : Finset (Fin 6)) : Decidable (noFort W) := by unfold noFort infer_instancetheorem noFort_iff (W : Finset (Fin 6)) : noFort W ↔ is_zero_forcing_set G ((Finset.univ \ W : Finset (Fin 6)) : Set (Fin 6)) := (zfs_compl_iff_no_stuck G W).symmdef level (k : ℕ) : Finset (Finset (Fin 6)) := Finset.univ.filter fun W => W.card = k ∧ noFort Wtheorem level_four : (level 4).card = 7 := by decidetheorem level_four_one : (level 4 |>.filter (fun W => (1 : Fin 6) ∈ W)).card = 5 := by decidetheorem level_four_four : (level 4 |>.filter (fun W => (4 : Fin 6) ∈ W)).card = 4 := by decidetheorem level_four_both : (level 4 |>.filter (fun W => (1 : Fin 6) ∈ W ∧ (4 : Fin 6) ∈ W)).card = 3 := by decidetheorem tree : G.IsTree := by apply SimpleGraph.isTree_iff_connected_and_card.mpr constructor · apply (G.connected_iff_exists_forall_reachable).mpr refine ⟨0, ?_⟩ have h01 : G.Reachable 0 1 := (show G.Adj 0 1 by decide).reachable have h02 : G.Reachable 0 2 := h01.trans (show G.Adj 1 2 by decide).reachable have h03 : G.Reachable 0 3 := (show G.Adj 0 3 by decide).reachable have h04 : G.Reachable 0 4 := h03.trans (show G.Adj 3 4 by decide).reachable have h05 : G.Reachable 0 5 := (show G.Adj 0 5 by decide).reachable intro v fin_cases v · exact SimpleGraph.Reachable.rfl · exact h01 · exact h02 · exact h03 · exact h04 · exact h05 · rw [Nat.card_eq_fintype_card, Nat.card_eq_fintype_card] decidedef family : Set (Finset (Fin 6)) := {W | W.card = 4 ∧ is_zero_forcing_set G ((Finset.univ \ W : Finset (Fin 6)) : Set (Fin 6))}theorem family_count (P : Finset (Fin 6) → Prop) [DecidablePred P] : {W ∈ family | P W}.ncard = ((level 4).filter P).card := by classical rw [Set.ncard_eq_toFinset_card'] congr 1 ext W simp [family, level, noFort_iff]theorem total_count : family.ncard = 7 := by have h := family_count (fun _ => True) have hfamily : {W ∈ family | True} = family := by ext W; simp have hfilter : (level 4).filter (fun _ => True) = level 4 := by simp rw [hfamily, hfilter, level_four] at h exact htheorem positive_corr : ∃ (T : SimpleGraph (Fin 6)) (i j : Fin 6), T.IsTree ∧ i ≠ j ∧ (let fortSet : Set (Finset (Fin 6)) := {W | W.card = 4 ∧ is_zero_forcing_set T ((Finset.univ \ W : Finset (Fin 6)) : Set (Fin 6))}; {W ∈ fortSet | i ∈ W ∧ j ∈ W}.ncard * fortSet.ncard > {W ∈ fortSet | i ∈ W}.ncard * {W ∈ fortSet | j ∈ W}.ncard) := by refine ⟨G, 1, 4, tree, by decide, ?_⟩ change {W ∈ family | (1 : Fin 6) ∈ W ∧ (4 : Fin 6) ∈ W}.ncard * family.ncard > {W ∈ family | (1 : Fin 6) ∈ W}.ncard * {W ∈ family | (4 : Fin 6) ∈ W}.ncard rw [family_count, family_count, family_count, total_count, level_four_both, level_four_one, level_four_four] decideend In800theorem tree_zf_white_rank_pair_positive_correlation : ∃ (T : SimpleGraph (Fin 6)) (i j : Fin 6), T.IsTree ∧ i ≠ j ∧ (let family : Set (Finset (Fin 6)) := {W | W.card = 4 ∧ is_zero_forcing_set T ((Finset.univ \ W : Finset (Fin 6)) : Set (Fin 6))}; {W ∈ family | i ∈ W ∧ j ∈ W}.ncard * family.ncard > {W ∈ family | i ∈ W}.ncard * {W ∈ family | j ∈ W}.ncard) := by exact In800.positive_corr