b3_graph
def
The 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 the same block or one of them lies in block 2 (the middle vertex of the path P_3).
Statement
def b3_graph (n : Fin 3 → ℕ) : SimpleGraph (Σ i : Fin 3, Fin (n i))- Defined in
- arXiv:2610.21388 (Stronger spectral bound for clique number), Sec. 2, definition of B_t(n_1,...,n_t) for t = 3, with G_3 = P_3 (the base graph whose quotient matrix M appears in Theorem 2.3 for s = 1); blocks indexed 0, 1, 2 with 2 the middle vertex
- Verified
- 18 Oct 2026
- Axioms
- none listed
- Used by 5
- 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.
- b3_cliqueNumThe clique number of B_3(n_0, n_1, n_2) is max(n_0 + n_2, n_1 + n_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…
- b3_adjMatrix_trace_sqFor B_3(n_0,n_1,n_2) with adjacency matrix A: tr(A^2) = tr(M^2) + (n - 3). Since tr(A^2) is the sum of the squares of all adjacency…
Lean source view module on GitHub
/-- `B₃(n₀, n₁, n₂)`: the generalized lexicographic product of the path `P₃` (middle vertex `2`) with the cliques `K_{n₀}, K_{n₁}, K_{n₂}`: each vertex `i` of `P₃` is replaced by a clique on `n i` vertices, and two vertices in different cliques are adjacent when one of them lies in the clique of the middle vertex. -/ def b3_graph (n : Fin 3 → ℕ) : SimpleGraph (Σ i : Fin 3, Fin (n i)) := { Adj := fun x y => x ≠ y ∧ (x.1 = y.1 ∨ x.1 = 2 ∨ y.1 = 2), symm := ⟨fun x y h => ⟨h.1.symm, by rcases h.2 with h | h | h <;> simp [h]⟩⟩, loopless := ⟨fun x h => h.1 rfl⟩ }