Sharp Bounds for Graph-Codes Avoiding Complete Bipartite Differences
Abstract
Let dKs,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 Ks,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 dKs,t(n)=Θs,t(n−h). For h>1, this improves the general Os,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 Ks,t has a nonzero syndrome.
Related
- (2,ℱ)-Avoiding Coloring and B-Coloring under Bipartite Exclusions
- Negative edge correlation in complete bipartite graphs
- The domination number of the 2-token graph of the complete bipartite graph
- Maximal Linear Arrangement is NP complete on Bipartite Graphs
- Wild number for spanning trees in complete and complete bipartite graphs
BibTeX
@misc{bshouty2026sharp,
title = {{Sharp Bounds for Graph-Codes Avoiding Complete Bipartite Differences}},
author = {Nader H. Bshouty},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.35136},
eprint = {2610.35136},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.35136},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Sharp Bounds for Graph-Codes Avoiding Complete Bipartite Differences
AU - Nader H. Bshouty
PY - 2026
DA - 2026/10/26
PB - arXiv
DO - 10.48550/arxiv.2610.35136
UR - https://arxiv.org/abs/2610.35136
AB - 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.
ER -