Source-linked AI summary
Sharp Bounds for Graph-Codes Avoiding Complete Bipartite Differences
Nader H. Bshouty
TL;DR
The paper asks for the maximum density of graph families with no pairwise symmetric difference equal to a fixed K_s,t. For each fixed positive s,t, the paper determines the maximum density of K_s,t-codes up to constant factors; the BCH property makes both factors nonzero. The density is exactly 1/2 when both part sizes are odd and otherwise has polynomial exponent half the largest even part size.
Problem
The paper asks for the maximum density of graph families with no pairwise symmetric difference equal to a fixed K_s,t.
Source: §1 · p. 1Method
For each fixed positive s,t, the paper determines the maximum density of K_s,t-codes up to constant factors; the BCH property makes both factors nonzero.
Source: §1.3 · p. 4, §1.4 · p. 5Results
The density is exactly 1/2 when both part sizes are odd and otherwise has polynomial exponent half the largest even part size.
Source: §1.1 · p. 2Takeaways & Limitations
For both even part sizes, the BCH construction gives each forbidden copy a nonzero syndrome, matching the upper bound.
Source: §1.4 · p. 5The asymptotic statements take s,t fixed; when n < s+t, both densities are one.
Source: §1.1 · p. 2
Abstract
from arXiv · showhide
Let $d_{K_{s,t}}(n)$ be the largest fraction of all graphs on $[n]$ in a family containing no two distinct members whose symmetric difference is a copy of $K_{s,t}$. We determine this maximum density for every fixed pair of positive integers $s,t$. If both part sizes are odd, it is known that the density is exactly $1/2$. Otherwise, let $2h$ be the largest even part size. We prove $$ d_{K_{s,t}}(n)=\Theta_{s,t}(n^{-h}). $$ For $h>1$, this improves the general $O_{s,t}(1/n)$ upper bound obtained from Alon's two-copy gluing theorem~\cite{Alon2024}. The sharp bounds for even stars were already proved by Alon and are recovered as special cases. The upper bound uses the Frankl--F\"uredi forbidden-intersection theorem. For the lower bound, we construct binary linear codes using BCH codes. When exactly one part size is even, we assign to each edge the sum of the binary vectors assigned to its endpoints. When both part sizes are even, we identify these vectors with elements of a finite field and assign to each edge the product of its endpoint elements. In both cases, every copy of $K_{s,t}$ has a nonzero syndrome.
1 Introduction
The paper studies the largest families of graphs whose pairwise symmetric differences avoid a fixed complete bipartite graph. It classifies the maximum density: exactly 1/2 when both part sizes are odd, and otherwise polynomial decay with exponent half the largest even part size.
1.1 Main result
- The maximum density is 1/2 when both part sizes are odd; otherwise, it decays polynomially with exponent half the largest even part size.The odd-part result is stated as exact, while the exponent does not depend on the size of an odd part.Source: §1.1 · p. 2
1.2 Previous work and our results
- The earlier even-star bounds are recovered as special cases, while prior general upper bounds for complete bipartite differences were O_s,t(n^-1).Alon’s even-star work used Frankl–Füredi for its upper bound and BCH codes for its lower bound.Source: §1.2 · p. 3
1 Introduction
- The paper determines the maximum density up to constant factors for every fixed pair of positive integers s,t.A graph-code is a family in which no two distinct members have symmetric difference exactly K_s,t.Source: §1 · p. 1, §1.3 · p. 4
1.3 Our contribution
- The upper bound adapts the Frankl–Füredi forbidden-intersection theorem by fixing a set of u vertices and considering K_R,A graphs.This improves the previously known general O_u,h(n^-1) bound when h > 1.Source: §1.3 · p. 4
- For the lower bound, BCH-based linear codes use endpoint-vector sums when exactly one part is even and finite-field endpoint products when both are even.The constructions make every forbidden copy have a nonzero edge-vector sum.Source: §1.3 · p. 4, §1.4 · p. 5
1.4 Proof overview
- The proof overview reduces the upper bound to counting a special family of complete bipartite graphs, then transfers that count to the full code.The Frankl–Füredi theorem bounds how many such graphs can belong to a code; translating every code member by the same fixed graph preserves the forbidden-difference condition.Source: §1.4 · p. 5
2 Preliminaries
These preliminaries give an averaging tool and a forbidden-intersection bound for upper bounds, then describe syndrome kernels for constructing linear codes.
2.1 Translations and averaging
- If every code intersects a fixed graph family T in at most M members, translation averaging bounds its density by M/|T|.Every translate remains a code, and translating a fixed member of T uniformly samples all graphs.Source: §2.1 · pp. 5–6
2.2 A forbidden-intersection theorem
- The upper-bound argument uses the Frankl–Füredi theorem for families of (2h−1)-element sets that avoid pairwise intersections of size h−1.For h ≥ 2, the cited formulation makes the allowed intersection sizes equivalent to excluding exactly h−1.Source: §2.2 · p. 6
2.3 Linear parity checks
- Assigning binary vectors to edges gives a linear syndrome; if every forbidden K_{s,t} has nonzero syndrome, its kernel is a code of codimension at most r and density at least 2^-r.Field-valued labels in F_{2^r} can be represented as r binary parity checks.Source: §2.3 · pp. 6–7
3 The upper bound for arbitrary graph-codes
The section establishes upper bounds when a part is even and proves the exact density when both parts are odd. The even-part argument reduces the problem to a forbidden-intersection bound.
3.1 At least one part is even
- For K_{u,2h}, the proof forms a family of sets whose pairwise intersection cannot have size h−1, then applies Theorem 2.2.An intersection of size h−1 would make the symmetric difference of the corresponding graphs a forbidden K_{u,2h}.Source: §3.1 · p. 7
- When at least one part is even, applying Proposition 3.1 with the larger part as 2h proves Theorem 1.1’s upper bound.The proof’s denominator has order m^(2h−1), with m = Θ_u(n).Source: §3.1 · pp. 7–8
3.2 Both parts odd
- When both part sizes are odd, the maximum density is exactly 1/2.The upper bound pairs graphs by toggling a fixed K_{s,t}; graphs with an even number of edges give a matching lower bound.Source: §3.2 · p. 8
4 Linear constructions
The linear constructions turn vertex labels with nonzero sums on even subsets into graph-codes with density matching the upper bound. The labels and edge assignments depend on the parity of the two part sizes.
4.1 Vertex labels that detect even subsets
- A modified standard BCH construction [6, Chapter 5], also used by Alon [1, Section 2.2], yields binary vectors with nonzero sums on every positive even subset of at most 2h vertices, using h ceil(log2 n) rather than 2h ceil(log2(n + 1)) coordinates.Source: §4.1 · p. 9
4.2 Constructing linear codes from vertex vectors
- Vertex vectors with nonzero sums on every subset of size s or t yield a binary linear K_{s,t}-code of codimension at most r and density at least 2^-r.The coordinate reduction in this refinement leaves the asymptotic density unchanged and saves h binary coordinates when n is a power of two.Source: §4.2 · p. 9
4.3 The linear construction
- When the other part is odd, edges receive endpoint-label sums; when it is even, nonzero subset sums of both part sizes feed the linear code construction.For the odd case, the even-sized part's vertices have odd degree in the bipartite graph, so the syndrome is nonzero by the even-subset label property.Source: §4.3 · p. 10
- For at least one even part, a binary linear K_{s,t}-code exists with codimension at most h⌈log2 n⌉, where 2h is the largest even part size.The construction uses endpoint sums when the other part is odd and the vertex-vector construction when it is even.Source: §4.3 · p. 10