{"id":"arxiv/2609.28527","url":"https://arxiv.org/abs/2609.28527","tags":["math.CO"],"score":0,"title":"Counting almost independent sets in regular graphs","domain":"math.CO","source":"arxiv","authors":["Gaia Carenini"],"reviews":0,"subject":"math.CO","summary":"Kahn proved that, among bipartite $d$-regular graphs on $n$ vertices, the number of independent sets is maximized by a disjoint union of copies of $K_{d,d}$. Zhao later extended this result to all $d$-regular graphs. We prove a robust version of this theorem in which independent sets are replaced by sets spanning few internal edges. If $G$ is $d$-regular on $n$ vertices, then the number of subsets spanning at most $γdn$ edges is at most $$ 2^{n/2}\\exp\\left\\{ O\\bigl(γ\\log(e/γ)n\\bigr) + O\\bigl(n/d\\bigr) \\right\\}. $$ Both correction terms are sharp up to absolute constants: the $γ\\log(1/γ)n$…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-22","reactions":{}}