AFTD Auto-Formalizing Theoretical Domains

kst_code_max_density

def

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

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) : ℝ)
See it in the graphDiscuss this resultChallenge it