kst_code_max_density_antitone
For all natural numbers s, t, n with 1 ≤ s and 1 ≤ t, the maximum density of a K_{s,t}-code is non-increasing in n: kst_code_max_density s t (n + 1) ≤ kst_code_max_density s t n.
Statement
theorem kst_code_max_density_antitone (s t n : ℕ) (hs : 1 ≤ s) (ht : 1 ≤ t) :
kst_code_max_density s t (n + 1) ≤ kst_code_max_density s t n- Source
- step towards four_cycle_graph_code_asymptotic_density_eventually_ge
- Verified
- 31 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- kst_code_max_densityThe maximum density of a K_{s,t}-code in simple graphs on vertex set [n] is the supremum over all K_{s,t}-codes C of |C| / 2^{n choose 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
- k22_code_max_density_ge_inv_pow_twoFor any natural numbers n and r such that n ≤ 2^r and 2 ≤ r, the maximum density of a K_{2,2}-code on Fin n is at least 1 / 2^r.
The proof, explained
The maximum density of a K_{s,t}-code is non-increasing. Given a code on n+1 vertices, partition it into 2^n fibers according to the neighborhood of the last vertex. The largest fiber has size at least |C|/2^n, and its restriction to the first n vertices forms a valid K_{s,t}-code on n vertices. Since (n+1 choose 2) = (n choose 2) + n, the density cannot increase.
neighborhood of vertex n matches
By analyzing whether vertices are the last vertex or earlier, the symmetric difference of two graphs agreeing on the neighborhood of the last vertex has edges only among the first n vertices.
have hNadj : ∀ a : Fin n, G1.Adj (Fin.castSucc a) (Fin.last n) ↔ G2.Adj (Fin.castSucc a) (Fin.last n) := by intro a have h1 : a ∈ kst_code_max_density_antitone_nhbd n G1 ↔ G1.Adj (Fin.castSucc a) (Fin.last n) := by simp [kst_code_max_density_antitone_nhbd] have h2 : a ∈ kst_code_max_density_antitone_nhbd n G2 ↔ G2.Adj (Fin.castSucc a) (Fin.last n) := by simp [kst_code_max_density_antitone_nhbd] rw [← h1, hN, h2] have hNadj' : ∀ a : Fin n, G1.Adj (Fin.last n) (Fin.castSucc a) ↔ G2.Adj (Fin.last n) (Fin.castSucc a) := by intro a exact (SimpleGraph.adj_comm G1 _ _).trans ((hNadj a).trans (SimpleGraph.adj_comm G2 _ _).symm) simp only [symmDiff, SimpleGraph.sup_adj, SimpleGraph.sdiff_adj, SimpleGraph.comap_adj, kst_code_max_density_antitone_restr] rcases Fin.eq_castSucc_or_eq_last u with ⟨a, rfl⟩ | rfl <;> rcases Fin.eq_castSucc_or_eq_last v with ⟨b, rfl⟩ | rfl · constructor · intro h; exact ⟨a, b, rfl, rfl, h⟩ · rintro ⟨a', b', h1, h2, h3⟩ rw [Fin.castSucc_inj] at h1 h2 subst h1; subst h2; exact h3 · constructor · intro h rcases h with ⟨h1, h2⟩ | ⟨h1, h2⟩ · exfalso; exact h2 ((hNadj a).mp h1) · exfalso; exact h2 ((hNadj a).mpr h1) · rintro ⟨a', b', h1, h2, h3⟩ exact (Fin.castSucc_ne_last b' h2.symm).elim · constructor · intro h rcases h with ⟨h1, h2⟩ | ⟨h1, h2⟩ · exfalso; exact h2 ((hNadj' b).mp h1) · exfalso; exact h2 ((hNadj' b).mpr h1) · rintro ⟨a', b', h1, h2, h3⟩ exact (Fin.castSucc_ne_last a' h1.symm).elim · constructor · intro h rcases h with ⟨h1, h2⟩ | ⟨h1, h2⟩ · exact absurd h1 (SimpleGraph.irrefl G1) · exact absurd h1 (SimpleGraph.irrefl G2) · rintro ⟨a', b', h1, h2, h3⟩ exact (Fin.castSucc_ne_last a' h1.symm).elim
main theorem
The density is non-increasing.
private lemma kst_code_max_density_antitone_between_lift (n : ℕ) (A B : Finset (Fin n)) (u v : Fin (n+1)) : (SimpleGraph.between ((A.image Fin.castSucc : Finset (Fin (n+1))) : Set _) ((B.image Fin.castSucc : Finset (Fin (n+1))) : Set _) ⊤).Adj u v ↔ ∃ a b : Fin n, u = Fin.castSucc a ∧ v = Fin.castSucc b ∧ (SimpleGraph.between (A : Set (Fin n)) (B : Set (Fin n)) ⊤).Adj a b := by have hmemA : ∀ a, (Fin.castSucc a ∈ ((A.image Fin.castSucc : Finset (Fin (n+1))) : Set _)) ↔ a ∈ A := by intro a; simp [Fin.castSucc_inj] have hmemB : ∀ a, (Fin.castSucc a ∈ ((B.image Fin.castSucc : Finset (Fin (n+1))) : Set _)) ↔ a ∈ B := by intro a; simp [Fin.castSucc_inj] have hlastA : Fin.last n ∉ ((A.image Fin.castSucc : Finset (Fin (n+1))) : Set _) := by simp [Fin.castSucc_ne_last] have hlastB : Fin.last n ∉ ((B.image Fin.castSucc : Finset (Fin (n+1))) : Set _) := by simp [Fin.castSucc_ne_last] simp only [SimpleGraph.between_adj, SimpleGraph.top_adj] rcases Fin.eq_castSucc_or_eq_last u with ⟨a, rfl⟩ | rfl <;> rcases Fin.eq_castSucc_or_eq_last v with ⟨b, rfl⟩ | rfl · rw [hmemA a, hmemB b, hmemA b, hmemB a] constructor · intro h exact ⟨a, b, rfl, rfl, fun hab => h.1 (by rw [hab]), h.2⟩ · rintro ⟨a', b', h1, h2, h3⟩ have ha : a = a' := Fin.castSucc_injective n h1 have hb : b = b' := Fin.castSucc_injective n h2 cases ha; cases hb exact ⟨fun h => h3.1 (Fin.castSucc_injective n h), h3.2⟩ · constructor · intro h rcases h.2 with ⟨_, hb⟩ | ⟨_, ha⟩ · exact (hlastB hb).elim · exact (hlastA ha).elim · rintro ⟨a', b', h1, h2, h3⟩ exact (Fin.castSucc_ne_last b' h2.symm).elim · constructor · intro h rcases h.2 with ⟨ha, _⟩ | ⟨hb, _⟩ · exact (hlastA ha).elim · exact (hlastB hb).elim · rintro ⟨a', b', h1, h2, h3⟩ exact (Fin.castSucc_ne_last a' h1.symm).elim · constructor · intro h; exact (h.1 rfl).elim · rintro ⟨a', b', h1, h2, h3⟩ exact (Fin.castSucc_ne_last a' h1.symm).elim private lemma kst_code_max_density_antitone_symmDiff_eq_between (n : ℕ) (G1 G2 : SimpleGraph (Fin (n+1))) (hN : kst_code_max_density_antitone_nhbd n G1 = kst_code_max_density_antitone_nhbd n G2) (A B : Finset (Fin n)) (heq : symmDiff (kst_code_max_density_antitone_restr n G1) (kst_code_max_density_antitone_restr n G2) = SimpleGraph.between (A : Set (Fin n)) (B : Set (Fin n)) ⊤) : symmDiff G1 G2 = SimpleGraph.between ((A.image Fin.castSucc : Finset (Fin (n+1))) : Set _) ((B.image Fin.castSucc : Finset (Fin (n+1))) : Set _) ⊤ := by apply SimpleGraph.ext funext u v apply propext rw [kst_code_max_density_antitone_adj_symmDiff n G1 G2 hN u v, kst_code_max_density_antitone_between_lift n A B u v] simp only [heq] private lemma kst_code_max_density_antitone_restr_injOn (n : ℕ) (N : Finset (Fin n)) : Set.InjOn (kst_code_max_density_antitone_restr n) {G : SimpleGraph (Fin (n+1)) | kst_code_max_density_antitone_nhbd n G = N} := by intro G1 h1 G2 h2 hrestr have hN : kst_code_max_density_antitone_nhbd n G1 = kst_code_max_density_antitone_nhbd n G2 := h1.trans h2.symm have hbot : symmDiff (kst_code_max_density_antitone_restr n G1) (kst_code_max_density_antitone_restr n G2) = ⊥ := by rw [hrestr, symmDiff_self] have hzero : symmDiff G1 G2 = ⊥ := by apply SimpleGraph.ext funext u v apply propext rw [kst_code_max_density_antitone_adj_symmDiff n G1 G2 hN u v, hbot] simp exact symmDiff_eq_bot.mp hzero private lemma kst_code_max_density_antitone_code_transfer (s t n : ℕ) (C : Set (SimpleGraph (Fin (n+1)))) (hC : is_kst_code s t (n+1) C) (G1 G2 : SimpleGraph (Fin (n+1))) (hG1 : G1 ∈ C) (hG2 : G2 ∈ C) (hN : kst_code_max_density_antitone_nhbd n G1 = kst_code_max_density_antitone_nhbd n G2) (hne : kst_code_max_density_antitone_restr n G1 ≠ kst_code_max_density_antitone_restr n G2) (A B : Finset (Fin n)) (hdisj : Disjoint A B) (hA : A.card = s) (hB : B.card = t) : symmDiff (kst_code_max_density_antitone_restr n G1) (kst_code_max_density_antitone_restr n G2) ≠ SimpleGraph.between (A : Set (Fin n)) (B : Set (Fin n)) ⊤ := by intro heq have hgraph := kst_code_max_density_antitone_symmDiff_eq_between n G1 G2 hN A B heq have hGne : G1 ≠ G2 := by intro h; exact hne (by rw [h]) have hdisj' : Disjoint (A.image Fin.castSucc) (B.image Fin.castSucc) := (Finset.disjoint_image (Fin.castSucc_injective n)).mpr hdisj have hA' : (A.image Fin.castSucc).card = s := by rw [Finset.card_image_of_injective _ (Fin.castSucc_injective n), hA] have hB' : (B.image Fin.castSucc).card = t := by rw [Finset.card_image_of_injective _ (Fin.castSucc_injective n), hB] exact hC hG1 hG2 hGne (A.image Fin.castSucc) (B.image Fin.castSucc) hdisj' hA' hB' hgraph private lemma kst_code_max_density_antitone_exists_smaller_code (s t n : ℕ) (C : Set (SimpleGraph (Fin (n+1)))) (hC : is_kst_code s t (n+1) C) : ∃ D : Set (SimpleGraph (Fin n)), is_kst_code s t n D ∧ (C.ncard : ℝ) / 2 ^ n ≤ (D.ncard : ℝ) := by classical let fib : Finset (Fin n) → Set (SimpleGraph (Fin (n+1))) := fun N => {G | G ∈ C ∧ kst_code_max_density_antitone_nhbd n G = N} have hcover : C = ⋃ N, fib N := by ext G constructor · intro hG exact Set.mem_iUnion.mpr ⟨kst_code_max_density_antitone_nhbd n G, hG, rfl⟩ · intro hG obtain ⟨N, hGN, -⟩ := Set.mem_iUnion.mp hG exact hGN have hsum : C.ncard ≤ ∑ N : Finset (Fin n), (fib N).ncard := by rw [hcover] exact Set.ncard_iUnion_le_of_fintype fib obtain ⟨N₀, -, hmax⟩ := Finset.exists_max_image (Finset.univ : Finset (Finset (Fin n))) (fun N => (fib N).ncard) ⟨∅, Finset.mem_univ ∅⟩ have hsum_le : ∑ N : Finset (Fin n), (fib N).ncard ≤ 2^n * (fib N₀).ncard := by calc ∑ N : Finset (Fin n), (fib N).ncard ≤ ∑ _N : Finset (Fin n), (fib N₀).ncard := Finset.sum_le_sum (fun N _ => hmax N (Finset.mem_univ N)) _ = 2^n * (fib N₀).ncard := by rw [Finset.sum_const, Finset.card_univ, Fintype.card_finset, Fintype.card_fin, smul_eq_mul] have hcard : C.ncard ≤ 2^n * (fib N₀).ncard := hsum.trans hsum_le refine ⟨kst_code_max_density_antitone_restr n '' fib N₀, ?_, ?_⟩ · intro G1 G2 hG1 hG2 hne A B hdisj hA hB obtain ⟨H1, hH1, rfl⟩ := hG1 obtain ⟨H2, hH2, rfl⟩ := hG2 exact kst_code_max_density_antitone_code_transfer s t n C hC H1 H2 hH1.1 hH2.1 (hH1.2.trans hH2.2.symm) hne A B hdisj hA hB · have hinj : Set.InjOn (kst_code_max_density_antitone_restr n) (fib N₀) := (kst_code_max_density_antitone_restr_injOn n N₀).mono (fun G hG => hG.2) rw [Set.InjOn.ncard_image hinj] have hcardR : (C.ncard : ℝ) ≤ 2^n * ((fib N₀).ncard : ℝ) := by exact_mod_cast hcard rw [div_le_iff₀ (by positivity : (0:ℝ) < 2^n)] calc (C.ncard : ℝ) ≤ 2^n * ((fib N₀).ncard : ℝ) := hcardR _ = ((fib N₀).ncard : ℝ) * 2^n := by ring private lemma kst_code_max_density_antitone_density_le_one (n : ℕ) (C : Set (SimpleGraph (Fin n))) : (C.ncard : ℝ) / 2 ^ n.choose 2 ≤ 1 := by have huniv : (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] have hle : C.ncard ≤ 2 ^ n.choose 2 := by rw [← huniv] exact Set.ncard_le_ncard (Set.subset_univ C) (Set.toFinite _) rw [div_le_one (by positivity : (0:ℝ) < 2 ^ n.choose 2)] exact_mod_cast hle private lemma kst_code_max_density_antitone_le_max_density (s t n : ℕ) (D : Set (SimpleGraph (Fin n))) (hD : is_kst_code s t n D) : (D.ncard : ℝ) / 2 ^ n.choose 2 ≤ ⨆ C, ⨆ (_ : is_kst_code s t n C), (C.ncard : ℝ) / 2 ^ n.choose 2 := by have hbdd : BddAbove (Set.range (fun C : Set (SimpleGraph (Fin n)) => ⨆ (_ : is_kst_code s t n C), (C.ncard : ℝ) / 2 ^ n.choose 2)) := by refine ⟨1, ?_⟩ rintro x ⟨C, rfl⟩ exact Real.iSup_le (fun hC => kst_code_max_density_antitone_density_le_one n C) (by norm_num) calc (D.ncard : ℝ) / 2 ^ n.choose 2 = ⨆ (_ : is_kst_code s t n D), (D.ncard : ℝ) / 2 ^ n.choose 2 := by rw [ciSup_pos hD] _ ≤ ⨆ C, ⨆ (_ : is_kst_code s t n C), (C.ncard : ℝ) / 2 ^ n.choose 2 := le_ciSup hbdd D /-- For all natural numbers s, t, n with 1 ≤ s and 1 ≤ t, the maximum density of a K_{s,t}-code is non-increasing in n: kst_code_max_density s t (n + 1) ≤ kst_code_max_density s t n. -/ theorem kst_code_max_density_antitone (s t n : ℕ) (hs : 1 ≤ s) (ht : 1 ≤ t) : kst_code_max_density s t (n + 1) ≤ kst_code_max_density s t n := by classical rw [kst_code_max_density] refine ciSup_le (fun C => ?_) by_cases hC : is_kst_code s t (n+1) C · rw [ciSup_pos hC] obtain ⟨D, hD, hle⟩ := kst_code_max_density_antitone_exists_smaller_code s t n C hC have hchoose : (n+1).choose 2 = n.choose 2 + n := by have h := Nat.choose_succ_succ n 1 simp [Nat.choose_one_right] at h omega calc (C.ncard : ℝ) / 2 ^ (n + 1).choose 2 = ((C.ncard : ℝ) / 2 ^ n) / 2 ^ n.choose 2 := by rw [hchoose, pow_add]; ring _ ≤ (D.ncard : ℝ) / 2 ^ n.choose 2 := by gcongr _ ≤ ⨆ D, ⨆ (_ : is_kst_code s t n D), (D.ncard : ℝ) / 2 ^ n.choose 2 := kst_code_max_density_antitone_le_max_density s t n D hD · rw [show (⨆ (_ : is_kst_code s t (n+1) C), (C.ncard : ℝ) / 2 ^ (n+1).choose 2) = 0 from by simp [hC]] exact Real.iSup_nonneg (fun C => Real.iSup_nonneg (fun h => by positivity))
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 Classicalnoncomputable def kst_code_max_density_antitone_nhbd (n : ℕ) (G : SimpleGraph (Fin (n+1))) : Finset (Fin n) := Finset.univ.filter (fun v => G.Adj (Fin.castSucc v) (Fin.last n))noncomputable def kst_code_max_density_antitone_restr (n : ℕ) (G : SimpleGraph (Fin (n+1))) : SimpleGraph (Fin n) := G.comap (Fin.castSucc : Fin n → Fin (n+1))private lemma kst_code_max_density_antitone_adj_symmDiff (n : ℕ) (G1 G2 : SimpleGraph (Fin (n+1))) (hN : kst_code_max_density_antitone_nhbd n G1 = kst_code_max_density_antitone_nhbd n G2) (u v : Fin (n+1)) : (symmDiff G1 G2).Adj u v ↔ ∃ a b : Fin n, u = Fin.castSucc a ∧ v = Fin.castSucc b ∧ (symmDiff (kst_code_max_density_antitone_restr n G1) (kst_code_max_density_antitone_restr n G2)).Adj a b := by have hNadj : ∀ a : Fin n, G1.Adj (Fin.castSucc a) (Fin.last n) ↔ G2.Adj (Fin.castSucc a) (Fin.last n) := by intro a have h1 : a ∈ kst_code_max_density_antitone_nhbd n G1 ↔ G1.Adj (Fin.castSucc a) (Fin.last n) := by simp [kst_code_max_density_antitone_nhbd] have h2 : a ∈ kst_code_max_density_antitone_nhbd n G2 ↔ G2.Adj (Fin.castSucc a) (Fin.last n) := by simp [kst_code_max_density_antitone_nhbd] rw [← h1, hN, h2] have hNadj' : ∀ a : Fin n, G1.Adj (Fin.last n) (Fin.castSucc a) ↔ G2.Adj (Fin.last n) (Fin.castSucc a) := by intro a exact (SimpleGraph.adj_comm G1 _ _).trans ((hNadj a).trans (SimpleGraph.adj_comm G2 _ _).symm) simp only [symmDiff, SimpleGraph.sup_adj, SimpleGraph.sdiff_adj, SimpleGraph.comap_adj, kst_code_max_density_antitone_restr] rcases Fin.eq_castSucc_or_eq_last u with ⟨a, rfl⟩ | rfl <;> rcases Fin.eq_castSucc_or_eq_last v with ⟨b, rfl⟩ | rfl · constructor · intro h; exact ⟨a, b, rfl, rfl, h⟩ · rintro ⟨a', b', h1, h2, h3⟩ rw [Fin.castSucc_inj] at h1 h2 subst h1; subst h2; exact h3 · constructor · intro h rcases h with ⟨h1, h2⟩ | ⟨h1, h2⟩ · exfalso; exact h2 ((hNadj a).mp h1) · exfalso; exact h2 ((hNadj a).mpr h1) · rintro ⟨a', b', h1, h2, h3⟩ exact (Fin.castSucc_ne_last b' h2.symm).elim · constructor · intro h rcases h with ⟨h1, h2⟩ | ⟨h1, h2⟩ · exfalso; exact h2 ((hNadj' b).mp h1) · exfalso; exact h2 ((hNadj' b).mpr h1) · rintro ⟨a', b', h1, h2, h3⟩ exact (Fin.castSucc_ne_last a' h1.symm).elim · constructor · intro h rcases h with ⟨h1, h2⟩ | ⟨h1, h2⟩ · exact absurd h1 (SimpleGraph.irrefl G1) · exact absurd h1 (SimpleGraph.irrefl G2) · rintro ⟨a', b', h1, h2, h3⟩ exact (Fin.castSucc_ne_last a' h1.symm).elimprivate lemma kst_code_max_density_antitone_between_lift (n : ℕ) (A B : Finset (Fin n)) (u v : Fin (n+1)) : (SimpleGraph.between ((A.image Fin.castSucc : Finset (Fin (n+1))) : Set _) ((B.image Fin.castSucc : Finset (Fin (n+1))) : Set _) ⊤).Adj u v ↔ ∃ a b : Fin n, u = Fin.castSucc a ∧ v = Fin.castSucc b ∧ (SimpleGraph.between (A : Set (Fin n)) (B : Set (Fin n)) ⊤).Adj a b := by have hmemA : ∀ a, (Fin.castSucc a ∈ ((A.image Fin.castSucc : Finset (Fin (n+1))) : Set _)) ↔ a ∈ A := by intro a; simp [Fin.castSucc_inj] have hmemB : ∀ a, (Fin.castSucc a ∈ ((B.image Fin.castSucc : Finset (Fin (n+1))) : Set _)) ↔ a ∈ B := by intro a; simp [Fin.castSucc_inj] have hlastA : Fin.last n ∉ ((A.image Fin.castSucc : Finset (Fin (n+1))) : Set _) := by simp [Fin.castSucc_ne_last] have hlastB : Fin.last n ∉ ((B.image Fin.castSucc : Finset (Fin (n+1))) : Set _) := by simp [Fin.castSucc_ne_last] simp only [SimpleGraph.between_adj, SimpleGraph.top_adj] rcases Fin.eq_castSucc_or_eq_last u with ⟨a, rfl⟩ | rfl <;> rcases Fin.eq_castSucc_or_eq_last v with ⟨b, rfl⟩ | rfl · rw [hmemA a, hmemB b, hmemA b, hmemB a] constructor · intro h exact ⟨a, b, rfl, rfl, fun hab => h.1 (by rw [hab]), h.2⟩ · rintro ⟨a', b', h1, h2, h3⟩ have ha : a = a' := Fin.castSucc_injective n h1 have hb : b = b' := Fin.castSucc_injective n h2 cases ha; cases hb exact ⟨fun h => h3.1 (Fin.castSucc_injective n h), h3.2⟩ · constructor · intro h rcases h.2 with ⟨_, hb⟩ | ⟨_, ha⟩ · exact (hlastB hb).elim · exact (hlastA ha).elim · rintro ⟨a', b', h1, h2, h3⟩ exact (Fin.castSucc_ne_last b' h2.symm).elim · constructor · intro h rcases h.2 with ⟨ha, _⟩ | ⟨hb, _⟩ · exact (hlastA ha).elim · exact (hlastB hb).elim · rintro ⟨a', b', h1, h2, h3⟩ exact (Fin.castSucc_ne_last a' h1.symm).elim · constructor · intro h; exact (h.1 rfl).elim · rintro ⟨a', b', h1, h2, h3⟩ exact (Fin.castSucc_ne_last a' h1.symm).elimprivate lemma kst_code_max_density_antitone_symmDiff_eq_between (n : ℕ) (G1 G2 : SimpleGraph (Fin (n+1))) (hN : kst_code_max_density_antitone_nhbd n G1 = kst_code_max_density_antitone_nhbd n G2) (A B : Finset (Fin n)) (heq : symmDiff (kst_code_max_density_antitone_restr n G1) (kst_code_max_density_antitone_restr n G2) = SimpleGraph.between (A : Set (Fin n)) (B : Set (Fin n)) ⊤) : symmDiff G1 G2 = SimpleGraph.between ((A.image Fin.castSucc : Finset (Fin (n+1))) : Set _) ((B.image Fin.castSucc : Finset (Fin (n+1))) : Set _) ⊤ := by apply SimpleGraph.ext funext u v apply propext rw [kst_code_max_density_antitone_adj_symmDiff n G1 G2 hN u v, kst_code_max_density_antitone_between_lift n A B u v] simp only [heq]private lemma kst_code_max_density_antitone_restr_injOn (n : ℕ) (N : Finset (Fin n)) : Set.InjOn (kst_code_max_density_antitone_restr n) {G : SimpleGraph (Fin (n+1)) | kst_code_max_density_antitone_nhbd n G = N} := by intro G1 h1 G2 h2 hrestr have hN : kst_code_max_density_antitone_nhbd n G1 = kst_code_max_density_antitone_nhbd n G2 := h1.trans h2.symm have hbot : symmDiff (kst_code_max_density_antitone_restr n G1) (kst_code_max_density_antitone_restr n G2) = ⊥ := by rw [hrestr, symmDiff_self] have hzero : symmDiff G1 G2 = ⊥ := by apply SimpleGraph.ext funext u v apply propext rw [kst_code_max_density_antitone_adj_symmDiff n G1 G2 hN u v, hbot] simp exact symmDiff_eq_bot.mp hzeroprivate lemma kst_code_max_density_antitone_code_transfer (s t n : ℕ) (C : Set (SimpleGraph (Fin (n+1)))) (hC : is_kst_code s t (n+1) C) (G1 G2 : SimpleGraph (Fin (n+1))) (hG1 : G1 ∈ C) (hG2 : G2 ∈ C) (hN : kst_code_max_density_antitone_nhbd n G1 = kst_code_max_density_antitone_nhbd n G2) (hne : kst_code_max_density_antitone_restr n G1 ≠ kst_code_max_density_antitone_restr n G2) (A B : Finset (Fin n)) (hdisj : Disjoint A B) (hA : A.card = s) (hB : B.card = t) : symmDiff (kst_code_max_density_antitone_restr n G1) (kst_code_max_density_antitone_restr n G2) ≠ SimpleGraph.between (A : Set (Fin n)) (B : Set (Fin n)) ⊤ := by intro heq have hgraph := kst_code_max_density_antitone_symmDiff_eq_between n G1 G2 hN A B heq have hGne : G1 ≠ G2 := by intro h; exact hne (by rw [h]) have hdisj' : Disjoint (A.image Fin.castSucc) (B.image Fin.castSucc) := (Finset.disjoint_image (Fin.castSucc_injective n)).mpr hdisj have hA' : (A.image Fin.castSucc).card = s := by rw [Finset.card_image_of_injective _ (Fin.castSucc_injective n), hA] have hB' : (B.image Fin.castSucc).card = t := by rw [Finset.card_image_of_injective _ (Fin.castSucc_injective n), hB] exact hC hG1 hG2 hGne (A.image Fin.castSucc) (B.image Fin.castSucc) hdisj' hA' hB' hgraphprivate lemma kst_code_max_density_antitone_exists_smaller_code (s t n : ℕ) (C : Set (SimpleGraph (Fin (n+1)))) (hC : is_kst_code s t (n+1) C) : ∃ D : Set (SimpleGraph (Fin n)), is_kst_code s t n D ∧ (C.ncard : ℝ) / 2 ^ n ≤ (D.ncard : ℝ) := by classical let fib : Finset (Fin n) → Set (SimpleGraph (Fin (n+1))) := fun N => {G | G ∈ C ∧ kst_code_max_density_antitone_nhbd n G = N} have hcover : C = ⋃ N, fib N := by ext G constructor · intro hG exact Set.mem_iUnion.mpr ⟨kst_code_max_density_antitone_nhbd n G, hG, rfl⟩ · intro hG obtain ⟨N, hGN, -⟩ := Set.mem_iUnion.mp hG exact hGN have hsum : C.ncard ≤ ∑ N : Finset (Fin n), (fib N).ncard := by rw [hcover] exact Set.ncard_iUnion_le_of_fintype fib obtain ⟨N₀, -, hmax⟩ := Finset.exists_max_image (Finset.univ : Finset (Finset (Fin n))) (fun N => (fib N).ncard) ⟨∅, Finset.mem_univ ∅⟩ have hsum_le : ∑ N : Finset (Fin n), (fib N).ncard ≤ 2^n * (fib N₀).ncard := by calc ∑ N : Finset (Fin n), (fib N).ncard ≤ ∑ _N : Finset (Fin n), (fib N₀).ncard := Finset.sum_le_sum (fun N _ => hmax N (Finset.mem_univ N)) _ = 2^n * (fib N₀).ncard := by rw [Finset.sum_const, Finset.card_univ, Fintype.card_finset, Fintype.card_fin, smul_eq_mul] have hcard : C.ncard ≤ 2^n * (fib N₀).ncard := hsum.trans hsum_le refine ⟨kst_code_max_density_antitone_restr n '' fib N₀, ?_, ?_⟩ · intro G1 G2 hG1 hG2 hne A B hdisj hA hB obtain ⟨H1, hH1, rfl⟩ := hG1 obtain ⟨H2, hH2, rfl⟩ := hG2 exact kst_code_max_density_antitone_code_transfer s t n C hC H1 H2 hH1.1 hH2.1 (hH1.2.trans hH2.2.symm) hne A B hdisj hA hB · have hinj : Set.InjOn (kst_code_max_density_antitone_restr n) (fib N₀) := (kst_code_max_density_antitone_restr_injOn n N₀).mono (fun G hG => hG.2) rw [Set.InjOn.ncard_image hinj] have hcardR : (C.ncard : ℝ) ≤ 2^n * ((fib N₀).ncard : ℝ) := by exact_mod_cast hcard rw [div_le_iff₀ (by positivity : (0:ℝ) < 2^n)] calc (C.ncard : ℝ) ≤ 2^n * ((fib N₀).ncard : ℝ) := hcardR _ = ((fib N₀).ncard : ℝ) * 2^n := by ringprivate lemma kst_code_max_density_antitone_density_le_one (n : ℕ) (C : Set (SimpleGraph (Fin n))) : (C.ncard : ℝ) / 2 ^ n.choose 2 ≤ 1 := by have huniv : (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] have hle : C.ncard ≤ 2 ^ n.choose 2 := by rw [← huniv] exact Set.ncard_le_ncard (Set.subset_univ C) (Set.toFinite _) rw [div_le_one (by positivity : (0:ℝ) < 2 ^ n.choose 2)] exact_mod_cast hleprivate lemma kst_code_max_density_antitone_le_max_density (s t n : ℕ) (D : Set (SimpleGraph (Fin n))) (hD : is_kst_code s t n D) : (D.ncard : ℝ) / 2 ^ n.choose 2 ≤ ⨆ C, ⨆ (_ : is_kst_code s t n C), (C.ncard : ℝ) / 2 ^ n.choose 2 := by have hbdd : BddAbove (Set.range (fun C : Set (SimpleGraph (Fin n)) => ⨆ (_ : is_kst_code s t n C), (C.ncard : ℝ) / 2 ^ n.choose 2)) := by refine ⟨1, ?_⟩ rintro x ⟨C, rfl⟩ exact Real.iSup_le (fun hC => kst_code_max_density_antitone_density_le_one n C) (by norm_num) calc (D.ncard : ℝ) / 2 ^ n.choose 2 = ⨆ (_ : is_kst_code s t n D), (D.ncard : ℝ) / 2 ^ n.choose 2 := by rw [ciSup_pos hD] _ ≤ ⨆ C, ⨆ (_ : is_kst_code s t n C), (C.ncard : ℝ) / 2 ^ n.choose 2 := le_ciSup hbdd D/-- For all natural numbers s, t, n with 1 ≤ s and 1 ≤ t, the maximum density of a K_{s,t}-code is non-increasing in n: kst_code_max_density s t (n + 1) ≤ kst_code_max_density s t n. -/theorem kst_code_max_density_antitone (s t n : ℕ) (hs : 1 ≤ s) (ht : 1 ≤ t) : kst_code_max_density s t (n + 1) ≤ kst_code_max_density s t n := by classical rw [kst_code_max_density] refine ciSup_le (fun C => ?_) by_cases hC : is_kst_code s t (n+1) C · rw [ciSup_pos hC] obtain ⟨D, hD, hle⟩ := kst_code_max_density_antitone_exists_smaller_code s t n C hC have hchoose : (n+1).choose 2 = n.choose 2 + n := by have h := Nat.choose_succ_succ n 1 simp [Nat.choose_one_right] at h omega calc (C.ncard : ℝ) / 2 ^ (n + 1).choose 2 = ((C.ncard : ℝ) / 2 ^ n) / 2 ^ n.choose 2 := by rw [hchoose, pow_add]; ring _ ≤ (D.ncard : ℝ) / 2 ^ n.choose 2 := by gcongr _ ≤ ⨆ D, ⨆ (_ : is_kst_code s t n D), (D.ncard : ℝ) / 2 ^ n.choose 2 := kst_code_max_density_antitone_le_max_density s t n D hD · rw [show (⨆ (_ : is_kst_code s t (n+1) C), (C.ncard : ℝ) / 2 ^ (n+1).choose 2) = 0 from by simp [hC]] exact Real.iSup_nonneg (fun C => Real.iSup_nonneg (fun h => by positivity))