AFTD Auto-Formalizing Theoretical Domains

kst_code_card_le

theoremverified

Let s, t, n be natural numbers with 1 ≤ s, 1 ≤ t, and s + t ≤ n. Every K_{s,t}-code C of simple graphs on vertex set [n] has cardinality at most 2^{n choose 2 - 1}.

Statement

theorem kst_code_card_le (s t n : ℕ) (hs : 1 ≤ s) (ht : 1 ≤ t) (hn : s + t ≤ n)
    (C : Set (SimpleGraph (Fin n))) (hC : is_kst_code s t n C) :
    Set.ncard C ≤ 2 ^ (n.choose 2 - 1)
Source
arXiv:2610.35136, Sharp Bounds for Graph-Codes Avoiding Complete Bipartite Differences, Proposition 3.2
Verified
28 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • is_kst_codeA family C of simple graphs on vertex set [n] is a K_{s,t}-code if for every two distinct graphs G, G' in C and every pair of disjoint…
  • card_simpleGraphThe number of simple graphs on a finite vertex set V is 2^{C(|V|,2)}, where C(|V|,2) = |V|(|V|-1)/2 is the number of unordered pairs of…
Used by 1
  • kst_code_density_odd_oddLet s and t be odd natural numbers, and let n be a natural number such that s + t ≤ n. Then the maximum density of a K_{s,t}-code in…

Read back from the Lean

Let $s, t, n$ be natural numbers such that $1 \le s$, $1 \le t$, and $s + t \le n$. Let $C$ be a set of simple graphs on vertex set Fin n satisfying is_kst_code s t n C. Then the cardinality of $C$ (Set.ncard C) is at most $2^{\binom{n}{2} - 1}$.

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 proved by a translation argument on the Boolean algebra of simple graphs on vertex set [n]. Fixing disjoint subsets A, B ⊆ [n] of sizes s and t, let H be the complete bipartite graph between A and B. Because C is a K_{s,t}-code, no two graphs in C differ by H, which implies that C is disjoint from its shift C Δ H = {G Δ H | G ∈ C}. Since the shift map G ↦ G Δ H is injective, |C Δ H| = |C|, and their disjoint union has size 2|C|. The total number of graphs on [n] is 2^(choose(n,2)), so 2|C| ≤ 2^(choose(n,2)), which yields |C| ≤ 2^(choose(n,2) - 1).

  1. A complete bipartite graph between two sets containing distinct vertices is non-empty.

    Suppose for contradiction that the complete bipartite graph between s and t is the empty graph ⊥. Since a ∈ s, b ∈ t, and a ≠ b, the pair {a, b} is an edge in the bipartite graph between s and t. But the empty graph ⊥ has no edges, yielding a contradiction.

    lines 6–11

    uses between_adj, Or.inl, bot_adj

      intro h
      have hadj : ((⊤ : SimpleGraph V).between s t).Adj a b := by
        rw [between_adj]
        exact ⟨hab, Or.inl ⟨ha, hb⟩⟩
      rw [h, bot_adj] at hadj
      exact hadj
  2. There exist disjoint subsets A and U \ A of [n] having cardinalities s and t, respectively.

    Since s + t ≤ n and the universe [n] has size n, there exists a subset U ⊆ [n] of size s + t. Since s ≤ s + t = |U|, U in turn contains a subset A of size s. The set difference U \ A is disjoint from A and has cardinality |U| - |A| = (s + t) - s = t.

    lines 17–24

    uses Finset.card_fin, Finset.exists_subset_card_eq, Nat.le_add_right, Finset.card_sdiff_of_subset, Nat.add_sub_cancel_left

      have h_univ : s + t ≤ (Finset.univ : Finset (Fin n)).card := by
        rw [Finset.card_fin]
        exact hn
      obtain ⟨U, -, hU⟩ := Finset.exists_subset_card_eq h_univ
      have hs_le : s ≤ U.card := by rw [hU]; exact Nat.le_add_right s t
      obtain ⟨A, hAU, hA⟩ := Finset.exists_subset_card_eq hs_le
      have hB_card : (U \ A).card = t := by
        rw [Finset.card_sdiff_of_subset hAU, hU, hA, Nat.add_sub_cancel_left]
  3. The sets A and U \ A contain distinct vertices a ∈ A and b ∈ U \ A.

    Because s ≥ 1 and t ≥ 1, the sets A and U \ A have positive cardinality, so there exist elements a ∈ A and b ∈ U \ A. If a = b, then a ∈ U \ A would imply a ∉ A, contradicting a ∈ A. Hence a ≠ b, completing the construction of the required witness.

    lines 25–32

    uses Finset.card_pos.mp, Finset.mem_sdiff.mp, disjoint_sdiff_self_right

      have hA_pos : 0 < A.card := by omega
      have hB_pos : 0 < (U \ A).card := by omega
      obtain ⟨a, ha⟩ := Finset.card_pos.mp hA_pos
      obtain ⟨b, hb⟩ := Finset.card_pos.mp hB_pos
      have hab : a ≠ b := by
        rintro rfl
        exact (Finset.mem_sdiff.mp hb).2 ha
      exact ⟨A, U \ A, a, b, disjoint_sdiff_self_right, hA, hB_card, ha, hb, hab⟩
  4. Any K_{s,t}-code C is disjoint from its image under symmetric difference with the complete bipartite graph H between A and B.

    Suppose for contradiction that some graph belongs to both C and {G Δ H | G ∈ C}, meaning there is G ∈ C such that G Δ H ∈ C. Since H ≠ ⊥, G ≠ G Δ H. The symmetric difference of G and G Δ H simplifies to H by the cancellation identity G Δ (G Δ H) = H. But by the definition of a K_{s,t}-code, no two distinct graphs in C can have symmetric difference equal to H, a contradiction.

    lines 40–52

    uses Set.disjoint_left, symmDiff_bot, symmDiff_right_inj, symmDiff_symmDiff_cancel_left

      rw [Set.disjoint_left]
      rintro _ hx ⟨G, hG, rfl⟩
      have hne : G ≠ symmDiff G H := by
        intro heq
        have h1 : symmDiff G ⊥ = symmDiff G H := by
          rw [symmDiff_bot]
          exact heq
        rw [symmDiff_right_inj] at h1
        exact hH_ne h1.symm
      have hdiff : symmDiff G (symmDiff G H) = H := symmDiff_symmDiff_cancel_left G H
      have hnot := hC hG hx hne A B hdisj hA hB
      rw [← hH_def] at hnot
      exact hnot hdiff
  5. There exists a non-empty complete bipartite graph H between disjoint parts of sizes s and t such that C and {G Δ H | G ∈ C} are disjoint.

    By the earlier lemmas, since s, t ≥ 1 and s + t ≤ n, there exist disjoint subsets A, B ⊆ [n] of sizes s, t and distinct elements a ∈ A, b ∈ B. Defining H to be the complete bipartite graph between A and B, H is non-empty because it contains the edge {a, b}. Consequently, C is disjoint from {G Δ H | G ∈ C}.

    lines 58–62

    uses kst_code_card_le_exists_disjoint_nonempty_finsets, kst_code_card_le_between_top_ne_bot, kst_code_card_le_disjoint_image_symmDiff

      obtain ⟨A, B, a, b, hdisj, hA, hB, ha, hb, hab⟩ :=
        kst_code_card_le_exists_disjoint_nonempty_finsets s t n hs ht hn
      set H : SimpleGraph (Fin n) := (⊤ : SimpleGraph (Fin n)).between (A : Set (Fin n)) (B : Set (Fin n))
      have hH_ne : H ≠ ⊥ := kst_code_card_le_between_top_ne_bot (A : Set (Fin n)) (B : Set (Fin n)) a b ha hb hab
      have hdisj_sets := kst_code_card_le_disjoint_image_symmDiff s t n C hC A B hdisj hA hB H rfl hH_ne
  6. The shift map G ↦ G Δ H is injective, and the union C ∪ {G Δ H | G ∈ C} has cardinality 2|C|.

    Symmetric difference with H is injective because G₁ Δ H = G₂ Δ H implies G₁ = G₂. An injective map preserves cardinality, so |{G Δ H | G ∈ C}| = |C|. Since C and this image are disjoint finite sets, the cardinality of their union is |C| + |C| = 2|C|.

    lines 63–69

    uses symmDiff_left_inj, Set.ncard_image_of_injective, Set.ncard_union_eq, Set.toFinite

      have hinj : Function.Injective (fun G : SimpleGraph (Fin n) => symmDiff G H) := by
        intro G₁ G₂ h
        rwa [symmDiff_left_inj] at h
      have h_img_card : ((fun G => symmDiff G H) '' C).ncard = C.ncard :=
        Set.ncard_image_of_injective C hinj
      have h_union : (C ∪ (fun G => symmDiff G H) '' C).ncard = C.ncard + C.ncard := by
        rw [Set.ncard_union_eq hdisj_sets (Set.toFinite C) (Set.toFinite _), h_img_card]
  7. The union is a subset of all simple graphs on [n], so 2|C| ≤ 2^(choose(n, 2)).

    The union C ∪ {G Δ H | G ∈ C} is contained in the universe of all simple graphs on vertex set [n], which has cardinality 2^(choose(n, 2)). Since the cardinality of a subset is bounded by that of the ambient set, 2|C| ≤ 2^(choose(n, 2)).

    lines 70–74

    uses Set.ncard_le_ncard, Set.subset_univ, Set.toFinite, Set.ncard_univ, Nat.card_eq_fintype_card, card_simpleGraph, Fintype.card_fin

      have h_le_univ : (C ∪ (fun G => symmDiff G H) '' C).ncard ≤ (Set.univ : Set (SimpleGraph (Fin n))).ncard :=
        Set.ncard_le_ncard (Set.subset_univ _) (Set.toFinite _)
      have h_univ : (Set.univ : Set (SimpleGraph (Fin n))).ncard = 2 ^ (n.choose 2) := by
        rw [Set.ncard_univ, Nat.card_eq_fintype_card, card_simpleGraph, Fintype.card_fin]
      rw [h_union, h_univ] at h_le_univ
  8. The code C has cardinality at most 2^(choose(n, 2) - 1).

    Since s, t ≥ 1 and s + t ≤ n, we have n ≥ 2, which implies choose(n, 2) ≥ 1. Thus choose(n, 2) = (choose(n, 2) - 1) + 1, so 2^(choose(n, 2)) = 2^(choose(n, 2) - 1) · 2. Dividing the inequality 2|C| ≤ 2 · 2^(choose(n, 2) - 1) by 2 gives |C| ≤ 2^(choose(n, 2) - 1).

    lines 75–79

    uses Nat.choose_pos, pow_succ

      have hn2 : 2 ≤ n := by omega
      have hk : 1 ≤ n.choose 2 := Nat.choose_pos hn2
      have hk' : n.choose 2 = (n.choose 2 - 1) + 1 := by omega
      rw [hk', pow_succ] at h_le_univ
      omega
between_adj
An edge {v, w} is present in the bipartite subgraph of G between sets s and t if and only if {v, w} is an edge in G and one endpoint lies in s while the other lies in t.
Or.inl
If proposition a holds, then the disjunction a ∨ b holds.
bot_adj
The empty graph ⊥ has no edges between any two vertices.
Finset.card_fin
The universal finset of Fin n has cardinality n.
Finset.exists_subset_card_eq
Any finite set of cardinality at least n contains a subset of cardinality n.
Nat.le_add_right
For any natural numbers n and k, n ≤ n + k.
Finset.card_sdiff_of_subset
If s is a subset of t, then |t \ s| = |t| - |s|.
Nat.add_sub_cancel_left
For any natural numbers n and m, (n + m) - n = m.
Finset.card_pos.mp
A finite set with strictly positive cardinality is nonempty.
Finset.mem_sdiff.mp
An element of t \ s belongs to t and does not belong to s.
disjoint_sdiff_self_right
Any set x is disjoint from y \ x.
Set.disjoint_left
Two sets are disjoint if and only if no element of the first belongs to the second.
symmDiff_bot
The symmetric difference of any element with the bottom element ⊥ is itself.
symmDiff_right_inj
Symmetric difference on the left is injective: a Δ b = a Δ c if and only if b = c.
symmDiff_symmDiff_cancel_left
Symmetric difference is self-inverting: a Δ (a Δ b) = b.
kst_code_card_le_exists_disjoint_nonempty_finsets
For natural numbers 1 ≤ s, 1 ≤ t, and s + t ≤ n, there exist disjoint subsets A, B ⊆ [n] of sizes s and t, and distinct elements a ∈ A and b ∈ B.
kst_code_card_le_between_top_ne_bot
If a ∈ s, b ∈ t, and a ≠ b, then the complete bipartite graph between s and t is not the empty graph ⊥.
kst_code_card_le_disjoint_image_symmDiff
A K_{s,t}-code C is disjoint from its image under symmetric difference with any nonempty complete bipartite graph H between disjoint sets of sizes s and t.
symmDiff_left_inj
Symmetric difference on the right is injective: a Δ b = c Δ b if and only if a = c.
Set.ncard_image_of_injective
An injective map between sets preserves cardinality.
Set.ncard_union_eq
The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
Set.toFinite
A set whose subtype is finite is finite.
Set.ncard_le_ncard
If s ⊆ t and t is finite, then |s| ≤ |t|.
Set.subset_univ
Every set is a subset of the universal set.
Set.ncard_univ
The cardinality of the universal set of a type is the cardinality of the type.
Nat.card_eq_fintype_card
For a finite type, its cardinality in ℕ equals its Fintype cardinality.
card_simpleGraph
The number of simple graphs on a finite vertex set V is 2^(|V| choose 2).
Fintype.card_fin
The type Fin n has cardinality n.
Nat.choose_pos
If k ≤ n, then (n choose k) is positive.
pow_succ
For any base a and exponent n, a^(n + 1) = a^n * a.

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 SimpleGraphprivate lemma kst_code_card_le_between_top_ne_bot {V : Type*} (s t : Set V) (a b : V)    (ha : a ∈ s) (hb : b ∈ t) (hab : a ≠ b) :    (⊤ : SimpleGraph V).between s t ≠ ⊥ := by  intro h  have hadj : ((⊤ : SimpleGraph V).between s t).Adj a b := by    rw [between_adj]    exact ⟨hab, Or.inl ⟨ha, hb⟩⟩  rw [h, bot_adj] at hadj  exact hadjprivate lemma kst_code_card_le_exists_disjoint_nonempty_finsets (s t n : ℕ)    (hs : 1 ≤ s) (ht : 1 ≤ t) (hn : s + t ≤ n) :    ∃ (A B : Finset (Fin n)) (a b : Fin n),      Disjoint A B ∧ A.card = s ∧ B.card = t ∧ a ∈ A ∧ b ∈ B ∧ a ≠ b := by  have h_univ : s + t ≤ (Finset.univ : Finset (Fin n)).card := by    rw [Finset.card_fin]    exact hn  obtain ⟨U, -, hU⟩ := Finset.exists_subset_card_eq h_univ  have hs_le : s ≤ U.card := by rw [hU]; exact Nat.le_add_right s t  obtain ⟨A, hAU, hA⟩ := Finset.exists_subset_card_eq hs_le  have hB_card : (U \ A).card = t := by    rw [Finset.card_sdiff_of_subset hAU, hU, hA, Nat.add_sub_cancel_left]  have hA_pos : 0 < A.card := by omega  have hB_pos : 0 < (U \ A).card := by omega  obtain ⟨a, ha⟩ := Finset.card_pos.mp hA_pos  obtain ⟨b, hb⟩ := Finset.card_pos.mp hB_pos  have hab : a ≠ b := by    rintro rfl    exact (Finset.mem_sdiff.mp hb).2 ha  exact ⟨A, U \ A, a, b, disjoint_sdiff_self_right, hA, hB_card, ha, hb, hab⟩private lemma kst_code_card_le_disjoint_image_symmDiff (s t n : ℕ) (C : Set (SimpleGraph (Fin n)))    (hC : is_kst_code s t n C) (A B : Finset (Fin n)) (hdisj : Disjoint A B)    (hA : A.card = s) (hB : B.card = t)    (H : SimpleGraph (Fin n)) (hH_def : H = (⊤ : SimpleGraph (Fin n)).between (A : Set (Fin n)) (B : Set (Fin n)))    (hH_ne : H ≠ ⊥) :    Disjoint C ((fun G => symmDiff G H) '' C) := by  rw [Set.disjoint_left]  rintro _ hx ⟨G, hG, rfl⟩  have hne : G ≠ symmDiff G H := by    intro heq    have h1 : symmDiff G ⊥ = symmDiff G H := by      rw [symmDiff_bot]      exact heq    rw [symmDiff_right_inj] at h1    exact hH_ne h1.symm  have hdiff : symmDiff G (symmDiff G H) = H := symmDiff_symmDiff_cancel_left G H  have hnot := hC hG hx hne A B hdisj hA hB  rw [← hH_def] at hnot  exact hnot hdiff/-- Upper bound on the size of a K_{s,t}-code for s, t ≥ 1 and n ≥ s + t. -/theorem kst_code_card_le (s t n : ℕ) (hs : 1 ≤ s) (ht : 1 ≤ t) (hn : s + t ≤ n)    (C : Set (SimpleGraph (Fin n))) (hC : is_kst_code s t n C) :    Set.ncard C ≤ 2 ^ (n.choose 2 - 1) := by  obtain ⟨A, B, a, b, hdisj, hA, hB, ha, hb, hab⟩ :=    kst_code_card_le_exists_disjoint_nonempty_finsets s t n hs ht hn  set H : SimpleGraph (Fin n) := (⊤ : SimpleGraph (Fin n)).between (A : Set (Fin n)) (B : Set (Fin n))  have hH_ne : H ≠ ⊥ := kst_code_card_le_between_top_ne_bot (A : Set (Fin n)) (B : Set (Fin n)) a b ha hb hab  have hdisj_sets := kst_code_card_le_disjoint_image_symmDiff s t n C hC A B hdisj hA hB H rfl hH_ne  have hinj : Function.Injective (fun G : SimpleGraph (Fin n) => symmDiff G H) := by    intro G₁ G₂ h    rwa [symmDiff_left_inj] at h  have h_img_card : ((fun G => symmDiff G H) '' C).ncard = C.ncard :=    Set.ncard_image_of_injective C hinj  have h_union : (C ∪ (fun G => symmDiff G H) '' C).ncard = C.ncard + C.ncard := by    rw [Set.ncard_union_eq hdisj_sets (Set.toFinite C) (Set.toFinite _), h_img_card]  have h_le_univ : (C ∪ (fun G => symmDiff G H) '' C).ncard ≤ (Set.univ : Set (SimpleGraph (Fin n))).ncard :=    Set.ncard_le_ncard (Set.subset_univ _) (Set.toFinite _)  have h_univ : (Set.univ : Set (SimpleGraph (Fin n))).ncard = 2 ^ (n.choose 2) := by    rw [Set.ncard_univ, Nat.card_eq_fintype_card, card_simpleGraph, Fintype.card_fin]  rw [h_union, h_univ] at h_le_univ  have hn2 : 2 ≤ n := by omega  have hk : 1 ≤ n.choose 2 := Nat.choose_pos hn2  have hk' : n.choose 2 = (n.choose 2 - 1) + 1 := by omega  rw [hk', pow_succ] at h_le_univ  omega
See it in the graphDiscuss this resultChallenge it