tree_four_zf_white_rank_sequence_counterexample
There 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 complements of zero forcing sets.
Statement
theorem tree_four_zf_white_rank_sequence_counterexample : ∃ T : SimpleGraph (Fin 4), T.IsTree ∧ ∀ M : Matroid (Fin 4), ∃ k : ℕ, {W : Finset (Fin 4) | W.card = k ∧ M.Indep (W : Set (Fin 4))}.ncard ≠ {W : Finset (Fin 4) | W.card = k ∧ is_zero_forcing_set T ((Finset.univ \ W : Finset (Fin 4)) : Set (Fin 4))}.ncard- Related work
- The tree zero forcing polynomial question is in https://arxiv.org/abs/2611.11352. Matroid independence-set ULC is proved in https://arxiv.org/abs/1811.01600.
- Verified
- 13 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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.
- FThe prime field $\mathrm{GF}(p)$, realized as $\mathbb{Z}/p\mathbb{Z}$ via
ZMod.
Read back from the Lean
There exists a simple graph $T$ on the vertex set Fin 4 such that $T$ is a tree, and for every matroid $M$ on Fin 4, there exists a natural number $k$ such that the number of subsets $W \\subseteq \\text{Fin } 4$ of cardinality $k$ that are independent in $M$ is not equal to the number of subsets $W \\subseteq \\text{Fin } 4$ of cardinality $k$ whose complement $(\\text{Fin } 4 \\setminus W)$ is a zero-forcing set of $T$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The theorem is proved by taking the 4-vertex path graph P_4 as the counterexample tree. By finite verification, the number of vertex subsets whose complements are zero forcing sets is 6 for size 2 (all pairs) and 2 for size 3. Any matroid matching these counts would have all 6 pairs independent, while having only two independent triples A and B; but the complements of A and B yield a pair {a, b} which, when augmented from A by the matroid independent set exchange axiom, produces a third independent triple, reaching a contradiction.
G is a well-defined loopless undirected graph on 4 vertices with decidable adjacency.
The graph G is defined as the 4-vertex path graph on {0, 1, 2, 3} with edge list [(0,1), (1,2), (2,3)]. Adjacency is the symmetric closure of this list, so symmetry holds by definition (line 9). Looplessness is verified by exhausting all four vertices (line 10), and decidability of adjacency follows because membership in the finite edge list is decidable (lines 12–14).
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
G is a tree.
By SimpleGraph.isTree_iff_connected_and_card.mpr, a graph is a tree if it is connected and has |E| + 1 = |V|. For connectedness, vertex 0 can reach vertices 1, 2, and 3 via the path 0 - 1 - 2 - 3, so all vertices in Fin 4 are reachable from 0. For the count condition, Nat.card_eq_fintype_card rewrites the cardinalities to 3 edges and 4 vertices, and 3 + 1 = 4 is checked by decide.
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 := h02.trans (show G.Adj 2 3 by decide).reachable intro v fin_cases v · exact SimpleGraph.Reachable.rfl · exact h01 · exact h02 · exact h03 · rw [Nat.card_eq_fintype_card, Nat.card_eq_fintype_card] decide
The property noFort W is decidable for every vertex subset W.
The definition noFort W asserts the non-existence of a fort (a nonempty stuck subset F ⊆ W). Since Fin 4 is a finite type, all quantifiers range over finite domains, so decidability is synthesized automatically.
instance (W : Finset (Fin 4)) : Decidable (noFort W) := by unfold noFort infer_instance
There are exactly 6 subsets of size 2 and 2 subsets of size 3 containing no fort. automation
The sets level 2 and level 3 collect all subsets of sizes 2 and 3 that contain no fort. Their cardinalities, 6 and 2 respectively, are computed by exhaustive enumeration via decide.
theorem level_two : (level 2).card = 6 := by decide theorem level_three : (level 3).card = 2 := by decide
The number of subsets of size k whose complements are zero forcing sets equals the cardinality of level k.
Using Set.ncard_eq_toFinset_card', the cardinality of the set of subsets is converted to finset cardinality. The characterization noFort_iff then equates being the complement of a zero forcing set with containing no fort, matching the definition of level k.
uses
Set.ncard_eq_toFinset_card',noFort_ifftheorem count_eq (k : ℕ) : {W : Finset (Fin 4) | W.card = k ∧ is_zero_forcing_set G ((Finset.univ \ W : Finset (Fin 4)) : Set (Fin 4))}.ncard = (level k).card := by classical rw [Set.ncard_eq_toFinset_card'] congr 1 ext W simp [level, noFort_iff]
If a matroid on 4 vertices has 6 independent pairs, then every pair is independent.
There are (4 choose 2) = 6 pairs of vertices in total. If the number of independent pairs is 6, the independent pairs form a subset of all pairs having the same cardinality. By Finset.eq_of_subset_of_card_le, the independent pairs are all pairs, so every pair P of size 2 is independent in M.
uses
Set.ncard_eq_toFinset_card',Finset.filter_filter,Finset.eq_of_subset_of_card_le,Finset.filter_subset,Finset.mem_filter.mptheorem no_matroid_two_triples (M : Matroid (Fin 4)) (h2 : {W : Finset (Fin 4) | W.card = 2 ∧ M.Indep (W : Set (Fin 4))}.ncard = 6) : {W : Finset (Fin 4) | W.card = 3 ∧ M.Indep (W : Set (Fin 4))}.ncard ≠ 2 := by classical let pairs : Finset (Finset (Fin 4)) := Finset.univ.filter (fun W => W.card = 2) let goodPairs : Finset (Finset (Fin 4)) := pairs.filter (fun W => M.Indep (W : Set (Fin 4))) have hpairs : pairs.card = 6 := by decide have hgoodPairs : goodPairs.card = 6 := by rw [Set.ncard_eq_toFinset_card'] at h2 convert h2 using 1 <;> simp [goodPairs, pairs, Finset.filter_filter] have heqPairs : goodPairs = pairs := Finset.eq_of_subset_of_card_le (Finset.filter_subset _ _) (by omega) have allPairs (P : Finset (Fin 4)) (hP : P.card = 2) : M.Indep (P : Set (Fin 4)) := by have hmem : P ∈ pairs := by simp [pairs, hP] rw [← heqPairs] at hmem exact (Finset.mem_filter.mp hmem).2
Assuming for contradiction that M has exactly 2 independent triples, let A and B denote these two distinct triples.
If the number of independent triples is 2, Finset.card_eq_two.mp gives two distinct 3-element sets A ≠ B that are both independent in M.
uses
Set.ncard_eq_toFinset_card',Finset.card_eq_two.mp,Finset.mem_filter.mpintro h3 let triples : Finset (Finset (Fin 4)) := Finset.univ.filter (fun W => W.card = 3 ∧ M.Indep (W : Set (Fin 4))) have hcard : triples.card = 2 := by rw [Set.ncard_eq_toFinset_card'] at h3 convert h3 using 1 <;> simp [triples] obtain ⟨A, B, hAB, htriples⟩ := Finset.card_eq_two.mp hcard have hA : A ∈ triples := by rw [htriples]; simp have hB : B ∈ triples := by rw [htriples]; simp have hAprops := (Finset.mem_filter.mp hA).2 have hBprops := (Finset.mem_filter.mp hB).2
The complements of A and B are singletons {a} and {b} with a ≠ b, so a ∉ A and b ∉ B.
Since the vertex set has size 4 and |A| = |B| = 3, the complements Finset.univ \ A and Finset.univ \ B each have size 4 - 3 = 1 by Finset.card_sdiff. By Finset.card_eq_one.mp, these complements are singletons {a} and {b}. Since A ≠ B, their complements are distinct, so a ≠ b. By definition of set difference, a ∉ A and b ∉ B.
uses
Finset.card_sdiff,Finset.card_eq_one.mp,Finset.mem_sdiff.mp,congrArg,Finset.mem_sdiff,Finset.mem_univ,true_and,not_iff_not.mp,Iff.of_eqhave hAc : (Finset.univ \ A).card = 1 := by simp [Finset.card_sdiff, hAprops.1] have hBc : (Finset.univ \ B).card = 1 := by simp [Finset.card_sdiff, hBprops.1] obtain ⟨a, ha⟩ := Finset.card_eq_one.mp hAc obtain ⟨b, hb⟩ := Finset.card_eq_one.mp hBc have haA : a ∉ A := by have : a ∈ Finset.univ \ A := by rw [ha]; simp exact (Finset.mem_sdiff.mp this).2 have hbB : b ∉ B := by have : b ∈ Finset.univ \ B := by rw [hb]; simp exact (Finset.mem_sdiff.mp this).2 have hab : a ≠ b := by intro h subst b have hc : Finset.univ \ A = Finset.univ \ B := ha.trans hb.symm apply hAB ext x have hx := congrArg (fun S : Finset (Fin 4) => x ∈ S) hc simp only [Finset.mem_sdiff, Finset.mem_univ, true_and] at hx exact not_iff_not.mp (Iff.of_eq hx)
Augmenting the independent pair {a, b} with an element from A yields a contradiction, so no such matroid can exist.
The pair P = {a, b} has size 2 because a ≠ b, so P is independent. Since |P| = 2 < 3 = |A| and both P and A are independent, the matroid augmentation property gives an element x ∈ A \ P such that P ∪ {x} is independent. This set has size 3, so it must be one of the only two independent triples, A or B. But P ⊆ P ∪ {x}, which implies a ∈ P ∪ {x} and b ∈ P ∪ {x}. If P ∪ {x} = A, this contradicts a ∉ A; if P ∪ {x} = B, this contradicts b ∉ B. In either case we have a contradiction.
uses
Finset.mem_univ,Finset.card_insert_of_notMem,Finset.coe_insert,Finset.mem_insert,Finset.mem_singletonlet P : Finset (Fin 4) := {a, b} have hPc : P.card = 2 := by simp [P, hab] have hPi := allPairs P hPc obtain ⟨x, hxA, hxP, hxIndep⟩ := hPi.augment_finset hAprops.2 (by omega) have hD : insert x P ∈ triples := by apply Finset.mem_filter.mpr refine ⟨Finset.mem_univ _, by simp [Finset.card_insert_of_notMem hxP, hPc], ?_⟩ simpa only [Finset.coe_insert] using hxIndep rw [htriples] at hD simp only [Finset.mem_insert, Finset.mem_singleton] at hD rcases hD with hD | hD · have : a ∈ A := by rw [← hD]; simp [P] exact haA this · have : b ∈ B := by rw [← hD]; simp [P] exact hbB this
No matroid on 4 vertices has independent set counts matching the complement-zero-forcing counts of G.
Using G and the fact tree that it is a tree, assume for contradiction that some matroid M matches the zero forcing complement counts for all sizes k. For k = 2, the count is 6 by count_eq and level_two. For k = 3, the count is 2 by count_eq and level_three. But no_matroid_two_triples shows that no matroid can simultaneously have 6 independent pairs and 2 independent triples.
uses
tree,count_eq,level_two,level_three,no_matroid_two_triplestheorem no_matching_matroid : ∃ T : SimpleGraph (Fin 4), T.IsTree ∧ ∀ M : Matroid (Fin 4), ∃ k : ℕ, {W : Finset (Fin 4) | W.card = k ∧ M.Indep (W : Set (Fin 4))}.ncard ≠ {W : Finset (Fin 4) | W.card = k ∧ is_zero_forcing_set T ((Finset.univ \ W : Finset (Fin 4)) : Set (Fin 4))}.ncard := by refine ⟨G, tree, ?_⟩ intro M by_contra h push_neg at h have h2 := h 2 rw [count_eq, level_two] at h2 have h3 := h 3 rw [count_eq, level_three] at h3 exact no_matroid_two_triples M h2 h3
There exists a 4-vertex tree whose complement-zero-forcing profile does not match the independent set profile of any matroid.
The main theorem is identical to IN800PathMatroid.no_matching_matroid and is closed by citing it directly.
uses
IN800PathMatroid.no_matching_matroidtheorem tree_four_zf_white_rank_sequence_counterexample : ∃ T : SimpleGraph (Fin 4), T.IsTree ∧ ∀ M : Matroid (Fin 4), ∃ k : ℕ, {W : Finset (Fin 4) | W.card = k ∧ M.Indep (W : Set (Fin 4))}.ncard ≠ {W : Finset (Fin 4) | W.card = k ∧ is_zero_forcing_set T ((Finset.univ \ W : Finset (Fin 4)) : Set (Fin 4))}.ncard := by exact IN800PathMatroid.no_matching_matroid
SimpleGraph.isTree_iff_connected_and_card.mpr- A simple graph is a tree if it is connected and its number of edges plus 1 equals its number of vertices.
SimpleGraph.Reachable.rfl- Every vertex in a graph is reachable from itself.
Nat.card_eq_fintype_card- For any finite type, its cardinality as a natural number equals its cardinality as a finite type.
Set.ncard_eq_toFinset_card'- The cardinality of a finite set equals the cardinality of the corresponding finset.
noFort_iff- A vertex subset has no fort if and only if its complement is a zero forcing set of the graph.
Finset.filter_filter- Filtering a finite set successively by two predicates is equivalent to filtering by their conjunction.
Finset.eq_of_subset_of_card_le- A subset of a finite set is equal to the whole set if its cardinality is at least that of the whole set.
Finset.filter_subset- The sub-finset of elements satisfying a predicate is a subset of the original finite set.
Finset.mem_filter.mp- An element belongs to a filtered finite set if and only if it belongs to the set and satisfies the predicate.
Finset.card_eq_two.mp- A finite set of cardinality 2 consists of two distinct elements.
Finset.card_sdiff- The cardinality of the difference of two finite sets equals the cardinality of the first minus that of their intersection.
Finset.card_eq_one.mp- A finite set of cardinality 1 consists of a single element.
Finset.mem_sdiff.mp- If an element is in the difference S \ T, then it is in S and not in T.
congrArg- Applying a function to equal arguments produces equal values.
Finset.mem_sdiff- An element belongs to S \ T if and only if it belongs to S and not to T.
Finset.mem_univ- Every element of a finite type belongs to the universal finite set of that type.
true_and- Conjunction of True with any proposition is equivalent to that proposition.
not_iff_not.mp- If the negations of two propositions are equivalent, then the propositions are equivalent.
Iff.of_eq- Equality of truth values implies logical equivalence.
Finset.card_insert_of_notMem- Inserting an element not already in a finite set increases its cardinality by 1.
Finset.coe_insert- The coercion of inserting an element into a finite set equals the set insert into the coerced set.
Finset.mem_insert- An element belongs to insert x S if and only if it equals x or belongs to S.
Finset.mem_singleton- An element belongs to the singleton {x} if and only if it equals x.
tree- The graph G (the 4-vertex path graph) is a tree.
count_eq- For any size k, the number of subsets whose complement is a zero forcing set equals the size of level k.
level_two- There are exactly 6 subsets of size 2 with no fort in G.
level_three- There are exactly 2 subsets of size 3 with no fort in G.
no_matroid_two_triples- Any matroid on 4 vertices with all 6 pairs independent cannot have exactly 2 independent triples.
IN800PathMatroid.no_matching_matroid- There exists a 4-vertex tree whose complement-zero-forcing profile does not match the independent set profile of any matroid.
- The counts of complement-zero-forcing sets of sizes 2 and 3 (the lemmas level_two and level_three) are established purely by exhaustive finite verification using the decide tactic.
- The equivalence between complements of zero forcing sets and sets without forts (noFort_iff) relies on the background theorem zfs_compl_iff_no_stuck, transforming a dynamic zero forcing process into a static combinatorial property.
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 IN800PathMatroiddef edges : List (Fin 4 × Fin 4) := [(0,1),(1,2),(2,3)]def G : SimpleGraph (Fin 4) 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_instancetheorem 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 := h02.trans (show G.Adj 2 3 by decide).reachable intro v fin_cases v · exact SimpleGraph.Reachable.rfl · exact h01 · exact h02 · exact h03 · rw [Nat.card_eq_fintype_card, Nat.card_eq_fintype_card] decidedef noFort (W : Finset (Fin 4)) : Prop := ¬ ∃ F : Finset (Fin 4), F.Nonempty ∧ F ⊆ W ∧ ∀ u : Fin 4, u ∉ F → ∀ w : Fin 4, w ∈ F → G.Adj u w → ∃ x : Fin 4, x ∈ F ∧ G.Adj u x ∧ x ≠ winstance (W : Finset (Fin 4)) : Decidable (noFort W) := by unfold noFort infer_instancetheorem noFort_iff (W : Finset (Fin 4)) : noFort W ↔ is_zero_forcing_set G ((Finset.univ \ W : Finset (Fin 4)) : Set (Fin 4)) := (zfs_compl_iff_no_stuck G W).symmdef level (k : ℕ) : Finset (Finset (Fin 4)) := Finset.univ.filter fun W => W.card = k ∧ noFort Wtheorem level_two : (level 2).card = 6 := by decidetheorem level_three : (level 3).card = 2 := by decidetheorem count_eq (k : ℕ) : {W : Finset (Fin 4) | W.card = k ∧ is_zero_forcing_set G ((Finset.univ \ W : Finset (Fin 4)) : Set (Fin 4))}.ncard = (level k).card := by classical rw [Set.ncard_eq_toFinset_card'] congr 1 ext W simp [level, noFort_iff]-- A rank-three matroid on four vertices with all pairs independent cannot-- have only two independent triples.theorem no_matroid_two_triples (M : Matroid (Fin 4)) (h2 : {W : Finset (Fin 4) | W.card = 2 ∧ M.Indep (W : Set (Fin 4))}.ncard = 6) : {W : Finset (Fin 4) | W.card = 3 ∧ M.Indep (W : Set (Fin 4))}.ncard ≠ 2 := by classical let pairs : Finset (Finset (Fin 4)) := Finset.univ.filter (fun W => W.card = 2) let goodPairs : Finset (Finset (Fin 4)) := pairs.filter (fun W => M.Indep (W : Set (Fin 4))) have hpairs : pairs.card = 6 := by decide have hgoodPairs : goodPairs.card = 6 := by rw [Set.ncard_eq_toFinset_card'] at h2 convert h2 using 1 <;> simp [goodPairs, pairs, Finset.filter_filter] have heqPairs : goodPairs = pairs := Finset.eq_of_subset_of_card_le (Finset.filter_subset _ _) (by omega) have allPairs (P : Finset (Fin 4)) (hP : P.card = 2) : M.Indep (P : Set (Fin 4)) := by have hmem : P ∈ pairs := by simp [pairs, hP] rw [← heqPairs] at hmem exact (Finset.mem_filter.mp hmem).2 intro h3 let triples : Finset (Finset (Fin 4)) := Finset.univ.filter (fun W => W.card = 3 ∧ M.Indep (W : Set (Fin 4))) have hcard : triples.card = 2 := by rw [Set.ncard_eq_toFinset_card'] at h3 convert h3 using 1 <;> simp [triples] obtain ⟨A, B, hAB, htriples⟩ := Finset.card_eq_two.mp hcard have hA : A ∈ triples := by rw [htriples]; simp have hB : B ∈ triples := by rw [htriples]; simp have hAprops := (Finset.mem_filter.mp hA).2 have hBprops := (Finset.mem_filter.mp hB).2 have hAc : (Finset.univ \ A).card = 1 := by simp [Finset.card_sdiff, hAprops.1] have hBc : (Finset.univ \ B).card = 1 := by simp [Finset.card_sdiff, hBprops.1] obtain ⟨a, ha⟩ := Finset.card_eq_one.mp hAc obtain ⟨b, hb⟩ := Finset.card_eq_one.mp hBc have haA : a ∉ A := by have : a ∈ Finset.univ \ A := by rw [ha]; simp exact (Finset.mem_sdiff.mp this).2 have hbB : b ∉ B := by have : b ∈ Finset.univ \ B := by rw [hb]; simp exact (Finset.mem_sdiff.mp this).2 have hab : a ≠ b := by intro h subst b have hc : Finset.univ \ A = Finset.univ \ B := ha.trans hb.symm apply hAB ext x have hx := congrArg (fun S : Finset (Fin 4) => x ∈ S) hc simp only [Finset.mem_sdiff, Finset.mem_univ, true_and] at hx exact not_iff_not.mp (Iff.of_eq hx) let P : Finset (Fin 4) := {a, b} have hPc : P.card = 2 := by simp [P, hab] have hPi := allPairs P hPc obtain ⟨x, hxA, hxP, hxIndep⟩ := hPi.augment_finset hAprops.2 (by omega) have hD : insert x P ∈ triples := by apply Finset.mem_filter.mpr refine ⟨Finset.mem_univ _, by simp [Finset.card_insert_of_notMem hxP, hPc], ?_⟩ simpa only [Finset.coe_insert] using hxIndep rw [htriples] at hD simp only [Finset.mem_insert, Finset.mem_singleton] at hD rcases hD with hD | hD · have : a ∈ A := by rw [← hD]; simp [P] exact haA this · have : b ∈ B := by rw [← hD]; simp [P] exact hbB thistheorem no_matching_matroid : ∃ T : SimpleGraph (Fin 4), T.IsTree ∧ ∀ M : Matroid (Fin 4), ∃ k : ℕ, {W : Finset (Fin 4) | W.card = k ∧ M.Indep (W : Set (Fin 4))}.ncard ≠ {W : Finset (Fin 4) | W.card = k ∧ is_zero_forcing_set T ((Finset.univ \ W : Finset (Fin 4)) : Set (Fin 4))}.ncard := by refine ⟨G, tree, ?_⟩ intro M by_contra h push_neg at h have h2 := h 2 rw [count_eq, level_two] at h2 have h3 := h 3 rw [count_eq, level_three] at h3 exact no_matroid_two_triples M h2 h3end IN800PathMatroidtheorem tree_four_zf_white_rank_sequence_counterexample : ∃ T : SimpleGraph (Fin 4), T.IsTree ∧ ∀ M : Matroid (Fin 4), ∃ k : ℕ, {W : Finset (Fin 4) | W.card = k ∧ M.Indep (W : Set (Fin 4))}.ncard ≠ {W : Finset (Fin 4) | W.card = k ∧ is_zero_forcing_set T ((Finset.univ \ W : Finset (Fin 4)) : Set (Fin 4))}.ncard := by exact IN800PathMatroid.no_matching_matroid