AFTD Auto-Formalizing Theoretical Domains

b3_cliqueNum

theoremverified

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

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).

  1. 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).

    lines 4–5

    uses Finset.card_sigma, Finset.sum_pair

      rw [Finset.card_sigma, Finset.sum_pair hi]
      simp
  2. 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.

    lines 11–16

    uses Finset.coe_sigma, Set.mem_sigma_iff, Finset.mem_coe, Finset.mem_insert, Finset.mem_singleton, b3_graph_adj

      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']
  3. 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.

    lines 20–23

    uses le_antisymm

      apply le_antisymm
      · obtain ⟨s, hs⟩ := (b3_graph n).exists_isNClique_cliqueNum
        rw [← hs.card_eq]
        by_cases h0 : ∃ x ∈ s, x.1 = 0
  4. 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.

    lines 25–38

    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_left

          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 _ _
  5. 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.

    lines 39–48

    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 _ _
  6. 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.

    lines 49–53

    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).

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

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
See it in the graphDiscuss this resultChallenge it