kst_code_max_density
The 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}.
Statement
noncomputable def kst_code_max_density (s t n : ℕ) : ℝ
- Defined in
- arXiv:2610.35136, Sharp Bounds for Graph-Codes Avoiding Complete Bipartite Differences, Section 1
- Verified
- 27 Oct 2026
- Axioms
- none listed
- Built on 1
- 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…
- Used by 7
- k22_code_max_density_two_pow_geFor every natural number r ≥ 2, the maximum density of a K_{2,2}-code on Fin (2^r) is at least 1 / 2^r.
- 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.
- four_cycle_graph_code_density_tendsto_one_along_powers_of_twoAs the natural number r tends to infinity, the sequence ((2 : ℝ) ^ r) * kst_code_max_density 2 2 (2 ^ r) tends to 1.
- kst_code_max_density_antitoneFor 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…
- 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…
- four_cycle_graph_code_asymptotic_density_eventually_leFor every real number ε > 0, for eventually all natural numbers n in Filter.atTop, (n : ℝ) * kst_code_max_density 2 2 n ≤ 1 + ε.
- k22_code_max_density_leFor every natural number n with 4 ≤ n, the maximum density of a K_{2,2}-code on Fin n, kst_code_max_density 2 2 n, is at most 1 / ((n : ℝ)…
Read back from the Lean
The declaration defines kst_code_max_density (s t n : ℕ) : ℝ as the supremum (in ℝ) over all sets of simple graphs C : Set (SimpleGraph (Fin n)) satisfying is_kst_code s t n C of the density (Set.ncard C : ℝ) / (2 ^ (n.choose 2) : ℝ).
Here, is_kst_code s t n C asserts that:
For all simple graphs G, G' : SimpleGraph (Fin n),
if G ∈ C, G' ∈ C, and G ≠ G',
then for all finite subsets A, B : Finset (Fin n),
if A and B are disjoint, A.card = s, and B.card = t,
then the symmetric difference graph symmDiff G G' is not equal to (⊤ : SimpleGraph (Fin n)).between (A : Set (Fin n)) (B : Set (Fin n)) (the graph on Fin n whose edges are precisely all pairs {u, v} with u ∈ A and v ∈ B, and no other edges).
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 maximum density of a K_{s,t}-code in simple graphs on Fin n. -/ noncomputable def kst_code_max_density (s t n : ℕ) : ℝ := open Classical in ⨆ (C : Set (SimpleGraph (Fin n))) (_hC : is_kst_code s t n C), (Set.ncard C : ℝ) / (2 ^ (n.choose 2) : ℝ)