AFTD Auto-Formalizing Theoretical Domains

bibd_isomorphic_of_block_clique_graph_iso

theoremverifiedoriginal

OP-1148: if two BIBDs D₁, D₂ with the same parameters (v, b, r, k, λ) on finite block sets have isomorphic modified block-clique graphs (bibd_block_clique_graph), then the designs are isomorphic (bibd_isomorphic), for every block size k.

Statement

theorem bibd_isomorphic_of_block_clique_graph_iso {X₁ B₁ X₂ B₂ : Type*} [Finite B₁] [Finite B₂]
    {v b r k lam : ℕ} (D₁ : BIBD X₁ B₁ v b r k lam) (D₂ : BIBD X₂ B₂ v b r k lam)
    (h : Nonempty (bibd_block_clique_graph D₁ ≃g bibd_block_clique_graph D₂)) :
    bibd_isomorphic D₁ D₂
Related work
arXiv:2611.05762, Conjecture 6.30.1 (Sec. 6.30, Algebraic Recoverability), for the construction of Sec. 6.9. Stated for every block size k; finiteness of the block sets is added because Nat.card gives no information on infinite types.
Verified
09 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • bibd_isomorphic_of_block_clique_graph_iso_of_three_leRecoverability of a BIBD from its modified block-clique graph when the block size k is at least 3: if two BIBDs D₁, D₂ with the same…
  • bibd_block_clique_graphThe modified block-clique graph K_v^*(D) of a balanced incomplete block design D with parameters (v, b, r, k, λ) is the simple graph on…
  • bibd_isomorphicTwo balanced incomplete block designs D₁ and D₂ with parameters (v, b, r, k, λ) are isomorphic if there exist a bijection f between their…
  • BIBDA structure BIBD parameterized by types X and B and natural numbers v, b, r, k, lam, with fields: card_points asserting Nat.card X = v;…
  • g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.

Read back from the Lean

Let $X_1, B_1, X_2, B_2$ be types with $B_1$ and $B_2$ finite, and let $v, b, r, k, \lambda$ be natural numbers. Let $D_1$ and $D_2$ be balanced incomplete block designs (BIBDs) on point sets $X_1, X_2$ and block sets $B_1, B_2$, respectively, both having parameters $(v, b, r, k, \lambda)$. If there exists a graph isomorphism between the block-clique graph of $D_1$ and the block-clique graph of $D_2$, then $D_1$ and $D_2$ are isomorphic as block designs.

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 theorem is established by case analysis on the block size k. For k ≥ 3, design isomorphism follows from graph isomorphism by the reconstruction theorem for block-clique graphs (bibd_isomorphic_of_block_clique_graph_iso_of_three_le). For small block sizes k ∈ {0, 1, 2}, the design is completely characterized up to isomorphism by its parameters alone without using the graph isomorphism: for k = 0 block incidence is vacuously false, for k = 1 blocks are singletons with point fibers of uniform size r, and for k = 2 blocks are pairs with pair fibers of uniform size λ, allowing explicit construction of the block bijection by fiber decomposition.

  1. The point sets and block sets of the two designs are finite with equal cardinalities, providing bijections between points and between blocks.

    Since k = 0 < v by the incomplete design axiom, the number of points v is non-zero. By Nat.finite_of_card_ne_zero, both point sets are finite. Because the designs share parameters v and b, Finite.card_eq.mp yields bijections f between the point sets and g between the block sets.

    lines 6–14

    uses Nat.finite_of_card_ne_zero, Finite.card_eq.mp

      have hv : v ≠ 0 := by
        have := D₁.incomplete
        omega
      have fx1 : Finite X₁ := Nat.finite_of_card_ne_zero (by rw [D₁.card_points]; exact hv)
      have fx2 : Finite X₂ := Nat.finite_of_card_ne_zero (by rw [D₂.card_points]; exact hv)
      have hX : Nonempty (X₁ ≃ X₂) := Finite.card_eq.mp (by rw [D₁.card_points, D₂.card_points])
      have hB : Nonempty (B₁ ≃ B₂) := Finite.card_eq.mp (by rw [D₁.card_blocks, D₂.card_blocks])
      rcases hX with ⟨f⟩
      rcases hB with ⟨g⟩
  2. The chosen bijections f and g form an isomorphism between the designs for k = 0.

    For block size 0, the incidence condition between blocks and points asserts the existence of an index in Fin 0, which is vacuously false on both sides using Fin.elim0.

    lines 15–18

    uses Fin.elim0

      refine ⟨f, g, fun b₁ x => ?_⟩
      constructor
      · rintro ⟨j, _⟩; exact Fin.elim0 j
      · rintro ⟨j', _⟩; exact Fin.elim0 j'
  3. The point sets are finite and there is a bijection f between them for k = 1.

    Since 1 = k < v, v is positive. Therefore both point sets have non-zero cardinality and are finite by Nat.finite_of_card_ne_zero. Since both have v points, Finite.card_eq.mp yields a bijection f between them.

    lines 23–29

    uses Nat.finite_of_card_ne_zero, Finite.card_eq.mp

      have hv : v ≠ 0 := by
        have := D₁.incomplete
        omega
      have fx1 : Finite X₁ := Nat.finite_of_card_ne_zero (by rw [D₁.card_points]; exact hv)
      have fx2 : Finite X₂ := Nat.finite_of_card_ne_zero (by rw [D₂.card_points]; exact hv)
      have hX : Nonempty (X₁ ≃ X₂) := Finite.card_eq.mp (by rw [D₁.card_points, D₂.card_points])
      rcases hX with ⟨f⟩
  4. For each point, the fibers of blocks containing that point have cardinality r in both designs, giving fiberwise bijections.

    When k = 1, the unique block index is j0 = 0 (since any index equals j0 by Subsingleton.elim). Through Equiv.subtypeEquivRight and Nat.card_congr, the fiber of blocks mapping to a given point is equivalent to the replication set, which has cardinality r by the design replication axiom. Since every fiber has size r, Finite.card_eq.mp provides a bijection between the fiber over x in D₁ and the fiber over f(x) in D₂.

    lines 30–61

    uses Nat.zero_lt_one, Equiv.subtypeEquivRight, Subsingleton.elim, Nat.card_congr, Finite.card_eq.mp

      let j0 : Fin 1 := ⟨0, Nat.zero_lt_one⟩
      let pt₁ : B₁ → X₁ := fun β => D₁.block_pts β j0
      let pt₂ : B₂ → X₂ := fun β => D₂.block_pts β j0
      have h_fib₁ : ∀ x : X₁, Nat.card { β : B₁ // pt₁ β = x } = r := by
        intro x
        have hr := D₁.replication x
        have heq : { β : B₁ // pt₁ β = x } ≃ { β : B₁ // ∃ j, D₁.block_pts β j = x } :=
          Equiv.subtypeEquivRight (fun β => by
            constructor
            · intro h; exact ⟨j0, h⟩
            · rintro ⟨j, hj⟩
              have : j = j0 := Subsingleton.elim j j0
              subst this
              exact hj)
        rw [Nat.card_congr heq]
        exact hr
      have h_fib₂ : ∀ y : X₂, Nat.card { β : B₂ // pt₂ β = y } = r := by
        intro y
        have hr := D₂.replication y
        have heq : { β : B₂ // pt₂ β = y } ≃ { β : B₂ // ∃ j, D₂.block_pts β j = y } :=
          Equiv.subtypeEquivRight (fun β => by
            constructor
            · intro h; exact ⟨j0, h⟩
            · rintro ⟨j, hj⟩
              have : j = j0 := Subsingleton.elim j j0
              subst this
              exact hj)
        rw [Nat.card_congr heq]
        exact hr
      have h_fib_iso : ∀ x : X₁, Nonempty ({ β : B₁ // pt₁ β = x } ≃ { β : B₂ // pt₂ β = f x }) := by
        intro x
        exact Finite.card_eq.mp (by rw [h_fib₁, h_fib₂])
  5. Gluing the fiber bijections over all points produces a bijection g between the block sets for k = 1.

    Decomposing each block set into a dependent sum of fibers over points gives canonical equivalences e₁ and e₂. Combining the point bijection f with the fiber bijections using Equiv.sigmaCongr yields an equivalence of sigma types, which when composed with e₁ and the inverse of e₂ gives a bijection g between the block sets.

    lines 62–80

    uses Equiv.sigmaCongr

      let e₁ : B₁ ≃ (x : X₁) × { β : B₁ // pt₁ β = x } :=
        { toFun := fun β => ⟨pt₁ β, ⟨β, rfl⟩⟩
          invFun := fun p => p.2.1
          left_inv := fun β => rfl
          right_inv := fun ⟨x, β, hβ⟩ => by
            dsimp
            subst hβ
            rfl }
      let e₂ : B₂ ≃ (y : X₂) × { β : B₂ // pt₂ β = y } :=
        { toFun := fun β => ⟨pt₂ β, ⟨β, rfl⟩⟩
          invFun := fun p => p.2.1
          left_inv := fun β => rfl
          right_inv := fun ⟨y, β, hβ⟩ => by
            dsimp
            subst hβ
            rfl }
      let e_sigma : ((x : X₁) × { β : B₁ // pt₁ β = x }) ≃ ((y : X₂) × { β : B₂ // pt₂ β = y }) :=
        Equiv.sigmaCongr f (fun x => (h_fib_iso x).some)
      let g : B₁ ≃ B₂ := e₁.trans (e_sigma.trans e₂.symm)
  6. The bijections f and g constitute a design isomorphism for k = 1.

    By construction, the point of block g(β) is f applied to the point of block β. Since any index in Fin 1 is j0 by Subsingleton.elim, block incidence reduces to point equality, which is preserved and reflected by f using congr_arg and injectivity of f.

    lines 81–103

    uses Subsingleton.elim, congr_arg

      refine ⟨f, g, fun β x => ?_⟩
      have hg_pt : pt₂ (g β) = f (pt₁ β) := by
        have this1 : (e_sigma (e₁ β)).1 = f (pt₁ β) := rfl
        have he2 : (e₂ (g β)).1 = (e_sigma (e₁ β)).1 := by
          change (e₂ (e₂.symm (e_sigma (e₁ β)))).1 = (e_sigma (e₁ β)).1
          rw [e₂.apply_symm_apply]
        exact he2.trans this1
      constructor
      · rintro ⟨j, hj⟩
        have hj0 : j = j0 := Subsingleton.elim j j0
        subst hj0
        refine ⟨j0, ?_⟩
        change pt₂ (g β) = f x
        rw [hg_pt]
        exact congr_arg f hj
      · rintro ⟨j', hj'⟩
        have hj0 : j' = j0 := Subsingleton.elim j' j0
        subst hj0
        refine ⟨j0, ?_⟩
        change pt₁ β = x
        change pt₂ (g β) = f x at hj'
        rw [hg_pt] at hj'
        exact f.injective hj'
  7. A point belongs to a block of size 2 if and only if it equals the block's point at index 0 or at index 1.

    Since any index in Fin 2 is either 0 or 1 by case exhaustion, the existential quantifier over Fin 2 is logically equivalent to the disjunction of equalities at index 0 and index 1.

    lines 107–121

      let j0 : Fin 2 := ⟨0, by omega⟩
      let j1 : Fin 2 := ⟨1, by omega⟩
      have hj : ∀ j : Fin 2, j = j0 ∨ j = j1 := by
        intro ⟨val, hval⟩
        interval_cases val
        · left; rfl
        · right; rfl
      constructor
      · rintro ⟨j, hjx⟩
        rcases hj j with rfl | rfl
        · left; exact hjx
        · right; exact hjx
      · rintro (h | h)
        · exact ⟨j0, h⟩
        · exact ⟨j1, h⟩
  8. Equality of unordered pairs under a bijection f preserves and reflects membership.

    Unordered pair equality expands via Sym2.eq_iff to matching coordinates in forward or swapped order. Applying injectivity of f via EmbeddingLike.apply_eq_iff_eq and disjunction commutativity or_comm shows that membership in the image pair is equivalent to membership in the source pair.

    lines 126–129

    uses Sym2.eq_iff, EmbeddingLike.apply_eq_iff_eq, or_comm

      simp only [Sym2.eq_iff] at h
      rcases h with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩
      · simp only [EmbeddingLike.apply_eq_iff_eq]
      · simp only [EmbeddingLike.apply_eq_iff_eq, or_comm]
  9. The point sets are finite and admit a bijection f between them for k = 2.

    From 2 = k < v, v is non-zero, making both point sets finite by Nat.finite_of_card_ne_zero. Since both have cardinality v, Finite.card_eq.mp gives a bijection f between them.

    lines 134–140

    uses Nat.finite_of_card_ne_zero, Finite.card_eq.mp

      have hv : v ≠ 0 := by
        have := D₁.incomplete
        omega
      have fx1 : Finite X₁ := Nat.finite_of_card_ne_zero (by rw [D₁.card_points]; exact hv)
      have fx2 : Finite X₂ := Nat.finite_of_card_ne_zero (by rw [D₂.card_points]; exact hv)
      have hX : Nonempty (X₁ ≃ X₂) := Finite.card_eq.mp (by rw [D₁.card_points, D₂.card_points])
      rcases hX with ⟨f⟩
  10. Each block determines an unordered pair of points, and for distinct points x ≠ y, the block's pair equals s(x, y) if and only if both x and y belong to the block.

    Using Sym2.eq_iff, equality of the block pair with s(x, y) is equivalent to the two points matching in either order. Because the block indices are restricted to 0 and 1 and x ≠ y prevents both indices from taking the same value, this is equivalent to both x and y being incident with the block.

    lines 141–175

    uses Sym2.eq_iff

      let j0 : Fin 2 := ⟨0, by omega⟩
      let j1 : Fin 2 := ⟨1, by omega⟩
      let pair₁ : B₁ → Sym2 X₁ := fun β => s(D₁.block_pts β j0, D₁.block_pts β j1)
      let pair₂ : B₂ → Sym2 X₂ := fun β => s(D₂.block_pts β j0, D₂.block_pts β j1)
      have hj : ∀ j : Fin 2, j = j0 ∨ j = j1 := by
        intro ⟨val, hval⟩
        interval_cases val
        · left; rfl
        · right; rfl
      have h_fib_eq₁ : ∀ (β : B₁) (x y : X₁), x ≠ y → (pair₁ β = s(x, y) ↔ (∃ j, D₁.block_pts β j = x) ∧ ∃ j', D₁.block_pts β j' = y) := by
        intro β x y hxy
        simp only [pair₁, Sym2.eq_iff]
        constructor
        · rintro (⟨h0, h1⟩ | ⟨h0, h1⟩)
          · refine ⟨⟨j0, h0⟩, ⟨j1, h1⟩⟩
          · refine ⟨⟨j1, h1⟩, ⟨j0, h0⟩⟩
        · rintro ⟨⟨j, hjx⟩, ⟨j', hj'y⟩⟩
          rcases hj j with rfl | rfl <;> rcases hj j' with rfl | rfl
          · subst hjx hj'y; exact (hxy rfl).elim
          · left; exact ⟨hjx, hj'y⟩
          · right; exact ⟨hj'y, hjx⟩
          · subst hjx hj'y; exact (hxy rfl).elim
      have h_fib_eq₂ : ∀ (β : B₂) (x y : X₂), x ≠ y → (pair₂ β = s(x, y) ↔ (∃ j, D₂.block_pts β j = x) ∧ ∃ j', D₂.block_pts β j' = y) := by
        intro β x y hxy
        simp only [pair₂, Sym2.eq_iff]
        constructor
        · rintro (⟨h0, h1⟩ | ⟨h0, h1⟩)
          · refine ⟨⟨j0, h0⟩, ⟨j1, h1⟩⟩
          · refine ⟨⟨j1, h1⟩, ⟨j0, h0⟩⟩
        · rintro ⟨⟨j, hjx⟩, ⟨j', hj'y⟩⟩
          rcases hj j with rfl | rfl <;> rcases hj j' with rfl | rfl
          · subst hjx hj'y; exact (hxy rfl).elim
          · left; exact ⟨hjx, hj'y⟩
          · right; exact ⟨hj'y, hjx⟩
          · subst hjx hj'y; exact (hxy rfl).elim
  11. Block pairs are never diagonal, and each off-diagonal pair appears in exactly λ blocks.

    Because the points of any block are distinct by injectivity of block_pts, Sym2.mk_isDiag_iff shows no block pair is diagonal. For any off-diagonal pair s(x, y) (analyzed using Sym2.ind and Sym2.mk_isDiag_iff), the fiber of blocks having this pair is equivalent via Equiv.subtypeEquivRight to the set of blocks containing both x and y, which has cardinality λ by Nat.card_congr and the design balance axiom.

    lines 176–205

    uses Sym2.mk_isDiag_iff, Sym2.ind, Equiv.subtypeEquivRight, Nat.card_congr

      have pair_not_diag₁ : ∀ β : B₁, ¬ (pair₁ β).IsDiag := by
        intro β
        rw [Sym2.mk_isDiag_iff]
        intro h
        have := D₁.block_inj β h
        revert this
        decide
      have pair_not_diag₂ : ∀ β : B₂, ¬ (pair₂ β).IsDiag := by
        intro β
        rw [Sym2.mk_isDiag_iff]
        intro h
        have := D₂.block_inj β h
        revert this
        decide
      have card_fib₁ : ∀ (p : Sym2 X₁), ¬ p.IsDiag → Nat.card { β : B₁ // pair₁ β = p } = lam := by
        intro p hp
        induction' p using Sym2.ind with x y
        rw [Sym2.mk_isDiag_iff] at hp
        have heq : { β : B₁ // pair₁ β = s(x, y) } ≃ { β : B₁ // (∃ j, D₁.block_pts β j = x) ∧ ∃ j', D₁.block_pts β j' = y } :=
          Equiv.subtypeEquivRight (fun β => h_fib_eq₁ β x y hp)
        rw [Nat.card_congr heq]
        exact D₁.balance hp
      have card_fib₂ : ∀ (p : Sym2 X₂), ¬ p.IsDiag → Nat.card { β : B₂ // pair₂ β = p } = lam := by
        intro p hp
        induction' p using Sym2.ind with x y
        rw [Sym2.mk_isDiag_iff] at hp
        have heq : { β : B₂ // pair₂ β = s(x, y) } ≃ { β : B₂ // (∃ j, D₂.block_pts β j = x) ∧ ∃ j', D₂.block_pts β j' = y } :=
          Equiv.subtypeEquivRight (fun β => h_fib_eq₂ β x y hp)
        rw [Nat.card_congr heq]
        exact D₂.balance hp
  12. The point bijection f induces an equivalence on non-diagonal unordered pairs, and corresponding fibers are isomorphic.

    The bijection f maps unordered pairs via Sym2.map, preserving non-diagonality by Sym2.ind and Sym2.mk_isDiag_iff, which yields an equivalence pair_equiv on non-diagonal pairs using Subtype.ext. Since every non-diagonal pair has fiber size λ in both designs, Finite.card_eq.mp provides a bijection between the fibers over corresponding pairs.

    lines 206–229

    uses Sym2.map, Sym2.ind, Sym2.mk_isDiag_iff, Subtype.ext, Finite.card_eq.mp

      let sym2_f : Sym2 X₁ ≃ Sym2 X₂ :=
        { toFun := Sym2.map f
          invFun := Sym2.map f.symm
          left_inv := fun p => by induction' p using Sym2.ind with x y; simp
          right_inv := fun p => by induction' p using Sym2.ind with x y; simp }
      have sym2_f_isDiag : ∀ p : Sym2 X₁, (sym2_f p).IsDiag ↔ p.IsDiag := by
        intro p
        induction' p using Sym2.ind with x y
        simp [sym2_f, Sym2.mk_isDiag_iff]
      have sym2_f_symm_isDiag : ∀ p : Sym2 X₂, (sym2_f.symm p).IsDiag ↔ p.IsDiag := by
        intro p
        have := sym2_f_isDiag (sym2_f.symm p)
        rw [sym2_f.apply_symm_apply] at this
        exact this.symm
      let pair_equiv : { p : Sym2 X₁ // ¬ p.IsDiag } ≃ { p : Sym2 X₂ // ¬ p.IsDiag } :=
        { toFun := fun ⟨p, hp⟩ => ⟨sym2_f p, by rwa [sym2_f_isDiag]⟩
          invFun := fun ⟨p, hp⟩ => ⟨sym2_f.symm p, by rwa [sym2_f_symm_isDiag]⟩
          left_inv := fun ⟨p, hp⟩ => Subtype.ext (sym2_f.symm_apply_apply p)
          right_inv := fun ⟨p, hp⟩ => Subtype.ext (sym2_f.apply_symm_apply p) }
      have fib_iso : ∀ P : { p : Sym2 X₁ // ¬ p.IsDiag },
          Nonempty ({ β : B₁ // pair₁ β = P.1 } ≃ { β : B₂ // pair₂ β = (pair_equiv P).1 }) := by
        intro P
        apply Finite.card_eq.mp
        rw [card_fib₁ P.1 P.2, card_fib₂ (pair_equiv P).1 (pair_equiv P).2]
  13. Gluing the fiber bijections over all non-diagonal pairs gives a bijection g between the block sets for k = 2.

    Decomposing each block set into a dependent sum over non-diagonal pairs yields equivalences e₁ and e₂. Combining the pair equivalence with the fiberwise isomorphisms using Equiv.sigmaCongr gives an equivalence of sigma types, which with e₁ and the inverse of e₂ yields a bijection g between block sets.

    lines 230–249

    uses Equiv.sigmaCongr

      let e₁ : B₁ ≃ (P : { p : Sym2 X₁ // ¬ p.IsDiag }) × { β : B₁ // pair₁ β = P.1 } :=
        { toFun := fun β => ⟨⟨pair₁ β, pair_not_diag₁ β⟩, ⟨β, rfl⟩⟩
          invFun := fun p => p.2.1
          left_inv := fun β => rfl
          right_inv := fun ⟨⟨p, hp⟩, ⟨β, hβ⟩⟩ => by
            dsimp at hβ
            subst hβ
            rfl }
      let e₂ : B₂ ≃ (P : { p : Sym2 X₂ // ¬ p.IsDiag }) × { β : B₂ // pair₂ β = P.1 } :=
        { toFun := fun β => ⟨⟨pair₂ β, pair_not_diag₂ β⟩, ⟨β, rfl⟩⟩
          invFun := fun p => p.2.1
          left_inv := fun β => rfl
          right_inv := fun ⟨⟨p, hp⟩, ⟨β, hβ⟩⟩ => by
            dsimp at hβ
            subst hβ
            rfl }
      let e_sigma : ((P : { p : Sym2 X₁ // ¬ p.IsDiag }) × { β : B₁ // pair₁ β = P.1 }) ≃
          ((P : { p : Sym2 X₂ // ¬ p.IsDiag }) × { β : B₂ // pair₂ β = P.1 }) :=
        Equiv.sigmaCongr pair_equiv (fun P => (fib_iso P).some)
      let g : B₁ ≃ B₂ := e₁.trans (e_sigma.trans e₂.symm)
  14. The bijections f and g form a design isomorphism for k = 2.

    The construction of g ensures that the pair of block g(β) is the image under f of the pair of block β using congr_arg and Subtype.val. Applying bibd_fin2_exists_iff reduces block incidence to membership in the 2-element set, which transfers across f by bibd_sym2_mem_iff_f.

    lines 250–263

    uses congr_arg, Subtype.val, bibd_fin2_exists_iff, bibd_sym2_mem_iff_f

      have hg_pair : ∀ β : B₁, pair₂ (g β) = sym2_f (pair₁ β) := by
        intro β
        have this1 : (e_sigma (e₁ β)).1 = pair_equiv ⟨pair₁ β, pair_not_diag₁ β⟩ := rfl
        have he2 : (e₂ (g β)).1 = (e_sigma (e₁ β)).1 := by
          change (e₂ (e₂.symm (e_sigma (e₁ β)))).1 = (e_sigma (e₁ β)).1
          rw [e₂.apply_symm_apply]
        have := he2.trans this1
        exact congr_arg Subtype.val this
      refine ⟨f, g, fun β x => ?_⟩
      have hp : pair₂ (g β) = s(f (D₁.block_pts β j0), f (D₁.block_pts β j1)) := by
        rw [hg_pair β]
        rfl
      rw [bibd_fin2_exists_iff, bibd_fin2_exists_iff]
      exact (bibd_sym2_mem_iff_f f (D₁.block_pts β j0) (D₁.block_pts β j1) x (D₂.block_pts (g β) j0) (D₂.block_pts (g β) j1) hp).symm
  15. If two designs have isomorphic block-clique graphs, they are isomorphic as designs for every block size k.

    We split into cases on the block size k. When k is 0, 1, or 2, the designs are isomorphic by bibd_isomorphic_of_k_zero, bibd_isomorphic_of_k_one, and bibd_isomorphic_of_k_two respectively, whose proofs do not need the graph isomorphism. When k ≥ 3, the result follows from bibd_isomorphic_of_block_clique_graph_iso_of_three_le using the assumed graph isomorphism.

    lines 269–273

    uses bibd_isomorphic_of_k_zero, bibd_isomorphic_of_k_one, bibd_isomorphic_of_k_two, bibd_isomorphic_of_block_clique_graph_iso_of_three_le

      rcases k with _ | _ | _ | k
      · exact bibd_isomorphic_of_k_zero D₁ D₂
      · exact bibd_isomorphic_of_k_one D₁ D₂
      · exact bibd_isomorphic_of_k_two D₁ D₂
      · exact bibd_isomorphic_of_block_clique_graph_iso_of_three_le D₁ D₂ (by omega) h
Nat.finite_of_card_ne_zero
A type with non-zero cardinality is finite.
Finite.card_eq.mp
Two finite types with equal cardinality admit a bijection between them.
Fin.elim0
An element of the empty type Fin 0 produces a value in any type by vacuous elimination.
Nat.zero_lt_one
Zero is strictly less than one.
Equiv.subtypeEquivRight
Subtypes defined by logically equivalent predicates on the same domain are naturally equivalent.
Subsingleton.elim
Any two terms of a subsingleton type are equal.
Nat.card_congr
Equivalent types have the same cardinality.
Equiv.sigmaCongr
An equivalence between index types together with fiberwise equivalences yields an equivalence of sigma types.
congr_arg
Equal arguments applied to a function yield equal results.
Sym2.eq_iff
Two unordered pairs are equal if and only if their elements match in the same or opposite order.
EmbeddingLike.apply_eq_iff_eq
Applying an injective map preserves and reflects equality.
or_comm
Disjunction is commutative.
Sym2.mk_isDiag_iff
An unordered pair lies on the diagonal if and only if its two coordinates are equal.
Sym2.ind
Any property of unordered pairs holds if it holds for all canonical representatives s(x, y).
Sym2.map
Functorial action mapping a function over an unordered pair.
Subtype.ext
Two subtype elements are equal if their underlying values are equal.
Subtype.val
The projection that extracts the underlying value from a subtype.
bibd_fin2_exists_iff
An element lies in the range of a function on Fin 2 if and only if it equals the value at index 0 or index 1.
bibd_sym2_mem_iff_f
Given equality of unordered pairs under a bijection f, membership in the target pair corresponds to membership in the source pair.
bibd_isomorphic_of_k_zero
Any two balanced incomplete block designs with block size 0 on finite block sets and matching parameters are isomorphic.
bibd_isomorphic_of_k_one
Any two balanced incomplete block designs with block size 1 on finite block sets and matching parameters are isomorphic.
bibd_isomorphic_of_k_two
Any two balanced incomplete block designs with block size 2 on finite block sets and matching parameters are isomorphic.
bibd_isomorphic_of_block_clique_graph_iso_of_three_le
Two balanced incomplete block designs with block size at least 3 and isomorphic block-clique graphs are isomorphic.

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

open Classicaltheorem bibd_isomorphic_of_k_zero {X₁ B₁ X₂ B₂ : Type*} [Finite B₁] [Finite B₂]    {v b r lam : ℕ} (D₁ : BIBD X₁ B₁ v b r 0 lam) (D₂ : BIBD X₂ B₂ v b r 0 lam) :    bibd_isomorphic D₁ D₂ := by  have hv : v ≠ 0 := by    have := D₁.incomplete    omega  have fx1 : Finite X₁ := Nat.finite_of_card_ne_zero (by rw [D₁.card_points]; exact hv)  have fx2 : Finite X₂ := Nat.finite_of_card_ne_zero (by rw [D₂.card_points]; exact hv)  have hX : Nonempty (X₁ ≃ X₂) := Finite.card_eq.mp (by rw [D₁.card_points, D₂.card_points])  have hB : Nonempty (B₁ ≃ B₂) := Finite.card_eq.mp (by rw [D₁.card_blocks, D₂.card_blocks])  rcases hX with ⟨f⟩  rcases hB with ⟨g⟩  refine ⟨f, g, fun b₁ x => ?_⟩  constructor  · rintro ⟨j, _⟩; exact Fin.elim0 j  · rintro ⟨j', _⟩; exact Fin.elim0 j'theorem bibd_isomorphic_of_k_one {X₁ B₁ X₂ B₂ : Type*} [Finite B₁] [Finite B₂]    {v b r lam : ℕ} (D₁ : BIBD X₁ B₁ v b r 1 lam) (D₂ : BIBD X₂ B₂ v b r 1 lam) :    bibd_isomorphic D₁ D₂ := by  have hv : v ≠ 0 := by    have := D₁.incomplete    omega  have fx1 : Finite X₁ := Nat.finite_of_card_ne_zero (by rw [D₁.card_points]; exact hv)  have fx2 : Finite X₂ := Nat.finite_of_card_ne_zero (by rw [D₂.card_points]; exact hv)  have hX : Nonempty (X₁ ≃ X₂) := Finite.card_eq.mp (by rw [D₁.card_points, D₂.card_points])  rcases hX with ⟨f⟩  let j0 : Fin 1 := ⟨0, Nat.zero_lt_one⟩  let pt₁ : B₁ → X₁ := fun β => D₁.block_pts β j0  let pt₂ : B₂ → X₂ := fun β => D₂.block_pts β j0  have h_fib₁ : ∀ x : X₁, Nat.card { β : B₁ // pt₁ β = x } = r := by    intro x    have hr := D₁.replication x    have heq : { β : B₁ // pt₁ β = x } ≃ { β : B₁ // ∃ j, D₁.block_pts β j = x } :=      Equiv.subtypeEquivRight (fun β => by        constructor        · intro h; exact ⟨j0, h⟩        · rintro ⟨j, hj⟩          have : j = j0 := Subsingleton.elim j j0          subst this          exact hj)    rw [Nat.card_congr heq]    exact hr  have h_fib₂ : ∀ y : X₂, Nat.card { β : B₂ // pt₂ β = y } = r := by    intro y    have hr := D₂.replication y    have heq : { β : B₂ // pt₂ β = y } ≃ { β : B₂ // ∃ j, D₂.block_pts β j = y } :=      Equiv.subtypeEquivRight (fun β => by        constructor        · intro h; exact ⟨j0, h⟩        · rintro ⟨j, hj⟩          have : j = j0 := Subsingleton.elim j j0          subst this          exact hj)    rw [Nat.card_congr heq]    exact hr  have h_fib_iso : ∀ x : X₁, Nonempty ({ β : B₁ // pt₁ β = x } ≃ { β : B₂ // pt₂ β = f x }) := by    intro x    exact Finite.card_eq.mp (by rw [h_fib₁, h_fib₂])  let e₁ : B₁ ≃ (x : X₁) × { β : B₁ // pt₁ β = x } :=    { toFun := fun β => ⟨pt₁ β, ⟨β, rfl⟩⟩      invFun := fun p => p.2.1      left_inv := fun β => rfl      right_inv := fun ⟨x, β, hβ⟩ => by        dsimp        subst hβ        rfl }  let e₂ : B₂ ≃ (y : X₂) × { β : B₂ // pt₂ β = y } :=    { toFun := fun β => ⟨pt₂ β, ⟨β, rfl⟩⟩      invFun := fun p => p.2.1      left_inv := fun β => rfl      right_inv := fun ⟨y, β, hβ⟩ => by        dsimp        subst hβ        rfl }  let e_sigma : ((x : X₁) × { β : B₁ // pt₁ β = x }) ≃ ((y : X₂) × { β : B₂ // pt₂ β = y }) :=    Equiv.sigmaCongr f (fun x => (h_fib_iso x).some)  let g : B₁ ≃ B₂ := e₁.trans (e_sigma.trans e₂.symm)  refine ⟨f, g, fun β x => ?_⟩  have hg_pt : pt₂ (g β) = f (pt₁ β) := by    have this1 : (e_sigma (e₁ β)).1 = f (pt₁ β) := rfl    have he2 : (e₂ (g β)).1 = (e_sigma (e₁ β)).1 := by      change (e₂ (e₂.symm (e_sigma (e₁ β)))).1 = (e_sigma (e₁ β)).1      rw [e₂.apply_symm_apply]    exact he2.trans this1  constructor  · rintro ⟨j, hj⟩    have hj0 : j = j0 := Subsingleton.elim j j0    subst hj0    refine ⟨j0, ?_⟩    change pt₂ (g β) = f x    rw [hg_pt]    exact congr_arg f hj  · rintro ⟨j', hj'⟩    have hj0 : j' = j0 := Subsingleton.elim j' j0    subst hj0    refine ⟨j0, ?_⟩    change pt₁ β = x    change pt₂ (g β) = f x at hj'    rw [hg_pt] at hj'    exact f.injective hj'theorem bibd_fin2_exists_iff {α : Type*} (p : Fin 2 → α) (x : α) :    (∃ j, p j = x) ↔ p ⟨0, by omega⟩ = x ∨ p ⟨1, by omega⟩ = x := by  let j0 : Fin 2 := ⟨0, by omega⟩  let j1 : Fin 2 := ⟨1, by omega⟩  have hj : ∀ j : Fin 2, j = j0 ∨ j = j1 := by    intro ⟨val, hval⟩    interval_cases val    · left; rfl    · right; rfl  constructor  · rintro ⟨j, hjx⟩    rcases hj j with rfl | rfl    · left; exact hjx    · right; exact hjx  · rintro (h | h)    · exact ⟨j0, h⟩    · exact ⟨j1, h⟩theorem bibd_sym2_mem_iff_f {α β : Type*} (f : α ≃ β) (a₁ b₁ x : α) (a₂ b₂ : β)    (h : s(a₂, b₂) = s(f a₁, f b₁)) :    (a₂ = f x ∨ b₂ = f x) ↔ (a₁ = x ∨ b₁ = x) := by  simp only [Sym2.eq_iff] at h  rcases h with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩  · simp only [EmbeddingLike.apply_eq_iff_eq]  · simp only [EmbeddingLike.apply_eq_iff_eq, or_comm]theorem bibd_isomorphic_of_k_two {X₁ B₁ X₂ B₂ : Type*} [Finite B₁] [Finite B₂]    {v b r lam : ℕ} (D₁ : BIBD X₁ B₁ v b r 2 lam) (D₂ : BIBD X₂ B₂ v b r 2 lam) :    bibd_isomorphic D₁ D₂ := by  have hv : v ≠ 0 := by    have := D₁.incomplete    omega  have fx1 : Finite X₁ := Nat.finite_of_card_ne_zero (by rw [D₁.card_points]; exact hv)  have fx2 : Finite X₂ := Nat.finite_of_card_ne_zero (by rw [D₂.card_points]; exact hv)  have hX : Nonempty (X₁ ≃ X₂) := Finite.card_eq.mp (by rw [D₁.card_points, D₂.card_points])  rcases hX with ⟨f⟩  let j0 : Fin 2 := ⟨0, by omega⟩  let j1 : Fin 2 := ⟨1, by omega⟩  let pair₁ : B₁ → Sym2 X₁ := fun β => s(D₁.block_pts β j0, D₁.block_pts β j1)  let pair₂ : B₂ → Sym2 X₂ := fun β => s(D₂.block_pts β j0, D₂.block_pts β j1)  have hj : ∀ j : Fin 2, j = j0 ∨ j = j1 := by    intro ⟨val, hval⟩    interval_cases val    · left; rfl    · right; rfl  have h_fib_eq₁ : ∀ (β : B₁) (x y : X₁), x ≠ y → (pair₁ β = s(x, y) ↔ (∃ j, D₁.block_pts β j = x) ∧ ∃ j', D₁.block_pts β j' = y) := by    intro β x y hxy    simp only [pair₁, Sym2.eq_iff]    constructor    · rintro (⟨h0, h1⟩ | ⟨h0, h1⟩)      · refine ⟨⟨j0, h0⟩, ⟨j1, h1⟩⟩      · refine ⟨⟨j1, h1⟩, ⟨j0, h0⟩⟩    · rintro ⟨⟨j, hjx⟩, ⟨j', hj'y⟩⟩      rcases hj j with rfl | rfl <;> rcases hj j' with rfl | rfl      · subst hjx hj'y; exact (hxy rfl).elim      · left; exact ⟨hjx, hj'y⟩      · right; exact ⟨hj'y, hjx⟩      · subst hjx hj'y; exact (hxy rfl).elim  have h_fib_eq₂ : ∀ (β : B₂) (x y : X₂), x ≠ y → (pair₂ β = s(x, y) ↔ (∃ j, D₂.block_pts β j = x) ∧ ∃ j', D₂.block_pts β j' = y) := by    intro β x y hxy    simp only [pair₂, Sym2.eq_iff]    constructor    · rintro (⟨h0, h1⟩ | ⟨h0, h1⟩)      · refine ⟨⟨j0, h0⟩, ⟨j1, h1⟩⟩      · refine ⟨⟨j1, h1⟩, ⟨j0, h0⟩⟩    · rintro ⟨⟨j, hjx⟩, ⟨j', hj'y⟩⟩      rcases hj j with rfl | rfl <;> rcases hj j' with rfl | rfl      · subst hjx hj'y; exact (hxy rfl).elim      · left; exact ⟨hjx, hj'y⟩      · right; exact ⟨hj'y, hjx⟩      · subst hjx hj'y; exact (hxy rfl).elim  have pair_not_diag₁ : ∀ β : B₁, ¬ (pair₁ β).IsDiag := by    intro β    rw [Sym2.mk_isDiag_iff]    intro h    have := D₁.block_inj β h    revert this    decide  have pair_not_diag₂ : ∀ β : B₂, ¬ (pair₂ β).IsDiag := by    intro β    rw [Sym2.mk_isDiag_iff]    intro h    have := D₂.block_inj β h    revert this    decide  have card_fib₁ : ∀ (p : Sym2 X₁), ¬ p.IsDiag → Nat.card { β : B₁ // pair₁ β = p } = lam := by    intro p hp    induction' p using Sym2.ind with x y    rw [Sym2.mk_isDiag_iff] at hp    have heq : { β : B₁ // pair₁ β = s(x, y) } ≃ { β : B₁ // (∃ j, D₁.block_pts β j = x) ∧ ∃ j', D₁.block_pts β j' = y } :=      Equiv.subtypeEquivRight (fun β => h_fib_eq₁ β x y hp)    rw [Nat.card_congr heq]    exact D₁.balance hp  have card_fib₂ : ∀ (p : Sym2 X₂), ¬ p.IsDiag → Nat.card { β : B₂ // pair₂ β = p } = lam := by    intro p hp    induction' p using Sym2.ind with x y    rw [Sym2.mk_isDiag_iff] at hp    have heq : { β : B₂ // pair₂ β = s(x, y) } ≃ { β : B₂ // (∃ j, D₂.block_pts β j = x) ∧ ∃ j', D₂.block_pts β j' = y } :=      Equiv.subtypeEquivRight (fun β => h_fib_eq₂ β x y hp)    rw [Nat.card_congr heq]    exact D₂.balance hp  let sym2_f : Sym2 X₁ ≃ Sym2 X₂ :=    { toFun := Sym2.map f      invFun := Sym2.map f.symm      left_inv := fun p => by induction' p using Sym2.ind with x y; simp      right_inv := fun p => by induction' p using Sym2.ind with x y; simp }  have sym2_f_isDiag : ∀ p : Sym2 X₁, (sym2_f p).IsDiag ↔ p.IsDiag := by    intro p    induction' p using Sym2.ind with x y    simp [sym2_f, Sym2.mk_isDiag_iff]  have sym2_f_symm_isDiag : ∀ p : Sym2 X₂, (sym2_f.symm p).IsDiag ↔ p.IsDiag := by    intro p    have := sym2_f_isDiag (sym2_f.symm p)    rw [sym2_f.apply_symm_apply] at this    exact this.symm  let pair_equiv : { p : Sym2 X₁ // ¬ p.IsDiag } ≃ { p : Sym2 X₂ // ¬ p.IsDiag } :=    { toFun := fun ⟨p, hp⟩ => ⟨sym2_f p, by rwa [sym2_f_isDiag]⟩      invFun := fun ⟨p, hp⟩ => ⟨sym2_f.symm p, by rwa [sym2_f_symm_isDiag]⟩      left_inv := fun ⟨p, hp⟩ => Subtype.ext (sym2_f.symm_apply_apply p)      right_inv := fun ⟨p, hp⟩ => Subtype.ext (sym2_f.apply_symm_apply p) }  have fib_iso : ∀ P : { p : Sym2 X₁ // ¬ p.IsDiag },      Nonempty ({ β : B₁ // pair₁ β = P.1 } ≃ { β : B₂ // pair₂ β = (pair_equiv P).1 }) := by    intro P    apply Finite.card_eq.mp    rw [card_fib₁ P.1 P.2, card_fib₂ (pair_equiv P).1 (pair_equiv P).2]  let e₁ : B₁ ≃ (P : { p : Sym2 X₁ // ¬ p.IsDiag }) × { β : B₁ // pair₁ β = P.1 } :=    { toFun := fun β => ⟨⟨pair₁ β, pair_not_diag₁ β⟩, ⟨β, rfl⟩⟩      invFun := fun p => p.2.1      left_inv := fun β => rfl      right_inv := fun ⟨⟨p, hp⟩, ⟨β, hβ⟩⟩ => by        dsimp at hβ        subst hβ        rfl }  let e₂ : B₂ ≃ (P : { p : Sym2 X₂ // ¬ p.IsDiag }) × { β : B₂ // pair₂ β = P.1 } :=    { toFun := fun β => ⟨⟨pair₂ β, pair_not_diag₂ β⟩, ⟨β, rfl⟩⟩      invFun := fun p => p.2.1      left_inv := fun β => rfl      right_inv := fun ⟨⟨p, hp⟩, ⟨β, hβ⟩⟩ => by        dsimp at hβ        subst hβ        rfl }  let e_sigma : ((P : { p : Sym2 X₁ // ¬ p.IsDiag }) × { β : B₁ // pair₁ β = P.1 }) ≃      ((P : { p : Sym2 X₂ // ¬ p.IsDiag }) × { β : B₂ // pair₂ β = P.1 }) :=    Equiv.sigmaCongr pair_equiv (fun P => (fib_iso P).some)  let g : B₁ ≃ B₂ := e₁.trans (e_sigma.trans e₂.symm)  have hg_pair : ∀ β : B₁, pair₂ (g β) = sym2_f (pair₁ β) := by    intro β    have this1 : (e_sigma (e₁ β)).1 = pair_equiv ⟨pair₁ β, pair_not_diag₁ β⟩ := rfl    have he2 : (e₂ (g β)).1 = (e_sigma (e₁ β)).1 := by      change (e₂ (e₂.symm (e_sigma (e₁ β)))).1 = (e_sigma (e₁ β)).1      rw [e₂.apply_symm_apply]    have := he2.trans this1    exact congr_arg Subtype.val this  refine ⟨f, g, fun β x => ?_⟩  have hp : pair₂ (g β) = s(f (D₁.block_pts β j0), f (D₁.block_pts β j1)) := by    rw [hg_pair β]    rfl  rw [bibd_fin2_exists_iff, bibd_fin2_exists_iff]  exact (bibd_sym2_mem_iff_f f (D₁.block_pts β j0) (D₁.block_pts β j1) x (D₂.block_pts (g β) j0) (D₂.block_pts (g β) j1) hp).symmtheorem bibd_isomorphic_of_block_clique_graph_iso {X₁ B₁ X₂ B₂ : Type*} [Finite B₁] [Finite B₂]    {v b r k lam : ℕ} (D₁ : BIBD X₁ B₁ v b r k lam) (D₂ : BIBD X₂ B₂ v b r k lam)    (h : Nonempty (bibd_block_clique_graph D₁ ≃g bibd_block_clique_graph D₂)) :    bibd_isomorphic D₁ D₂ := by  rcases k with _ | _ | _ | k  · exact bibd_isomorphic_of_k_zero D₁ D₂  · exact bibd_isomorphic_of_k_one D₁ D₂  · exact bibd_isomorphic_of_k_two D₁ D₂  · exact bibd_isomorphic_of_block_clique_graph_iso_of_three_le D₁ D₂ (by omega) h
See it in the graphDiscuss this resultChallenge it