{"id":"arxiv/2610.35136","url":"https://arxiv.org/abs/2610.35136","tags":["math.CO","cs.IT"],"score":0,"title":"Sharp Bounds for Graph-Codes Avoiding Complete Bipartite Differences","domain":"math.CO","source":"arxiv","authors":["Nader H. Bshouty"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-26","reactions":{}}