Geodesic
On the number of independent sets in extenders
Diskretnaya Matematika, Tome 13 (2001) no. 1, pp. 56-62 
A. A. Sapozhenko. On the number of independent sets in extenders. Diskretnaya Matematika, Tome 13 (2001) no. 1, pp. 56-62. http://geodesic.mathdoc.fr/item/DM_2001_13_1_a1/
@article{DM_2001_13_1_a1,
     author = {A. A. Sapozhenko},
     title = {On the number of independent sets in extenders},
     journal = {Diskretnaya Matematika},
     pages = {56--62},
     year = {2001},
     volume = {13},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2001_13_1_a1/}
}
TY  - JOUR
AU  - A. A. Sapozhenko
TI  - On the number of independent sets in extenders
JO  - Diskretnaya Matematika
PY  - 2001
SP  - 56
EP  - 62
VL  - 13
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DM_2001_13_1_a1/
LA  - ru
ID  - DM_2001_13_1_a1
ER  - 
%0 Journal Article
%A A. A. Sapozhenko
%T On the number of independent sets in extenders
%J Diskretnaya Matematika
%D 2001
%P 56-62
%V 13
%N 1
%U http://geodesic.mathdoc.fr/item/DM_2001_13_1_a1/
%G ru
%F DM_2001_13_1_a1

Voir la notice de l'article provenant de la source Math-Net.Ru

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.

[1] Alon N., “Independent sets in regular graphs and sum-free subsets of finite groups”, Israel J. Math., 73:2 (1991), 247–256 | DOI | MR | Zbl

[2] Korshunov A. D., Sapozhenko A. A., “O chisle dvoichnykh kodov s rasstoyaniem 2”, Probl. kibernetiki, 40 (1983), 111–140 | MR

[3] Sapozhenko A. A., “On the number of independent sets in graphs and the number of sum-free sets in abelian groups”, Materialy Mezhdunarodnoi konferentsii “Diskretnyi analiz i issledovanie operatsii” (26 iyunya–1 iyulya), 2000, 89

[4] Sapozhenko A. A., “O chisle nezavisimykh mnozhestv v dvudolnykh grafakh”, Trudy IV mezhdunarodnoi konferentsii “Diskretnye modeli v teorii upravlyayuschikh sistem” (19-25 iyunya 2000), MAKS Press, Moskva, 116–119

[5] Sapozhenko A. A., “On the number of independent sets in bipartite graphs with large minimum degree”, DIMACS Technical Report 2000-25 (August 2000)

[6] Sapozhenko A. A., “O chisle svyaznykh podmnozhestv s zadannoi moschnostyu granitsy v dvudolnykh grafakh”, Metody diskretnogo analiza v reshenii kombinatornykh zadach, 45, 1987, 42–70 | MR | Zbl

[7] Sapozhenko A. A., “O chisle svyaznykh podmnozhestv s zadannoi moschnostyu okrestnosti v grafe”, Diskretnyi analiz i issledovanie operatsii, 4:3 (1997), 18–34 | MR

[8] Shiryaev A. N., Veroyatnost, Nauka, Moskva, 1989 | MR