AFTD Auto-Formalizing Theoretical Domains

b4_graph

def

The 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 and 1, blocks 1 and 3, and blocks 2 and 3.

Statement

def b4_graph (n : Fin 4 → ℕ) : SimpleGraph (Σ i : Fin 4, Fin (n i))
Defined in
arXiv:2610.21388, Section 2
Verified
22 Oct 2026
Axioms
none listed
Used by 4
  • b4_cliqueNumThe 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).
  • 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_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…
  • 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

b4_graph n defines a simple graph on the vertex type Σ i : Fin 4, Fin (n i) (where n : Fin 4 → ℕ). Two vertices x and y are adjacent if and only if x ≠ y and either: 1. x.1 = y.1 (distinct vertices with the same first component are adjacent, so each part i induces a complete subgraph / clique), or 2. {x.1, y.1} = {0, 1}, or 3. {x.1, y.1} = {1, 3}, or 4. {x.1, y.1} = {2, 3}. In other words, it is a graph composed of four cliques of sizes n 0, n 1, n 2, n 3, with all possible edges present between part 0 and part 1, between part 1 and part 3, and between part 2 and part 3 (a path-like arrangement of complete bipartite connections between parts: 0 — 1 — 3 — 2).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- The graph B_4(n_0, n_1, n_2, n_3) of arXiv:2610.21388: generalized lexicographic product of G_4 = P_4 with complete graphs of sizes n_i. -/
def b4_graph (n : Fin 4 → ℕ) : SimpleGraph (Σ i : Fin 4, Fin (n i)) :=
  { Adj := fun x y => x ≠ y ∧ (x.1 = y.1 ∨ (x.1 = 0 ∧ y.1 = 1) ∨ (x.1 = 1 ∧ y.1 = 0) ∨
      (x.1 = 1 ∧ y.1 = 3) ∨ (x.1 = 3 ∧ y.1 = 1) ∨ (x.1 = 2 ∧ y.1 = 3) ∨ (x.1 = 3 ∧ y.1 = 2)),
    symm := ⟨fun x y h => ⟨h.1.symm, by
      rcases h.2 with h | ⟨h0, h1⟩ | ⟨h1, h0⟩ | ⟨h1, h3⟩ | ⟨h3, h1⟩ | ⟨h2, h3⟩ | ⟨h3, h2⟩
      · exact Or.inl h.symm
      · exact Or.inr (Or.inr (Or.inl ⟨h1, h0⟩))
      · exact Or.inr (Or.inl ⟨h0, h1⟩)
      · exact Or.inr (Or.inr (Or.inr (Or.inr (Or.inl ⟨h3, h1⟩))))
      · exact Or.inr (Or.inr (Or.inr (Or.inl ⟨h1, h3⟩)))
      · exact Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr ⟨h3, h2⟩)))))
      · exact Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inl ⟨h2, h3⟩)))))⟩⟩,
    loopless := ⟨fun x h => h.1 rfl⟩ }
See it in the graphDiscuss this resultChallenge it