b5_graph
def
The 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 vertices of G_5 are completely joined.
Statement
def b5_graph (n : Fin 5 → ℕ) : SimpleGraph (Σ i : Fin 5, Fin (n i))- Defined in
- arXiv:2610.21388 (Stronger spectral bound for clique number), Sec. 2, definition of B_t for t = 5
- Verified
- 18 Oct 2026
- Axioms
- none listed
- Built on 2
- 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.
- g5_adj_symmSanity lemma: the adjacency of G_5 is symmetric.
- Used by 3
- b5_graph_adjSanity lemma: adjacency in B_5 unfolds to: distinct, and the same block or adjacent blocks of G_5.
- 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…
- b5_cliqueNumω(B_5(n_0..n_4)) = n_4 + max(n_0 + n_1, n_1 + n_3, n_2 + n_3).
Lean source view module on GitHub
/-- `B₅(n₀, …, n₄)`: the generalized lexicographic product of `G₅` with cliques `K_{n₀}, …, K_{n₄}`: two distinct vertices are adjacent iff they lie in the same block or their blocks are adjacent in `G₅`. -/ def b5_graph (n : Fin 5 → ℕ) : SimpleGraph (Σ i : Fin 5, Fin (n i)) := { Adj := fun x y => x ≠ y ∧ (x.1 = y.1 ∨ g5_adj x.1 y.1), symm := ⟨fun _ _ h => ⟨h.1.symm, h.2.imp Eq.symm (g5_adj_symm _ _)⟩⟩, loopless := ⟨fun _ h => h.1 rfl⟩ }