kst_code_card_le
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).
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.
uses
between_adj,Or.inl,bot_adjintro 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
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.
uses
Finset.card_fin,Finset.exists_subset_card_eq,Nat.le_add_right,Finset.card_sdiff_of_subset,Nat.add_sub_cancel_lefthave 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]
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.
uses
Finset.card_pos.mp,Finset.mem_sdiff.mp,disjoint_sdiff_self_righthave 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⟩
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.
uses
Set.disjoint_left,symmDiff_bot,symmDiff_right_inj,symmDiff_symmDiff_cancel_leftrw [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
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}.
uses
kst_code_card_le_exists_disjoint_nonempty_finsets,kst_code_card_le_between_top_ne_bot,kst_code_card_le_disjoint_image_symmDiffobtain ⟨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
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|.
uses
symmDiff_left_inj,Set.ncard_image_of_injective,Set.ncard_union_eq,Set.toFinitehave 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]
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)).
uses
Set.ncard_le_ncard,Set.subset_univ,Set.toFinite,Set.ncard_univ,Nat.card_eq_fintype_card,card_simpleGraph,Fintype.card_finhave 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
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).
uses
Nat.choose_pos,pow_succhave 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.
- The complete bipartite graph with parts A and B is represented formally as `(⊤ : SimpleGraph (Fin n)).between A B`, selecting all edges of the complete graph having one endpoint in A and the other in B.
- The `omega` tactic is used in several places to handle straightforward Presburger arithmetic on natural numbers (e.g., nonemptiness of sets of positive size and dividing the inequality 2|C| ≤ 2 · 2^(choose(n,2) - 1) by 2).
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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