New sharp limits found for graph families avoiding certain bipartite patterns
Sharp Bounds for Graph-Codes Avoiding Complete Bipartite Differences
Information Theory
Summary
The paper studies families of graphs where no two differ exactly by a special kind of small bipartite graph called a complete bipartite graph. The authors find precise limits on how large these families can be, depending on the sizes of the parts of this bipartite graph. They improve previous upper bounds and construct special binary codes to show these limits are tight. Their work connects graph theory with coding theory and uses advanced combinatorial methods.
What this means in practice
- •For network designers: Design communication networks that avoid specific error patterns represented by certain bipartite subgraphs in graph difference codes.
- •For error correction engineers: Create binary error-correcting codes sensitive to forbidden bipartite graph differences to enhance code reliability under structured noise.
A theory result. No direct application yet.
Authors
Nader H. Bshouty
Abstract
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)=Θ_{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üredi 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.