AI & ML
Sharp Bounds for Graph-Codes Avoiding Complete Bipartite Differences
arXiv math.IT0 views
arXiv:2610.35136v1 Announce Type: cross 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)=\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.
Source:https://arxiv.org/abs/2610.35136PreviousRevisiting entropy and entropy-related magnitudes of a symbolic sequence and their estimationNextMovable Antenna Enabled Anti-Jamming: From Local Optimality Guaranteed Design to a Unified Antenna Position Optimization Framework
Related posts
Best Dyson Vacuum Deals (2026): Dyson Spot+Scrub Ai, Dyson V16 Piston Animal
0Wired
CPU, GPU, TPU, NPU: Who Will Power the Future of Computing?
0dev.to

Lower loss, worse stories: small NCMs trained on TinyStories
0dev.to

I Built LLM Explained: 43 Interactive Pages That Take You From Tokens to AI Agents
0dev.to OpenSource
MIT CSAIL: Astra edita 0,016% de pesos de Qwen3.5-0.8B y sube MATH-500 a 48,1%
0dev.to Programming

Gemma 4 in Rust on TorchTPU: A Native TPU Rig With PyO3 and MCP
0dev.to Rust