b4_cliqueNum
The clique number of B_4(n_0, n_1, n_2, n_3) is max(max(n_0 + n_1, n_1 + n_3), n_2 + n_3).
Statement
theorem b4_cliqueNum (n : Fin 4 → ℕ) :
(b4_graph n).cliqueNum = max (max (n 0 + n 1) (n 1 + n 3)) (n 2 + n 3)- Formalizes
- arXiv:2610.21388, Section 2.2
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- b4_graphThe graph B_4(n_0, n_1, n_2, n_3) on the disjoint union of four complete blocks of sizes n_0, n_1, n_2, n_3, with edges between blocks 0…
- b4_graph_adjSanity lemma: two distinct vertices in B_4(n) are adjacent if and only if they belong to the same block, or one is in block 0 and the…
- Used by 2
- b4_sqrt_trace_quotient_sq_gt_clique_bound_of_one_oneFor n : Fin 4 → ℕ with n 0 = 1, n 1 = 1, n 2 = 1, and n 3 = 1, (∑ i, (n i : ℝ)) * (1 - 1 / ((b4_graph n).cliqueNum : ℝ)) < Real.sqrt…
- b4_sqrt_trace_quotient_sq_le_clique_boundFor any n : Fin 4 → ℕ with 1 ≤ n i for all i : Fin 4 and ¬ (n 0 = 1 ∧ n 1 = 1 ∧ n 2 = 1 ∧ n 3 = 1), Real.sqrt ((b4_quotient_matrix n ^…
Read back from the Lean
For every function $n : \text{Fin } 4 \to \mathbb{N}$, the clique number of the simple graph b4_graph n is equal to $\max(\max(n(0) + n(1), n(1) + n(3)), n(2) + n(3))$.
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 graph B_4(n) is formed by four parts where each part is a clique and the edges between parts form the path 0 - 1 - 3 - 2. Since this 4-vertex path contains no triangles, any clique in B_4(n) can only intersect parts that form an edge of the path, namely {0, 1}, {1, 3}, or {2, 3}. A case analysis shows that any clique is contained in one of these three pair blocks, bounding its size by max(max(n_0 + n_1, n_1 + n_3), n_2 + n_3), while each pair block provides a matching lower bound clique of size n_a + n_b.
The cardinality of the pair block of two distinct parts a and b is n(a) + n(b).
The pair block is defined as a sigma-finset over the pair {a, b}. Its cardinality is the sum of the cardinalities of the two fibers, which simplifies to n(a) + n(b) because a ≠ b.
uses
b4_cliqueNum_pairBlock,card_sigmarw [b4_cliqueNum_pairBlock, card_sigma] simp [hab]
A vertex belongs to the pair block of a and b if and only if its part index is a or b.
By definition of the sigma-finset over {a, b}, a vertex (i, x) belongs to the block precisely when i ∈ {a, b}, which simplifies to i = a ∨ i = b.
uses
b4_cliqueNum_pairBlocksimp [b4_cliqueNum_pairBlock]The pair block of parts 0 and 1 forms a clique in B_4(n).
For any two distinct vertices in parts 0 and 1, their part indices are each 0 or 1. In all four cases, the vertices either share the same part index or belong to the adjacent parts 0 and 1, both of which satisfy the adjacency condition for B_4(n).
uses
b4_graph_adjintro x hx y hy hne simp only [b4_cliqueNum_pairBlock, mem_coe, mem_sigma, mem_insert, mem_singleton, mem_univ, and_true] at hx hy rw [b4_graph_adj] refine ⟨hne, ?_⟩ rcases hx with hx | hx <;> rcases hy with hy | hy · left; rw [hx, hy] · right; left; exact ⟨hx, hy⟩ · right; right; left; exact ⟨hx, hy⟩ · left; rw [hx, hy]
The pair block of parts 1 and 3 forms a clique in B_4(n).
Any two distinct vertices whose indices belong to {1, 3} either share a part index or form the pair {1, 3}, which is an edge in the underlying path of parts; thus they are adjacent in B_4(n).
uses
b4_graph_adjintro x hx y hy hne simp only [b4_cliqueNum_pairBlock, mem_coe, mem_sigma, mem_insert, mem_singleton, mem_univ, and_true] at hx hy rw [b4_graph_adj] refine ⟨hne, ?_⟩ rcases hx with hx | hx <;> rcases hy with hy | hy · left; rw [hx, hy] · right; right; right; left; exact ⟨hx, hy⟩ · right; right; right; right; left; exact ⟨hx, hy⟩ · left; rw [hx, hy]
The pair block of parts 2 and 3 forms a clique in B_4(n).
Any two distinct vertices whose indices belong to {2, 3} are either in the same part or in the adjacent parts 2 and 3, and are therefore adjacent.
uses
b4_graph_adjintro x hx y hy hne simp only [b4_cliqueNum_pairBlock, mem_coe, mem_sigma, mem_insert, mem_singleton, mem_univ, and_true] at hx hy rw [b4_graph_adj] refine ⟨hne, ?_⟩ rcases hx with hx | hx <;> rcases hy with hy | hy · left; rw [hx, hy] · right; right; right; right; right; left; exact ⟨hx, hy⟩ · right; right; right; right; right; right; exact ⟨hx, hy⟩ · left; rw [hx, hy]
Any clique containing a vertex from part 0 is a subset of the pair block of parts 0 and 1.
Let x be a clique vertex in part 0. Any other vertex y in the clique is distinct from x and therefore adjacent to x. Unfolding the definition of adjacency shows that part 0 is only adjacent to itself and part 1. Hence every vertex y in the clique has part index 0 or 1.
uses
b4_cliqueNum_mem_pairBlock_iff,b4_graph_adjintro y hy rw [b4_cliqueNum_mem_pairBlock_iff] by_cases hy0 : y.1 = 0 · left; exact hy0 · right have hne : x ≠ y := by intro h; subst h; exact hy0 hx0 have hadj := hc hx hy hne rw [b4_graph_adj] at hadj rcases hadj.2 with h | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ · rw [hx0] at h; exact (hy0 h.symm).elim · exact h2 · rw [hx0] at h1; contradiction · rw [hx0] at h1; contradiction · rw [hx0] at h1; contradiction · rw [hx0] at h1; contradiction · rw [hx0] at h1; contradiction
Any clique with no vertices in part 0 that contains a vertex from part 1 is a subset of the pair block of parts 1 and 3.
Let x be a clique vertex in part 1. Every distinct vertex y in the clique must be adjacent to x, so y's part index can only be 0, 1, or 3. Since the clique contains no vertex in part 0 by hypothesis, y must belong to part 1 or part 3.
uses
b4_cliqueNum_mem_pairBlock_iff,b4_graph_adjintro y hy rw [b4_cliqueNum_mem_pairBlock_iff] by_cases hy1 : y.1 = 1 · left; exact hy1 · right have hne : x ≠ y := by intro h; subst h; exact hy1 hx1 have hadj := hc hx hy hne rw [b4_graph_adj] at hadj have hy0 : y.1 ≠ 0 := h_no_0 y hy rcases hadj.2 with h | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ · rw [hx1] at h; exact (hy1 h.symm).elim · rw [hx1] at h1; contradiction · rw [h2] at hy0; contradiction · exact h2 · rw [hx1] at h1; contradiction · rw [hx1] at h1; contradiction · rw [hx1] at h1; contradiction
Any clique containing no vertices from parts 0 or 1 is a subset of the pair block of parts 2 and 3. automation
Every vertex y in the clique has a part index in {0, 1, 2, 3}. Since indices 0 and 1 are excluded by hypothesis, linear arithmetic over Fin 4 leaves only 2 and 3 as possible values.
uses
b4_cliqueNum_mem_pairBlock_iffintro y hy rw [b4_cliqueNum_mem_pairBlock_iff] have hy0 := h_no_0 y hy have hy1 := h_no_1 y hy omega
Every clique s has cardinality at most max(max(n_0 + n_1, n_1 + n_3), n_2 + n_3).
We case-split on which parts meet s: if s meets part 0, then s ⊆ pairBlock(0, 1) and |s| ≤ n_0 + n_1; if s avoids part 0 but meets part 1, then s ⊆ pairBlock(1, 3) and |s| ≤ n_1 + n_3; otherwise s avoids parts 0 and 1, so s ⊆ pairBlock(2, 3) and |s| ≤ n_2 + n_3. In all three cases, |s| is bounded by the maximum of the three sums.
uses
b4_cliqueNum_card_pairBlock,b4_cliqueNum_case_0,b4_cliqueNum_case_1,b4_cliqueNum_case_23,card_le_card,le_max_left,le_max_of_le_left,le_max_right,le_transby_cases h0 : ∃ x ∈ s, (x : Σ i : Fin 4, Fin (n i)).1 = 0 · rcases h0 with ⟨x, hx, hx0⟩ have hsub := b4_cliqueNum_case_0 n s hc x hx hx0 have hle := card_le_card hsub rw [b4_cliqueNum_card_pairBlock n 0 1 (by decide)] at hle exact le_trans hle (le_max_of_le_left (le_max_left _ _)) · push Not at h0 by_cases h1 : ∃ x ∈ s, (x : Σ i : Fin 4, Fin (n i)).1 = 1 · rcases h1 with ⟨x, hx, hx1⟩ have hsub := b4_cliqueNum_case_1 n s hc h0 x hx hx1 have hle := card_le_card hsub rw [b4_cliqueNum_card_pairBlock n 1 3 (by decide)] at hle exact le_trans hle (le_max_of_le_left (le_max_right _ _)) · push Not at h1 have hsub := b4_cliqueNum_case_23 n s h0 h1 have hle := card_le_card hsub rw [b4_cliqueNum_card_pairBlock n 2 3 (by decide)] at hle exact le_trans hle (le_max_right _ _)
The clique number of B_4(n) is at most max(max(n_0 + n_1, n_1 + n_3), n_2 + n_3).
By definition of the clique number, there exists a maximum clique s with |s| = cliqueNum. Applying the clique size bound to s yields the upper bound on the clique number.
uses
b4_cliqueNum_card_le_of_isClique,isNClique_iff,le_antisymmapply le_antisymm · obtain ⟨s, hs⟩ := (b4_graph n).exists_isNClique_cliqueNum rw [isNClique_iff] at hs rw [← hs.2] exact b4_cliqueNum_card_le_of_isClique n s hs.1
The clique number of B_4(n) equals max(max(n_0 + n_1, n_1 + n_3), n_2 + n_3).
The three pair blocks {0, 1}, {1, 3}, and {2, 3} are explicit cliques of sizes n_0 + n_1, n_1 + n_3, and n_2 + n_3, so each sum is at most the clique number. Their maximum is therefore also at most the clique number. Combined with the upper bound via antisymmetry, the clique number equals this maximum.
uses
b4_cliqueNum_card_pairBlock,b4_cliqueNum_isClique_01,b4_cliqueNum_isClique_13,b4_cliqueNum_isClique_23,max_le· have h01 : n 0 + n 1 ≤ (b4_graph n).cliqueNum := by have := (b4_cliqueNum_isClique_01 n).card_le_cliqueNum rwa [b4_cliqueNum_card_pairBlock n 0 1 (by decide)] at this have h13 : n 1 + n 3 ≤ (b4_graph n).cliqueNum := by have := (b4_cliqueNum_isClique_13 n).card_le_cliqueNum rwa [b4_cliqueNum_card_pairBlock n 1 3 (by decide)] at this have h23 : n 2 + n 3 ≤ (b4_graph n).cliqueNum := by have := (b4_cliqueNum_isClique_23 n).card_le_cliqueNum rwa [b4_cliqueNum_card_pairBlock n 2 3 (by decide)] at this exact max_le (max_le h01 h13) h23
b4_cliqueNum_pairBlock- The Finset of all vertices belonging to part a or part b.
card_sigma- The cardinality of a disjoint union of finite sets indexed by a Finset is the sum of their cardinalities.
b4_graph_adj- Two vertices in B_4(n) are adjacent if and only if they are distinct and either belong to the same part or to parts adjacent in the path 0-1-3-2.
b4_cliqueNum_mem_pairBlock_iff- A vertex belongs to the pair block of a and b if and only if its part index is a or b.
b4_cliqueNum_case_0- Any clique containing a vertex from part 0 is a subset of the pair block of parts 0 and 1.
card_le_card- If s ⊆ t for finite sets s and t, then |s| ≤ |t|.
b4_cliqueNum_card_pairBlock- For distinct parts a and b, the pair block of a and b has cardinality n(a) + n(b).
le_trans- Inequality is transitive: if a ≤ b and b ≤ c, then a ≤ c.
le_max_of_le_left- If a ≤ b, then a ≤ max(b, c).
le_max_left- For any a and b, a ≤ max(a, b).
b4_cliqueNum_case_1- Any clique with no vertices in part 0 that contains a vertex from part 1 is a subset of the pair block of parts 1 and 3.
le_max_right- For any a and b, b ≤ max(a, b).
b4_cliqueNum_case_23- Any clique with no vertices in parts 0 or 1 is a subset of the pair block of parts 2 and 3.
le_antisymm- If a ≤ b and b ≤ a, then a = b.
isNClique_iff- A set is an n-clique if and only if it is a clique and its cardinality is n.
b4_cliqueNum_card_le_of_isClique- Any clique in B_4(n) has cardinality at most max(max(n_0 + n_1, n_1 + n_3), n_2 + n_3).
b4_cliqueNum_isClique_01- The pair block of parts 0 and 1 forms a clique in B_4(n).
b4_cliqueNum_isClique_13- The pair block of parts 1 and 3 forms a clique in B_4(n).
b4_cliqueNum_isClique_23- The pair block of parts 2 and 3 forms a clique in B_4(n).
max_le- If a ≤ c and b ≤ c, then max(a, b) ≤ c.
- The step establishing that vertices outside parts 0 and 1 must belong to parts 2 and 3 is automated using `omega`.
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.
open SimpleGraph Finsetdef b4_cliqueNum_pairBlock (n : Fin 4 → ℕ) (a b : Fin 4) : Finset (Σ i : Fin 4, Fin (n i)) := ({a, b} : Finset (Fin 4)).sigma (fun _ => univ)lemma b4_cliqueNum_card_pairBlock (n : Fin 4 → ℕ) (a b : Fin 4) (hab : a ≠ b) : (b4_cliqueNum_pairBlock n a b).card = n a + n b := by rw [b4_cliqueNum_pairBlock, card_sigma] simp [hab]lemma b4_cliqueNum_mem_pairBlock_iff (n : Fin 4 → ℕ) (a b : Fin 4) (x : Σ i : Fin 4, Fin (n i)) : x ∈ b4_cliqueNum_pairBlock n a b ↔ x.1 = a ∨ x.1 = b := by simp [b4_cliqueNum_pairBlock]lemma b4_cliqueNum_isClique_01 (n : Fin 4 → ℕ) : (b4_graph n).IsClique (b4_cliqueNum_pairBlock n 0 1 : Set (Σ i : Fin 4, Fin (n i))) := by intro x hx y hy hne simp only [b4_cliqueNum_pairBlock, mem_coe, mem_sigma, mem_insert, mem_singleton, mem_univ, and_true] at hx hy rw [b4_graph_adj] refine ⟨hne, ?_⟩ rcases hx with hx | hx <;> rcases hy with hy | hy · left; rw [hx, hy] · right; left; exact ⟨hx, hy⟩ · right; right; left; exact ⟨hx, hy⟩ · left; rw [hx, hy]lemma b4_cliqueNum_isClique_13 (n : Fin 4 → ℕ) : (b4_graph n).IsClique (b4_cliqueNum_pairBlock n 1 3 : Set (Σ i : Fin 4, Fin (n i))) := by intro x hx y hy hne simp only [b4_cliqueNum_pairBlock, mem_coe, mem_sigma, mem_insert, mem_singleton, mem_univ, and_true] at hx hy rw [b4_graph_adj] refine ⟨hne, ?_⟩ rcases hx with hx | hx <;> rcases hy with hy | hy · left; rw [hx, hy] · right; right; right; left; exact ⟨hx, hy⟩ · right; right; right; right; left; exact ⟨hx, hy⟩ · left; rw [hx, hy]lemma b4_cliqueNum_isClique_23 (n : Fin 4 → ℕ) : (b4_graph n).IsClique (b4_cliqueNum_pairBlock n 2 3 : Set (Σ i : Fin 4, Fin (n i))) := by intro x hx y hy hne simp only [b4_cliqueNum_pairBlock, mem_coe, mem_sigma, mem_insert, mem_singleton, mem_univ, and_true] at hx hy rw [b4_graph_adj] refine ⟨hne, ?_⟩ rcases hx with hx | hx <;> rcases hy with hy | hy · left; rw [hx, hy] · right; right; right; right; right; left; exact ⟨hx, hy⟩ · right; right; right; right; right; right; exact ⟨hx, hy⟩ · left; rw [hx, hy]lemma b4_cliqueNum_case_0 (n : Fin 4 → ℕ) (s : Finset (Σ i : Fin 4, Fin (n i))) (hc : (b4_graph n).IsClique (s : Set (Σ i : Fin 4, Fin (n i)))) (x : Σ i : Fin 4, Fin (n i)) (hx : x ∈ s) (hx0 : x.1 = 0) : s ⊆ b4_cliqueNum_pairBlock n 0 1 := by intro y hy rw [b4_cliqueNum_mem_pairBlock_iff] by_cases hy0 : y.1 = 0 · left; exact hy0 · right have hne : x ≠ y := by intro h; subst h; exact hy0 hx0 have hadj := hc hx hy hne rw [b4_graph_adj] at hadj rcases hadj.2 with h | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ · rw [hx0] at h; exact (hy0 h.symm).elim · exact h2 · rw [hx0] at h1; contradiction · rw [hx0] at h1; contradiction · rw [hx0] at h1; contradiction · rw [hx0] at h1; contradiction · rw [hx0] at h1; contradictionlemma b4_cliqueNum_case_1 (n : Fin 4 → ℕ) (s : Finset (Σ i : Fin 4, Fin (n i))) (hc : (b4_graph n).IsClique (s : Set (Σ i : Fin 4, Fin (n i)))) (h_no_0 : ∀ z ∈ s, z.1 ≠ 0) (x : Σ i : Fin 4, Fin (n i)) (hx : x ∈ s) (hx1 : x.1 = 1) : s ⊆ b4_cliqueNum_pairBlock n 1 3 := by intro y hy rw [b4_cliqueNum_mem_pairBlock_iff] by_cases hy1 : y.1 = 1 · left; exact hy1 · right have hne : x ≠ y := by intro h; subst h; exact hy1 hx1 have hadj := hc hx hy hne rw [b4_graph_adj] at hadj have hy0 : y.1 ≠ 0 := h_no_0 y hy rcases hadj.2 with h | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ | ⟨h1, h2⟩ · rw [hx1] at h; exact (hy1 h.symm).elim · rw [hx1] at h1; contradiction · rw [h2] at hy0; contradiction · exact h2 · rw [hx1] at h1; contradiction · rw [hx1] at h1; contradiction · rw [hx1] at h1; contradictionlemma b4_cliqueNum_case_23 (n : Fin 4 → ℕ) (s : Finset (Σ i : Fin 4, Fin (n i))) (h_no_0 : ∀ z ∈ s, z.1 ≠ 0) (h_no_1 : ∀ z ∈ s, z.1 ≠ 1) : s ⊆ b4_cliqueNum_pairBlock n 2 3 := by intro y hy rw [b4_cliqueNum_mem_pairBlock_iff] have hy0 := h_no_0 y hy have hy1 := h_no_1 y hy omegalemma b4_cliqueNum_card_le_of_isClique (n : Fin 4 → ℕ) (s : Finset (Σ i : Fin 4, Fin (n i))) (hc : (b4_graph n).IsClique (s : Set (Σ i : Fin 4, Fin (n i)))) : s.card ≤ max (max (n 0 + n 1) (n 1 + n 3)) (n 2 + n 3) := by by_cases h0 : ∃ x ∈ s, (x : Σ i : Fin 4, Fin (n i)).1 = 0 · rcases h0 with ⟨x, hx, hx0⟩ have hsub := b4_cliqueNum_case_0 n s hc x hx hx0 have hle := card_le_card hsub rw [b4_cliqueNum_card_pairBlock n 0 1 (by decide)] at hle exact le_trans hle (le_max_of_le_left (le_max_left _ _)) · push Not at h0 by_cases h1 : ∃ x ∈ s, (x : Σ i : Fin 4, Fin (n i)).1 = 1 · rcases h1 with ⟨x, hx, hx1⟩ have hsub := b4_cliqueNum_case_1 n s hc h0 x hx hx1 have hle := card_le_card hsub rw [b4_cliqueNum_card_pairBlock n 1 3 (by decide)] at hle exact le_trans hle (le_max_of_le_left (le_max_right _ _)) · push Not at h1 have hsub := b4_cliqueNum_case_23 n s h0 h1 have hle := card_le_card hsub rw [b4_cliqueNum_card_pairBlock n 2 3 (by decide)] at hle exact le_trans hle (le_max_right _ _)/-- The clique number of B_4(n_0, n_1, n_2, n_3) is max(max(n_0 + n_1, n_1 + n_3), n_2 + n_3). -/theorem b4_cliqueNum (n : Fin 4 → ℕ) : (b4_graph n).cliqueNum = max (max (n 0 + n 1) (n 1 + n 3)) (n 2 + n 3) := by apply le_antisymm · obtain ⟨s, hs⟩ := (b4_graph n).exists_isNClique_cliqueNum rw [isNClique_iff] at hs rw [← hs.2] exact b4_cliqueNum_card_le_of_isClique n s hs.1 · have h01 : n 0 + n 1 ≤ (b4_graph n).cliqueNum := by have := (b4_cliqueNum_isClique_01 n).card_le_cliqueNum rwa [b4_cliqueNum_card_pairBlock n 0 1 (by decide)] at this have h13 : n 1 + n 3 ≤ (b4_graph n).cliqueNum := by have := (b4_cliqueNum_isClique_13 n).card_le_cliqueNum rwa [b4_cliqueNum_card_pairBlock n 1 3 (by decide)] at this have h23 : n 2 + n 3 ≤ (b4_graph n).cliqueNum := by have := (b4_cliqueNum_isClique_23 n).card_le_cliqueNum rwa [b4_cliqueNum_card_pairBlock n 2 3 (by decide)] at this exact max_le (max_le h01 h13) h23