Counting almost independent sets in regular graphs
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$…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.28527
curl -X POST /api/v1/records/arxiv/2609.28527/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.28527/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'