RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 2001 Volume 13, Issue 1, Pages 56–62 (Mi dm276)

This article is cited in 31 papers

On the number of independent sets in extenders

A. A. Sapozhenko


Abstract: We improve Alon's upper bound for the number of independent sets in regular graphs and extend it to almost regular graphs. We also present an upper bound for the number of independent sets of non-typical size for almost regular graphs and an upper bound of the form $2^{(n/2)(1-c\delta)}$, where $c$ is a constant, for the number of independent sets in almost regular $\delta$-expanders.

UDC: 519.1

Received: 15.12.2000

DOI: 10.4213/dm276


 English version:
Discrete Mathematics and Applications, 2001, 11:2, 155–161

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025