is_kst_code
A 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 subsets A, B of [n] with |A| = s and |B| = t, the symmetric difference of G and G' is not the complete bipartite graph between A and B.
Statement
def is_kst_code (s t n : ℕ) (C : Set (SimpleGraph (Fin n))) : Prop
- Defined in
- arXiv:2610.35136, Sharp Bounds for Graph-Codes Avoiding Complete Bipartite Differences, Section 1
- Verified
- 27 Oct 2026
- Axioms
- none listed
- Used by 12
- 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.
- kst_code_linear_construction_finite_fieldLet n, s, t, r ≥ 1 be integers, and let w_1, ..., w_n in (ZMod 2)^r be vectors such that the sum of w_i over S is nonzero for every subset…
- 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…
- kst_code_card_leLet 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…
- is_kst_code_singletonAny singleton set consisting of a single graph on vertex set [n] is a K_{s,t}-code.
- is_kst_code_even_edge_graphsLet s and t be odd natural numbers, and let n be a natural number. The set of simple graphs on vertex set [n] with an even number of edges…
- k22_code_exists_dense_family_of_power_of_twoFor every natural number r ≥ 2, there exists a K_{2,2}-code on Fin (2^r) with density at least 1 / 2^r.
- k22_code_card_leLet n be a natural number with 4 ≤ n. For every K_{2,2}-code C of simple graphs on Fin n, (n - 2) * Set.ncard C ≤ 2 ^ (n.choose 2).
- 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 : ℝ)…
- k22_code_shortening_densityFor natural numbers 4 ≤ n ≤ N, any K_{2,2}-code on Fin N can be restricted to Fin n with density at least that of the original code.
- 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}.
Read back from the Lean
A set C of simple graphs on vertex set Fin n is a (s, t)-code if for all pairs of distinct graphs G, G' ∈ C, and for all disjoint subsets A, B of Fin n such that |A| = s and |B| = t, the symmetric difference of G and G' is not equal to the complete bipartite graph on parts A and B (i.e., the spanning simple graph on Fin n whose edges are precisely all pairs {u, v} with u ∈ A and v ∈ B).
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
/-- A family of graphs on Fin n is a K_{s,t}-code if the symmetric difference of any two distinct members is not a complete bipartite graph with parts of sizes s and t. -/ def is_kst_code (s t n : ℕ) (C : Set (SimpleGraph (Fin n))) : Prop := ∀ ⦃G G' : SimpleGraph (Fin n)⦄, G ∈ C → G' ∈ C → G ≠ G' → ∀ (A B : Finset (Fin n)), Disjoint A B → A.card = s → B.card = t → symmDiff G G' ≠ (⊤ : SimpleGraph (Fin n)).between (A : Set (Fin n)) (B : Set (Fin n))