Counting almost independent sets in regular graphs

Gaia Carenini

In the authors' words

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 $γ d n$ edges is at most $2^{n /2} exp {O (γ lo g (e / γ) n) + O (n / d)} .$ Both correction terms are sharp up to absolute constants: the $γ lo g (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.

Main resultThe abstract does not state a limitation.

Counting almost independent sets in regular graphs

In the authors' words

More on Combinatorics & discrete math that day

Thinning and sprinkling: from robust sampling to almost Hamiltonicity

Boolean threshold functions, neuron capacity, and memory retrieval

The Marcus-Minc Transform Inequality

The coarse Erd\H{o}s-P\'{o}sa theorem

A Combinatorial Proof of Hilton's Conjecture and Beyond