b5_cliqueNum
ω(B_5(n_0..n_4)) = n_4 + max(n_0 + n_1, n_1 + n_3, n_2 + n_3).
Statement
theorem b5_cliqueNum (n : Fin 5 → ℕ) :
(b5_graph n).cliqueNum = n 4 + max (max (n 0 + n 1) (n 1 + n 3)) (n 2 + n 3)- Source
- arXiv:2610.21388 (Stronger spectral bound for clique number), Sec. 2.2 (structural clique number of B_t) for t = 5; serves b5_clique_bound_iff
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- b5_graphThe graph B_5(n_1..n_5) of arXiv:2610.21388: each vertex i of G_5 is replaced by a clique of n_i vertices, and cliques of adjacent…
- b5_graph_adjSanity lemma: adjacency in B_5 unfolds to: distinct, and the same block or adjacent blocks of G_5.
- g5_adjG_5 on vertices r_1, r_2, w_1, w_2, r_3 (indices 0..4): edges r_1 r_2, w_1 w_2, r_2 w_2, and r_3 adjacent to all.
- Used by 1
- b5_clique_bound_iffFor B_5(n_0..n_4) with all n_i ≥ 1, the strong spectral clique bound sqrt(Σ_{λ ≠ -1} λ^2) ≤ n(1 - 1/ω) (with Σ_{λ≠-1} λ^2 = tr(M^2) for…
The proof, explained
The graph B₅(n) is obtained from the 5-vertex base graph G₅ by replacing each vertex i with a clique of size n i, connecting vertices in different blocks whenever the corresponding blocks are adjacent in G₅. The maximal cliques of G₅ are {0, 1, 4}, {1, 3, 4}, and {2, 3, 4}, each consisting of the universal apex vertex 4 and an edge of the remaining 4-cycle path. For the lower bound on the clique number ω(B₅(n)), the full union of blocks corresponding to any of these three cliques forms a clique in B₅(n) of size n 0 + n 1 + n 4, n 1 + n 3 + n 4, or n 2 + n 3 + n 4, respectively. For the upper bound, the vertices of any maximum clique in B₅(n) must project to a clique in G₅ and hence are contained in one of these three block unions, so its size cannot exceed the maximum of the three sums. By partial order antisymmetry, the clique number equals n 4 + max(max(n 0 + n 1, n 1 + n 3), n 2 + n 3).
For any index set T ⊆ Fin 5, the cardinality of the full union of blocks over T is the sum of their sizes, ∑_{i ∈ T} n i.
Rewriting with `Finset.card_sigma` decomposes the cardinality of the sigma type into the sum of the cardinalities of each fiber `Finset.univ : Finset (Fin (n i))`. Simplification then evaluates each fiber's cardinality to n i.
uses
Finset.card_sigma/-- Cardinality of a full union of blocks: `Σ_{i ∈ T} n i`. -/ theorem b5_cliqueNum_card_sigma_univ (n : Fin 5 → ℕ) (T : Finset (Fin 5)) : (Finset.sigma T (fun i => (Finset.univ : Finset (Fin (n i))))).card = ∑ i ∈ T, n i := by rw [Finset.card_sigma] simp
The full union of blocks indexed by {0, 1, 4} contains n 0 + n 1 + n 4 vertices.
Applying the general block union cardinality formula `b5_cliqueNum_card_sigma_univ` rewrites the cardinality as the sum ∑_{i ∈ {0, 1, 4}} n i. Simplification expands this finite sum to n 0 + (n 1 + n 4), and linear integer arithmetic (`omega`) re-associates the terms to n 0 + n 1 + n 4.
uses
b5_cliqueNum_card_sigma_univ/-- The union of blocks `{0,1,4}` has `n 0 + n 1 + n 4` vertices. -/ theorem b5_cliqueNum_card_014 (n : Fin 5 → ℕ) : (Finset.sigma {0,1,4} (fun i => (Finset.univ : Finset (Fin (n i))))).card = n 0 + n 1 + n 4 := by rw [b5_cliqueNum_card_sigma_univ] simp omega
The full union of blocks indexed by {1, 3, 4} contains n 1 + n 3 + n 4 vertices.
By `b5_cliqueNum_card_sigma_univ`, the cardinality is the sum ∑_{i ∈ {1, 3, 4}} n i, which simplifies to n 1 + (n 3 + n 4), and `omega` concludes that this equals n 1 + n 3 + n 4.
uses
b5_cliqueNum_card_sigma_univ/-- The union of blocks `{1,3,4}` has `n 1 + n 3 + n 4` vertices. -/ theorem b5_cliqueNum_card_134 (n : Fin 5 → ℕ) : (Finset.sigma {1,3,4} (fun i => (Finset.univ : Finset (Fin (n i))))).card = n 1 + n 3 + n 4 := by rw [b5_cliqueNum_card_sigma_univ] simp omega
The full union of blocks indexed by {2, 3, 4} contains n 2 + n 3 + n 4 vertices.
By `b5_cliqueNum_card_sigma_univ`, the cardinality is the sum ∑_{i ∈ {2, 3, 4}} n i, simplifying to n 2 + (n 3 + n 4), which `omega` re-associates to n 2 + n 3 + n 4.
uses
b5_cliqueNum_card_sigma_univ/-- The union of blocks `{2,3,4}` has `n 2 + n 3 + n 4` vertices. -/ theorem b5_cliqueNum_card_234 (n : Fin 5 → ℕ) : (Finset.sigma {2,3,4} (fun i => (Finset.univ : Finset (Fin (n i))))).card = n 2 + n 3 + n 4 := by rw [b5_cliqueNum_card_sigma_univ] simp omega
Every clique in the base graph G₅ is a subset of {0, 1, 4}, {1, 3, 4}, or {2, 3, 4}. automation
Since G₅ has only 5 vertices, the property that every pairwise adjacent subset of vertices is contained in {0, 1, 4}, {1, 3, 4}, or {2, 3, 4} is a finite combinatorial statement. Lean's `decide` tactic checks this exhaustively by evaluating the condition on all 2⁵ = 32 subsets.
/-- The cliques of `G₅` are contained in `{0,1,4}`, `{1,3,4}` or `{2,3,4}` (finite check). -/ theorem b5_cliqueNum_block_subset : ∀ A : Finset (Fin 5), (∀ i ∈ A, ∀ j ∈ A, i ≠ j → g5_adj i j) → (A ⊆ ({0,1,4} : Finset (Fin 5)) ∨ A ⊆ ({1,3,4} : Finset (Fin 5)) ∨ A ⊆ ({2,3,4} : Finset (Fin 5))) := by decide
The full union of blocks indexed by any clique T of G₅ is a clique in B₅(n).
Take two distinct vertices x and y in the block union over T. By `b5_graph_adj`, they are adjacent in B₅(n) if either their block indices are equal (x.1 = y.1, using `Or.inl`) or their block indices are adjacent in G₅ (using `Or.inr`). A case distinction on whether x.1 = y.1 establishes the claim: if x.1 ≠ y.1, since both block indices belong to T, the hypothesis that T is a clique in G₅ implies that x.1 and y.1 are adjacent in G₅.
uses
b5_graph_adj,Or.inl,Or.inr/-- The union of any set of pairwise adjacent blocks of `G₅` is a clique of `B_5`. -/ theorem b5_cliqueNum_sigma_univ_isClique (n : Fin 5 → ℕ) (T : Finset (Fin 5)) (hT : ∀ i ∈ T, ∀ j ∈ T, i ≠ j → g5_adj i j) : (b5_graph n).IsClique ↑(Finset.sigma T (fun i => (Finset.univ : Finset (Fin (n i))))) := by intro x hx y hy hxy rw [b5_graph_adj] refine ⟨hxy, ?_⟩ by_cases h : x.1 = y.1 · exact Or.inl h · exact Or.inr (hT x.1 (Finset.mem_sigma.1 hx).1 y.1 (Finset.mem_sigma.1 hy).1 h)
To prove the clique number formula, it suffices to prove both inequalities, and the upper bound reduces to bounding the size of a maximum clique s.
The equality is split into two inequalities using partial order antisymmetry (`le_antisymm`). For the upper bound, we obtain a maximum clique s whose cardinality equals the clique number ω(B₅(n)), reducing the goal to showing |s| ≤ n 4 + max(max(n 0 + n 1, n 1 + n 3), n 2 + n 3).
uses
le_antisymmtheorem b5_cliqueNum (n : Fin 5 → ℕ) : (b5_graph n).cliqueNum = n 4 + max (max (n 0 + n 1) (n 1 + n 3)) (n 2 + n 3) := by apply le_antisymm · obtain ⟨s, hs⟩ := (b5_graph n).exists_isNClique_cliqueNum rw [← hs.card_eq]
The projection of the maximum clique s to the block indices {x.1 | x ∈ s} forms a clique in G₅.
Let i ≠ j be two distinct block indices in the projection of s, with witnesses x, y ∈ s having x.1 = i and y.1 = j. Because i ≠ j, x and y are distinct. Since s is a clique, x and y are adjacent in B₅(n). By `b5_graph_adj`, this adjacency means x.1 = y.1 or g5_adj x.1 y.1. Since x.1 = y.1 contradicts i ≠ j, the only possibility is that g5_adj i j holds.
uses
b5_graph_adjhave hclique : ∀ i ∈ s.image (fun x => x.1), ∀ j ∈ s.image (fun x => x.1), i ≠ j → g5_adj i j := by intro i hi j hj hij obtain ⟨x, hx, rfl⟩ := Finset.mem_image.1 hi obtain ⟨y, hy, rfl⟩ := Finset.mem_image.1 hj have hxy : x ≠ y := by rintro rfl; exact hij rfl have h := (b5_graph_adj n x y).1 (hs.isClique hx hy hxy) rcases h.2 with h' | h' · exact absurd h' hij · exact h'
When the block projection of s is contained in {0, 1, 4}, |s| is bounded by the desired formula.
Using `b5_cliqueNum_block_subset`, we perform a three-way case analysis on the projection of s. In the first case where the projection is a subset of {0, 1, 4}, every element x ∈ s has x.1 ∈ {0, 1, 4} and x.2 ∈ Finset.univ (`Finset.mem_univ`), so s is a subset of the full block union over {0, 1, 4}. By monotonicity of cardinality (`Finset.card_le_card`), |s| is bounded by the cardinality of that union, which is n 0 + n 1 + n 4 by `b5_cliqueNum_card_014`. Linear arithmetic (`omega`) confirms n 0 + n 1 + n 4 ≤ n 4 + max(max(n 0 + n 1, n 1 + n 3), n 2 + n 3).
uses
b5_cliqueNum_block_subset,Finset.mem_univ,Finset.card_le_card,b5_cliqueNum_card_014rcases b5_cliqueNum_block_subset (s.image fun x => x.1) hclique with h014 | h134 | h234 · have hsub : s ⊆ Finset.sigma {0,1,4} (fun i => (Finset.univ : Finset (Fin (n i)))) := by intro x hx exact Finset.mem_sigma.2 ⟨h014 (Finset.mem_image.2 ⟨x, hx, rfl⟩), Finset.mem_univ x.2⟩ calc s.card ≤ _ := Finset.card_le_card hsub _ = n 0 + n 1 + n 4 := b5_cliqueNum_card_014 n _ ≤ n 4 + max (max (n 0 + n 1) (n 1 + n 3)) (n 2 + n 3) := by omega
When the block projection of s is contained in {1, 3, 4}, |s| is bounded by the desired formula.
In the second case of the projection case split, s is a subset of the full block union over {1, 3, 4} (since x.2 ∈ Finset.univ by `Finset.mem_univ`). Monotonicity of cardinality (`Finset.card_le_card`) and the size formula `b5_cliqueNum_card_134` give |s| ≤ n 1 + n 3 + n 4. Linear arithmetic (`omega`) verifies that this is at most n 4 + max(max(n 0 + n 1, n 1 + n 3), n 2 + n 3).
uses
Finset.mem_univ,Finset.card_le_card,b5_cliqueNum_card_134· have hsub : s ⊆ Finset.sigma {1,3,4} (fun i => (Finset.univ : Finset (Fin (n i)))) := by intro x hx exact Finset.mem_sigma.2 ⟨h134 (Finset.mem_image.2 ⟨x, hx, rfl⟩), Finset.mem_univ x.2⟩ calc s.card ≤ _ := Finset.card_le_card hsub _ = n 1 + n 3 + n 4 := b5_cliqueNum_card_134 n _ ≤ n 4 + max (max (n 0 + n 1) (n 1 + n 3)) (n 2 + n 3) := by omega
When the block projection of s is contained in {2, 3, 4}, |s| is bounded by the desired formula.
In the third case, s is contained in the block union over {2, 3, 4} (`Finset.mem_univ`). By `Finset.card_le_card` and `b5_cliqueNum_card_234`, |s| ≤ n 2 + n 3 + n 4. Linear arithmetic (`omega`) shows this is at most n 4 + max(max(n 0 + n 1, n 1 + n 3), n 2 + n 3).
uses
Finset.mem_univ,Finset.card_le_card,b5_cliqueNum_card_234· have hsub : s ⊆ Finset.sigma {2,3,4} (fun i => (Finset.univ : Finset (Fin (n i)))) := by intro x hx exact Finset.mem_sigma.2 ⟨h234 (Finset.mem_image.2 ⟨x, hx, rfl⟩), Finset.mem_univ x.2⟩ calc s.card ≤ _ := Finset.card_le_card hsub _ = n 2 + n 3 + n 4 := b5_cliqueNum_card_234 n _ ≤ n 4 + max (max (n 0 + n 1) (n 1 + n 3)) (n 2 + n 3) := by omega
The lower bound n 4 + max(max(n 0 + n 1, n 1 + n 3), n 2 + n 3) ≤ ω(B₅(n)) holds.
The sets {0, 1, 4}, {1, 3, 4}, and {2, 3, 4} are pairwise adjacent in G₅ (verified by `decide`), so by `b5_cliqueNum_sigma_univ_isClique`, each of their full block unions forms a clique in B₅(n), whose cardinality is at most the clique number. Using the cardinality formulas `b5_cliqueNum_card_014`, `b5_cliqueNum_card_134`, and `b5_cliqueNum_card_234`, this yields n 0 + n 1 + n 4 ≤ ω(B₅(n)), n 1 + n 3 + n 4 ≤ ω(B₅(n)), and n 2 + n 3 + n 4 ≤ ω(B₅(n)). Finally, linear arithmetic with max (`omega`) combines these three bounds to conclude that n 4 + max(max(n 0 + n 1, n 1 + n 3), n 2 + n 3) ≤ ω(B₅(n)).
uses
b5_cliqueNum_sigma_univ_isClique,b5_cliqueNum_card_014,b5_cliqueNum_card_134,b5_cliqueNum_card_234· have h1 := (b5_cliqueNum_sigma_univ_isClique n {0,1,4} (by decide)).card_le_cliqueNum have h2 := (b5_cliqueNum_sigma_univ_isClique n {1,3,4} (by decide)).card_le_cliqueNum have h3 := (b5_cliqueNum_sigma_univ_isClique n {2,3,4} (by decide)).card_le_cliqueNum rw [b5_cliqueNum_card_014 n] at h1 rw [b5_cliqueNum_card_134 n] at h2 rw [b5_cliqueNum_card_234 n] at h3 omega
Finset.card_sigma- The cardinality of a dependent sum (disjoint union) of finite sets is the sum of the cardinalities of the fibers over the indexing set.
b5_cliqueNum_card_sigma_univ- For any set of block indices T, the cardinality of the full union of the corresponding blocks is the sum of their sizes, ∑_{i ∈ T} n i.
b5_graph_adj- Two distinct vertices x and y in B₅(n) are adjacent if and only if they belong to the same block or their respective blocks are adjacent in G₅.
Or.inl- From a proof of proposition a, infers the disjunction a ∨ b.
Or.inr- From a proof of proposition b, infers the disjunction a ∨ b.
le_antisymm- In a partially ordered set, if a ≤ b and b ≤ a, then a = b.
b5_cliqueNum_block_subset- Every clique of vertices in the 5-vertex base graph G₅ is contained in at least one of the three sets {0, 1, 4}, {1, 3, 4}, or {2, 3, 4}.
Finset.mem_univ- Every element of a finite type belongs to the universal finset of that type.
Finset.card_le_card- If a finite set s is a subset of a finite set t, then the cardinality of s is at most the cardinality of t.
b5_cliqueNum_card_014- The full union of the blocks indexed by {0, 1, 4} has exactly n 0 + n 1 + n 4 vertices.
b5_cliqueNum_card_134- The full union of the blocks indexed by {1, 3, 4} has exactly n 1 + n 3 + n 4 vertices.
b5_cliqueNum_card_234- The full union of the blocks indexed by {2, 3, 4} has exactly n 2 + n 3 + n 4 vertices.
b5_cliqueNum_sigma_univ_isClique- If T is a set of pairwise adjacent vertices in G₅, then the full union of the blocks indexed by T forms a clique in B₅(n).
- The classification of all cliques of the base 5-vertex graph G₅ into subsets of {0, 1, 4}, {1, 3, 4}, or {2, 3, 4} (lemma `b5_cliqueNum_block_subset`, line 36) is carried out by the decision procedure `decide`, which exhaustively evaluates the condition on all 32 subsets of Fin 5 rather than using paper-style case analysis.
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.
/-- Cardinality of a full union of blocks: `Σ_{i ∈ T} n i`. -/theorem b5_cliqueNum_card_sigma_univ (n : Fin 5 → ℕ) (T : Finset (Fin 5)) : (Finset.sigma T (fun i => (Finset.univ : Finset (Fin (n i))))).card = ∑ i ∈ T, n i := by rw [Finset.card_sigma] simp/-- The union of blocks `{0,1,4}` has `n 0 + n 1 + n 4` vertices. -/theorem b5_cliqueNum_card_014 (n : Fin 5 → ℕ) : (Finset.sigma {0,1,4} (fun i => (Finset.univ : Finset (Fin (n i))))).card = n 0 + n 1 + n 4 := by rw [b5_cliqueNum_card_sigma_univ] simp omega/-- The union of blocks `{1,3,4}` has `n 1 + n 3 + n 4` vertices. -/theorem b5_cliqueNum_card_134 (n : Fin 5 → ℕ) : (Finset.sigma {1,3,4} (fun i => (Finset.univ : Finset (Fin (n i))))).card = n 1 + n 3 + n 4 := by rw [b5_cliqueNum_card_sigma_univ] simp omega/-- The union of blocks `{2,3,4}` has `n 2 + n 3 + n 4` vertices. -/theorem b5_cliqueNum_card_234 (n : Fin 5 → ℕ) : (Finset.sigma {2,3,4} (fun i => (Finset.univ : Finset (Fin (n i))))).card = n 2 + n 3 + n 4 := by rw [b5_cliqueNum_card_sigma_univ] simp omega/-- The cliques of `G₅` are contained in `{0,1,4}`, `{1,3,4}` or `{2,3,4}` (finite check). -/theorem b5_cliqueNum_block_subset : ∀ A : Finset (Fin 5), (∀ i ∈ A, ∀ j ∈ A, i ≠ j → g5_adj i j) → (A ⊆ ({0,1,4} : Finset (Fin 5)) ∨ A ⊆ ({1,3,4} : Finset (Fin 5)) ∨ A ⊆ ({2,3,4} : Finset (Fin 5))) := by decide/-- The union of any set of pairwise adjacent blocks of `G₅` is a clique of `B_5`. -/theorem b5_cliqueNum_sigma_univ_isClique (n : Fin 5 → ℕ) (T : Finset (Fin 5)) (hT : ∀ i ∈ T, ∀ j ∈ T, i ≠ j → g5_adj i j) : (b5_graph n).IsClique ↑(Finset.sigma T (fun i => (Finset.univ : Finset (Fin (n i))))) := by intro x hx y hy hxy rw [b5_graph_adj] refine ⟨hxy, ?_⟩ by_cases h : x.1 = y.1 · exact Or.inl h · exact Or.inr (hT x.1 (Finset.mem_sigma.1 hx).1 y.1 (Finset.mem_sigma.1 hy).1 h)theorem b5_cliqueNum (n : Fin 5 → ℕ) : (b5_graph n).cliqueNum = n 4 + max (max (n 0 + n 1) (n 1 + n 3)) (n 2 + n 3) := by apply le_antisymm · obtain ⟨s, hs⟩ := (b5_graph n).exists_isNClique_cliqueNum rw [← hs.card_eq] have hclique : ∀ i ∈ s.image (fun x => x.1), ∀ j ∈ s.image (fun x => x.1), i ≠ j → g5_adj i j := by intro i hi j hj hij obtain ⟨x, hx, rfl⟩ := Finset.mem_image.1 hi obtain ⟨y, hy, rfl⟩ := Finset.mem_image.1 hj have hxy : x ≠ y := by rintro rfl; exact hij rfl have h := (b5_graph_adj n x y).1 (hs.isClique hx hy hxy) rcases h.2 with h' | h' · exact absurd h' hij · exact h' rcases b5_cliqueNum_block_subset (s.image fun x => x.1) hclique with h014 | h134 | h234 · have hsub : s ⊆ Finset.sigma {0,1,4} (fun i => (Finset.univ : Finset (Fin (n i)))) := by intro x hx exact Finset.mem_sigma.2 ⟨h014 (Finset.mem_image.2 ⟨x, hx, rfl⟩), Finset.mem_univ x.2⟩ calc s.card ≤ _ := Finset.card_le_card hsub _ = n 0 + n 1 + n 4 := b5_cliqueNum_card_014 n _ ≤ n 4 + max (max (n 0 + n 1) (n 1 + n 3)) (n 2 + n 3) := by omega · have hsub : s ⊆ Finset.sigma {1,3,4} (fun i => (Finset.univ : Finset (Fin (n i)))) := by intro x hx exact Finset.mem_sigma.2 ⟨h134 (Finset.mem_image.2 ⟨x, hx, rfl⟩), Finset.mem_univ x.2⟩ calc s.card ≤ _ := Finset.card_le_card hsub _ = n 1 + n 3 + n 4 := b5_cliqueNum_card_134 n _ ≤ n 4 + max (max (n 0 + n 1) (n 1 + n 3)) (n 2 + n 3) := by omega · have hsub : s ⊆ Finset.sigma {2,3,4} (fun i => (Finset.univ : Finset (Fin (n i)))) := by intro x hx exact Finset.mem_sigma.2 ⟨h234 (Finset.mem_image.2 ⟨x, hx, rfl⟩), Finset.mem_univ x.2⟩ calc s.card ≤ _ := Finset.card_le_card hsub _ = n 2 + n 3 + n 4 := b5_cliqueNum_card_234 n _ ≤ n 4 + max (max (n 0 + n 1) (n 1 + n 3)) (n 2 + n 3) := by omega · have h1 := (b5_cliqueNum_sigma_univ_isClique n {0,1,4} (by decide)).card_le_cliqueNum have h2 := (b5_cliqueNum_sigma_univ_isClique n {1,3,4} (by decide)).card_le_cliqueNum have h3 := (b5_cliqueNum_sigma_univ_isClique n {2,3,4} (by decide)).card_le_cliqueNum rw [b5_cliqueNum_card_014 n] at h1 rw [b5_cliqueNum_card_134 n] at h2 rw [b5_cliqueNum_card_234 n] at h3 omega