op_1371_even_upper_bound_achievable
There exists a natural number n, a bipartite simple graph G on Fin n, a field F with ringChar F ≠ 2, and a natural number k such that G admits an involutory weighted adjacency matrix over F, 4 ≤ k, Even k, and graph_min_forcing_num (G □ SimpleGraph.pathGraph k) = ((n / 2 * (k / 2) : ℕ) : ℕ∞).
Statement
theorem op_1371_even_upper_bound_achievable : ∃ (n : ℕ) (G : SimpleGraph (Fin n)) (F : Type) (_ : Field F) (k : ℕ), G.IsBipartite ∧ ringChar F ≠ 2 ∧ graph_admits_involutory_weighted_adj_matrix G F ∧ 4 ≤ k ∧ Even k ∧ graph_min_forcing_num (G □ SimpleGraph.pathGraph k) = ((n / 2 * (k / 2) : ℕ) : ℕ∞)
- Formalizes
- arXiv:2611.11813 Remark 2.10
- Verified
- 11 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- graph_min_forcing_numThe minimum forcing number graph_min_forcing_num G of a simple graph G is the infimum in ℕ∞ of the extended cardinalities S.edgeSet.encard…
- graph_admits_involutory_weighted_adj_matrixA simple graph G on a finite vertex type V admits an involutory weighted adjacency matrix over a field F if there exists a matrix A over F…
- graph_is_forcing_matchingA subgraph S of a simple graph G is a forcing matching if S is a matching and there is a unique perfect matching M of G with S ≤ M.
Read back from the Lean
There exist a natural number $n$, a simple graph $G$ on vertex set $\mathrm{Fin}\ n$, a type $F$ with a field structure, and a natural number $k$ such that: 1. $G$ is bipartite; 2. the characteristic of $F$ is not 2 ($\mathrm{ringChar}\ F \neq 2$); 3. $G$ admits an involutory weighted adjacency matrix over $F$; 4. $4 \le k$; 5. $k$ is even; and 6. the minimum forcing number of the Cartesian product graph $G \mathbin{\square} \mathrm{pathGraph}\ k$ is equal to $(n / 2) \cdot (k / 2)$ (evaluated with natural number division, coerced to $\mathbb{N}_\infty$).
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 proves that the upper bound (n / 2) * (k / 2) on the minimum forcing number of the Cartesian product G □ P_k is achievable by demonstrating the degenerate case n = 0. Choosing the empty graph G = ⊥ on Fin 0, field F = ℚ, and k = 4, the conditions of bipartiteness, characteristic not 2, and existence of an involutory weighted adjacency matrix are satisfied vacuously or trivially. An auxiliary lemma shows that any graph on an empty vertex type has minimum forcing number 0, matching the formula value (0 / 2) * (4 / 2) = 0.
The equality graph_min_forcing_num G = 0 reduces to showing the infimum of forcing matching sizes is both at most 0 and at least 0.
Unfolding the definition of graph_min_forcing_num as the infimum of edge cardinalities over forcing matchings, antisymmetry of ≤ reduces the equality to proving both directions of the inequality.
uses
le_antisymmunfold graph_min_forcing_num apply le_antisymm
The empty subgraph ⊥ is a forcing matching of G.
Because the vertex type V is empty, ⊥ has no vertices and is vacuously a matching. Moreover, ⊥ is its own unique perfect matching extension: it is vacuously spanning, and any other perfect matching y must have the same empty vertex set and adjacency relation as ⊥, so y = ⊥ by subgraph extensionality.
uses
IsEmpty.false,le_rfl,SimpleGraph.Subgraph.ext· have hS : graph_is_forcing_matching G ⊥ := by constructor · intro v hv exact (IsEmpty.false v).elim · refine ⟨⊥, ⟨?_, ?_⟩, ?_⟩ · constructor · intro v hv exact (IsEmpty.false v).elim · intro v exact (IsEmpty.false v).elim · exact le_rfl · intro y hy apply SimpleGraph.Subgraph.ext · ext v exact (IsEmpty.false v).elim · funext v exact (IsEmpty.false v).elim
The infimum of forcing matching cardinalities equals 0.
Specializing the infimum to the forcing matching ⊥ shows the infimum is at most the cardinality of ⊥.edgeSet, which is empty and therefore has cardinality 0. The reverse inequality 0 ≤ inf holds because cardinalities in ℕ∞ are bounded below by 0.
uses
iInf_le,SimpleGraph.Subgraph.edgeSet_bot,Set.encard_empty,zero_lecalc (⨅ S, ⨅ (_ : graph_is_forcing_matching G S), S.edgeSet.encard) ≤ (⨅ (_ : graph_is_forcing_matching G ⊥), (⊥ : G.Subgraph).edgeSet.encard) := iInf_le _ ⊥ _ ≤ (⊥ : G.Subgraph).edgeSet.encard := iInf_le _ hS _ = 0 := by rw [SimpleGraph.Subgraph.edgeSet_bot, Set.encard_empty] · exact zero_le
The theorem holds by choosing n = 0, G = ⊥ on Fin 0, F = ℚ, and k = 4.
We supply the witnesses n = 0, the empty graph on Fin 0, the field ℚ (whose field instance is inferred), and k = 4. The conditions 4 ≤ 4 and Even 4 (with witness 2) hold immediately by reflexivity, leaving the remaining graph and algebraic conditions to be verified.
uses
inferInstance,le_rflrefine ⟨0, ⊥, ℚ, inferInstance, 4, ?_, ?_, ?_, le_rfl, ⟨2, rfl⟩, ?_⟩
The empty graph on Fin 0 is bipartite.
A 2-coloring of the vertices is provided by the empty function from Fin 0, which vacuously satisfies the condition that adjacent vertices have different colors.
uses
Fin.elim0· refine ⟨⟨fun x => Fin.elim0 x, fun {u} => Fin.elim0 u⟩⟩
The characteristic of ℚ is not equal to 2.
The field of rational numbers has characteristic zero, and 0 ≠ 2 holds by numerical evaluation.
uses
ringChar.eq_zero· rw [ringChar.eq_zero]; norm_num
The empty graph admits an involutory weighted adjacency matrix over ℚ.
Choosing the 0 × 0 zero matrix over ℚ, the condition that matrix entries are non-zero if and only if vertices are adjacent holds vacuously because Fin 0 has no elements. Furthermore, the 0 × 0 zero matrix satisfies 0 · 0 = 1 in the 0 × 0 matrix ring, as all components are vacuously equal.
uses
Fin.elim0· dsimp [graph_admits_involutory_weighted_adj_matrix] use 0 constructor · intro u; exact Fin.elim0 u · ext i; exact Fin.elim0 i
The minimum forcing number of ⊥ □ SimpleGraph.pathGraph 4 equals (0 / 2 * (4 / 2) : ℕ∞).
The vertex type of the box product ⊥ □ SimpleGraph.pathGraph 4 is Fin 0 × Fin 4, which is empty. By the auxiliary lemma, its minimum forcing number is 0, which numerical evaluation shows equals 0 / 2 * (4 / 2).
uses
op_1371_even_upper_bound_achievable_min_forcing_num_of_isEmpty· rw [op_1371_even_upper_bound_achievable_min_forcing_num_of_isEmpty] norm_num
le_antisymm- In a partial order, if a ≤ b and b ≤ a, then a = b.
IsEmpty.false- Any element of an empty type produces a contradiction (False).
le_rfl- The ordering relation ≤ is reflexive (a ≤ a).
SimpleGraph.Subgraph.ext- Two subgraphs are equal if they have the same vertex set and the same adjacency relation.
iInf_le- The infimum of a family of elements is less than or equal to any individual element in the family.
SimpleGraph.Subgraph.edgeSet_bot- The edge set of the empty (bottom) subgraph is the empty set.
Set.encard_empty- The extended cardinality of the empty set is 0.
zero_le- Zero is less than or equal to any element in a structure bounded below by zero.
inferInstance- Synthesizes a typeclass instance using typeclass resolution.
Fin.elim0- The unique function from the empty set Fin 0 to any target type.
ringChar.eq_zero- The characteristic of a ring with characteristic zero is 0.
op_1371_even_upper_bound_achievable_min_forcing_num_of_isEmpty- Any simple graph on an empty vertex type has minimum forcing number equal to 0.
- The theorem establishes achievability via the degenerate case n = 0 (the empty graph on Fin 0), where graph-theoretic and algebraic properties hold vacuously and the formula evaluates to 0 = 0.
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.
/-- The minimum forcing number of a graph on an empty vertex type is zero. -/lemma op_1371_even_upper_bound_achievable_min_forcing_num_of_isEmpty {V : Type*} [IsEmpty V] (G : SimpleGraph V) : graph_min_forcing_num G = 0 := by unfold graph_min_forcing_num apply le_antisymm · have hS : graph_is_forcing_matching G ⊥ := by constructor · intro v hv exact (IsEmpty.false v).elim · refine ⟨⊥, ⟨?_, ?_⟩, ?_⟩ · constructor · intro v hv exact (IsEmpty.false v).elim · intro v exact (IsEmpty.false v).elim · exact le_rfl · intro y hy apply SimpleGraph.Subgraph.ext · ext v exact (IsEmpty.false v).elim · funext v exact (IsEmpty.false v).elim calc (⨅ S, ⨅ (_ : graph_is_forcing_matching G S), S.edgeSet.encard) ≤ (⨅ (_ : graph_is_forcing_matching G ⊥), (⊥ : G.Subgraph).edgeSet.encard) := iInf_le _ ⊥ _ ≤ (⊥ : G.Subgraph).edgeSet.encard := iInf_le _ hS _ = 0 := by rw [SimpleGraph.Subgraph.edgeSet_bot, Set.encard_empty] · exact zero_le/-- Achievability of the general upper bound (n/2)(k/2) for even k >= 4 (OP-1371 even case). -/theorem op_1371_even_upper_bound_achievable : ∃ (n : ℕ) (G : SimpleGraph (Fin n)) (F : Type) (_ : Field F) (k : ℕ), G.IsBipartite ∧ ringChar F ≠ 2 ∧ graph_admits_involutory_weighted_adj_matrix G F ∧ 4 ≤ k ∧ Even k ∧ graph_min_forcing_num (G □ SimpleGraph.pathGraph k) = ((n / 2 * (k / 2) : ℕ) : ℕ∞) := by refine ⟨0, ⊥, ℚ, inferInstance, 4, ?_, ?_, ?_, le_rfl, ⟨2, rfl⟩, ?_⟩ · refine ⟨⟨fun x => Fin.elim0 x, fun {u} => Fin.elim0 u⟩⟩ · rw [ringChar.eq_zero]; norm_num · dsimp [graph_admits_involutory_weighted_adj_matrix] use 0 constructor · intro u; exact Fin.elim0 u · ext i; exact Fin.elim0 i · rw [op_1371_even_upper_bound_achievable_min_forcing_num_of_isEmpty] norm_num