b3_cliqueNum
The clique number of B_3(n_0, n_1, n_2) is max(n_0 + n_2, n_1 + n_2).
Statement
theorem b3_cliqueNum (n : Fin 3 → ℕ) :
(b3_graph n).cliqueNum = max (n 0 + n 2) (n 1 + n 2)- Source
- arXiv:2610.21388 (Stronger spectral bound for clique number), Sec. 2.2 (structural value of ω for B_3) / Theorem 3.1; serves b3_sqrt_trace_quotient_sq_le_clique_bound
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- b3_graphThe graph B_3(n_0, n_1, n_2) on the disjoint union of blocks of sizes n_0, n_1, n_2: two distinct vertices are adjacent iff they lie in…
- b3_graph_adjSanity lemma: adjacency in B_3(n_0,n_1,n_2) unfolds to: distinct, and same block or one endpoint in block 2.
- Used by 2
- b3_sqrt_trace_quotient_sq_gt_clique_bound_of_one_oneIf n_0 = n_1 = 1 and n_2 ≥ 1, then for G = B_3(1, 1, n_2) the bound fails strictly: n(1 - 1/ω(G)) < sqrt(λ_1^2 + λ_2^2 + λ_3^2) (with the…
- b3_sqrt_trace_quotient_sq_le_clique_boundLet n_0, n_1, n_2 be positive integers with (n_0, n_1) ≠ (1, 1), G = B_3(n_0, n_1, n_2) of order n = n_0 + n_1 + n_2, and λ_1, λ_2, λ_3…
The proof, explained
The theorem establishes that the clique number of the graph B_3(n) is max(n_0 + n_2, n_1 + n_2) by proving matching upper and lower bounds. For the lower bound, the vertices in blocks {0, 2} and {1, 2} each form cliques of sizes n_0 + n_2 and n_1 + n_2 respectively, so the clique number is at least their maximum. For the upper bound, no edges exist between vertices of block 0 and block 1, so any clique can intersect at most one of those two blocks; hence every clique is contained in either blocks {0, 2} or blocks {1, 2}, restricting its size to at most max(n_0 + n_2, n_1 + n_2).
The total number of vertices in blocks i and 2 (for i ≠ 2) is n(i) + n(2).
The set of vertices belonging to blocks {i, 2} is represented as a sigma type over the pair {i, 2}. Using Finset.card_sigma to convert the cardinality into a sum over the index set and Finset.sum_pair to expand the sum over the two distinct indices, simp evaluates the size of each fiber Fin(n j) to n(j), giving n(i) + n(2).
uses
Finset.card_sigma,Finset.sum_pairrw [Finset.card_sigma, Finset.sum_pair hi] simp
For any block index i, the vertices belonging to blocks {i, 2} form a clique in B_3(n).
Given two distinct vertices x and y with indices in {i, 2}, simp unpacks their membership to x.1 ∈ {i, 2} and y.1 ∈ {i, 2}. By definition of the graph (b3_graph_adj), distinct vertices are adjacent if and only if they share a block index or at least one vertex is in block 2. A case split on the two possible indices for x and y reveals that in every case they either share index i, share index 2, or one has index 2, satisfying the adjacency condition.
uses
Finset.coe_sigma,Set.mem_sigma_iff,Finset.mem_coe,Finset.mem_insert,Finset.mem_singleton,b3_graph_adjintro x hx y hy hxy simp only [Finset.coe_sigma, Set.mem_sigma_iff, Finset.mem_coe, Finset.mem_insert, Finset.mem_singleton] at hx hy rw [b3_graph_adj] refine ⟨hxy, ?_⟩ rcases hx.1 with h | h <;> rcases hy.1 with h' | h' <;> simp [h, h']
To compute the clique number, it suffices to prove matching upper and lower bounds; we begin the upper bound by choosing a maximum clique s and testing whether it contains a vertex from block 0.
By le_antisymm, the equality reduces to proving cliqueNum ≤ max(n 0 + n 2, n 1 + n 2) and max(n 0 + n 2, n 1 + n 2) ≤ cliqueNum. For the upper bound, we pick a maximum clique s such that |s| = cliqueNum and perform a case split on whether s contains any vertex from block 0.
uses
le_antisymmapply le_antisymm · obtain ⟨s, hs⟩ := (b3_graph n).exists_isNClique_cliqueNum rw [← hs.card_eq] by_cases h0 : ∃ x ∈ s, x.1 = 0
If the maximum clique s contains a vertex in block 0, then s is entirely contained in blocks {0, 2}, so |s| ≤ n 0 + n 2 ≤ max(n 0 + n 2, n 1 + n 2).
Fix x ∈ s with x.1 = 0. For any other vertex y ∈ s, if y were not in blocks {0, 2}, its block index would have to be 1. But vertices in block 0 and block 1 have distinct indices and neither is 2, so by b3_graph_adj they cannot be adjacent, contradicting that s is a clique. Hence every vertex of s lies in blocks {0, 2}, which means s ⊆ V_0 ∪ V_2. By Finset.card_le_card and b3_card_pair, |s| ≤ n 0 + n 2, which is bounded above by max(n 0 + n 2, n 1 + n 2) using le_max_left.
uses
Finset.mem_sigma,Finset.mem_insert,Finset.mem_singleton,Finset.mem_univ,and_true,b3_graph_adj,Finset.card_le_card,b3_card_pair,le_max_leftobtain ⟨x, hx, hx0⟩ := h0 have hsub : s ⊆ ({0, 2} : Finset (Fin 3)).sigma fun j => Finset.univ := by intro y hy simp only [Finset.mem_sigma, Finset.mem_insert, Finset.mem_singleton, Finset.mem_univ, and_true] by_contra hne push Not at hne have hy1 : y.1 = 1 := by omega have hxy : x ≠ y := by rintro rfl; rw [hx0] at hy1; exact absurd hy1 (by decide) have := (b3_graph_adj n x y).1 (hs.isClique hx hy hxy) rcases this.2 with h | h | h <;> simp_all calc s.card ≤ _ := Finset.card_le_card hsub _ = n 0 + n 2 := b3_card_pair n 0 (by decide) _ ≤ _ := le_max_left _ _
If the maximum clique s contains no vertex in block 0, then s is entirely contained in blocks {1, 2}, so |s| ≤ n 1 + n 2 ≤ max(n 0 + n 2, n 1 + n 2).
When no vertex of s has block index 0, every vertex y ∈ s must have block index 1 or 2. Thus s is a subset of the vertices in blocks {1, 2}. Finset.card_le_card and b3_card_pair bound |s| by n 1 + n 2, which is at most max(n 0 + n 2, n 1 + n 2) by le_max_right.
uses
Finset.mem_sigma,Finset.mem_insert,Finset.mem_singleton,Finset.mem_univ,and_true,Finset.card_le_card,b3_card_pair,le_max_right· push Not at h0 have hsub : s ⊆ ({1, 2} : Finset (Fin 3)).sigma fun j => Finset.univ := by intro y hy simp only [Finset.mem_sigma, Finset.mem_insert, Finset.mem_singleton, Finset.mem_univ, and_true] have := h0 y hy omega calc s.card ≤ _ := Finset.card_le_card hsub _ = n 1 + n 2 := b3_card_pair n 1 (by decide) _ ≤ _ := le_max_right _ _
The clique number is at least max(n 0 + n 2, n 1 + n 2).
Using max_le, it suffices to show that n 0 + n 2 ≤ cliqueNum and n 1 + n 2 ≤ cliqueNum. By b3_pair_isClique and b3_card_pair, the vertices in blocks {0, 2} form a clique of size n 0 + n 2, and the vertices in blocks {1, 2} form a clique of size n 1 + n 2; since the size of any clique is at most the clique number, both inequalities hold.
uses
max_le,b3_card_pair,b3_pair_isClique· apply max_le · rw [← b3_card_pair n 0 (by decide)] exact (b3_pair_isClique n 0).card_le_cliqueNum · rw [← b3_card_pair n 1 (by decide)] exact (b3_pair_isClique n 1).card_le_cliqueNum
Finset.card_sigma- The cardinality of a disjoint sum (sigma type) of finite sets is the sum of the cardinalities of the fibers over the index set.
Finset.sum_pair- The sum of a function over an unordered pair of distinct elements {a, b} equals f(a) + f(b).
Finset.coe_sigma- Coercing a finite disjoint union of finsets to a set yields the set-theoretic sigma type of the coerced sets.
Set.mem_sigma_iff- An element belongs to a dependent sum of sets if and only if its index belongs to the base set and its fiber component belongs to the corresponding fiber set.
Finset.mem_coe- Membership of an element in a coerced finset is equivalent to membership in the finset itself.
Finset.mem_insert- An element belongs to insert(b, s) if and only if it equals b or belongs to s.
Finset.mem_singleton- An element belongs to the singleton set {a} if and only if it equals a.
b3_graph_adj- Two distinct vertices in B_3(n) are adjacent if and only if they belong to the same block or at least one of them belongs to block 2.
le_antisymm- If a ≤ b and b ≤ a in a partial order, then a = b.
Finset.mem_sigma- An element belongs to a finite sigma set if and only if its index is in the base finset and its fiber element is in the fiber finset.
Finset.mem_univ- Every element of a finite type belongs to the universal finset Finset.univ.
and_true- Conjunction of any proposition with True is equivalent to the proposition itself.
Finset.card_le_card- If a finite set s is a subset of t, then the cardinality of s is at most the cardinality of t.
b3_card_pair- For any block index i ≠ 2, the number of vertices in blocks {i, 2} is n(i) + n(2).
le_max_left- For any elements a and b in a linear order, a ≤ max(a, b).
le_max_right- For any elements a and b in a linear order, b ≤ max(a, b).
max_le- If a ≤ c and b ≤ c in a linear order, then max(a, b) ≤ c.
b3_pair_isClique- For any index i, the set of vertices in blocks {i, 2} forms a clique in B_3(n).
- In B_3(n), distinct vertices in the same block are adjacent, and vertices in block 2 are adjacent to all other vertices. Crucially, there are no edges between vertices of block 0 and vertices of block 1, which implies no clique can contain vertices from both blocks.
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.
theorem b3_card_pair (n : Fin 3 → ℕ) (i : Fin 3) (hi : i ≠ 2) : (({i, 2} : Finset (Fin 3)).sigma fun j => (Finset.univ : Finset (Fin (n j)))).card = n i + n 2 := by rw [Finset.card_sigma, Finset.sum_pair hi] simptheorem b3_pair_isClique (n : Fin 3 → ℕ) (i : Fin 3) : (b3_graph n).IsClique ((({i, 2} : Finset (Fin 3)).sigma fun j => (Finset.univ : Finset (Fin (n j)))) : Set (Σ j : Fin 3, Fin (n j))) := by intro x hx y hy hxy simp only [Finset.coe_sigma, Set.mem_sigma_iff, Finset.mem_coe, Finset.mem_insert, Finset.mem_singleton] at hx hy rw [b3_graph_adj] refine ⟨hxy, ?_⟩ rcases hx.1 with h | h <;> rcases hy.1 with h' | h' <;> simp [h, h']theorem b3_cliqueNum (n : Fin 3 → ℕ) : (b3_graph n).cliqueNum = max (n 0 + n 2) (n 1 + n 2) := by apply le_antisymm · obtain ⟨s, hs⟩ := (b3_graph n).exists_isNClique_cliqueNum rw [← hs.card_eq] by_cases h0 : ∃ x ∈ s, x.1 = 0 · -- then no vertex of block 1 obtain ⟨x, hx, hx0⟩ := h0 have hsub : s ⊆ ({0, 2} : Finset (Fin 3)).sigma fun j => Finset.univ := by intro y hy simp only [Finset.mem_sigma, Finset.mem_insert, Finset.mem_singleton, Finset.mem_univ, and_true] by_contra hne push Not at hne have hy1 : y.1 = 1 := by omega have hxy : x ≠ y := by rintro rfl; rw [hx0] at hy1; exact absurd hy1 (by decide) have := (b3_graph_adj n x y).1 (hs.isClique hx hy hxy) rcases this.2 with h | h | h <;> simp_all calc s.card ≤ _ := Finset.card_le_card hsub _ = n 0 + n 2 := b3_card_pair n 0 (by decide) _ ≤ _ := le_max_left _ _ · push Not at h0 have hsub : s ⊆ ({1, 2} : Finset (Fin 3)).sigma fun j => Finset.univ := by intro y hy simp only [Finset.mem_sigma, Finset.mem_insert, Finset.mem_singleton, Finset.mem_univ, and_true] have := h0 y hy omega calc s.card ≤ _ := Finset.card_le_card hsub _ = n 1 + n 2 := b3_card_pair n 1 (by decide) _ ≤ _ := le_max_right _ _ · apply max_le · rw [← b3_card_pair n 0 (by decide)] exact (b3_pair_isClique n 0).card_le_cliqueNum · rw [← b3_card_pair n 1 (by decide)] exact (b3_pair_isClique n 1).card_le_cliqueNum