PreprintCC BY-NC-ND 4.0arXiv
Counting almost independent sets in regular graphs
Abstract
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 Kd,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 2n/2exp{ O(γlog(e/γ)n) + O(n/d) }. Both correction terms are sharp up to absolute constants: the γlog(1/γ)n term is necessary when d is sufficiently large in terms of γ, while the n/d term is already necessary for independent sets. Our result answers a question of Seth.
Related
- On Counting Independent Sets in Regular Hypergraphs
- Almost Linear Universal Point Sets for Planar Graphs
- Automorphism groups of Cayley graphs on almost simple groups with normal connection sets
- Nonexistence of Strongly Regular Graphs via Gegenbauer Positivity and SRG Counting
- Existence of regular sets in circulant quartic graphs: a complete characterization
BibTeX
@misc{carenini2026counting,
title = {{Counting almost independent sets in regular graphs}},
author = {Gaia Carenini},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.28527},
eprint = {2609.28527},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.28527},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Counting almost independent sets in regular graphs
AU - Gaia Carenini
PY - 2026
DA - 2026/09/22
PB - arXiv
DO - 10.48550/arxiv.2609.28527
UR - https://arxiv.org/abs/2609.28527
AB - 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/2exp{ O(γlog(e/γ)n) + O(n/d) }. Both correction terms are sharp up to absolute constants: the γlog(1/γ)n term is necessary when d is sufficiently large in terms of γ, while the n/d term is already necessary for independent sets. Our result answers a question of Seth.
ER -