# Systems of Containers and Enumeration Problems

• Alexander Sapozhenko
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3777)

## Abstract

We discuss a technique (named “the container method”) for enumeration problems. It was applied for obtaining upper bounds and asymptotically sharp estimates for the number of independent sets, codes, antichains in posets, sum-free sets, monotone boolean functions and so on. The container method works even the appropriate recurrent equalities are absent and the traditional generating function method is not applicable. The idea of the method is to reduce a considered enumeration problem to evaluating the number of independent sets in the appropriate graph. We give some examples of such reduction and a survey of upper bounds for the number of independent sets in graphs. The method is usually successful if considered graphs are almost regular and expanders.

## References

1. 1.
Alon, N.: Independent sets in regular graphs and Sum-Free Subsets of Finite Groups. Israel Journal of Math. 73(2), 247–256 (1991)
2. 2.
Bollobas, B.: Random Graphs, 2nd edn., p. 495. Cambridge University Press, Cambridge (2001)
3. 3.
Cameron, P., Erdős, P.: On the number of integers with various properties. In: Mollin, R.A. (ed.) Number Theory: Proc. First Conf. Can. Number Th. Ass., Banff, 1988, — de Gruyter, pp. 61–79 (1990)Google Scholar
4. 4.
Freiman, G.A.: Finite set addition. Izv. Vyssh. Uchebn. Zaved., Matematika 6(13), 202–213 (1959)
5. 5.
Green, B.: The Cameron-Erdos conjecture. Bull. Lond. Math. Soc. 36(6), 769–778 (2004)
6. 6.
Hansel, G.: Sur le nombre des fonctions booleen monotonesde n variables. C.R. Acad. Sci. Paris 262, 1088–1090 (1966)
7. 7.
8. 8.
Korobkov, V.K.: On monotone Boolean functions. Problemy Kibernetiki, M. Nauka 38, 5–108 (1981) (in Russian) Google Scholar
9. 9.
Korshunov, A.D.: On the number of monotone Boolean functions. Problemy Kibernetiki, M. Nauka 13, 5–28 (1965) (in Russian)Google Scholar
10. 10.
Korshunov, A.D., Sapozhenko, A.A.: On the number of binary codes with distance two. Problemy Kibernetiki, M. Nauka 40, 111–140 (1993) (in Russian) Google Scholar
11. 11.
Lev, V.F., Luczak, T., Schoen, T.: Sum-free sets in Abelian groups. Israel Journ. Math. 125(347), 347–367 (2001)
12. 12.
Sapozhenko, A.A.: On the number of connected sets with given size of boundary in graphs. Metody diskretnoi matematiki v reshenii combinatornykh zadach, - Novosibirsk 45, 35–58 (1987)Google Scholar
13. 13.
Sapozhenko, A.A.: On the number of antichains in posets. Discrete Mathematics and Applications 1(1), 35–59Google Scholar
14. 14.
Sapozhenko, A.A.: On the number of antichains in multylevelled posets. Discrete Mathematics and Applications 1(2), 149–171Google Scholar
15. 15.
Sapozhenko, A.A.: The Dedekind problem and boundary funcional method. Matematicheskie Voprosy Kibernetiki, M. Fizmatlit 9, 161–220 (2000)
16. 16.
Sapozhenko, A.A.: On the Number of Independent Sets in Bipartite Graphs with Large Minimum Degree. DIMACS Technical Report 2000-25, 24–31 (August 2000) (in Russian)Google Scholar
17. 17.
Sapozhenko, A.A.: On the Number of Independent Sets in expanders. Diskretnaya matematika, Moscow 13(1), 56–62 (2001) (in Russian)Google Scholar
18. 18.
Sapozhenko, A.A.: On the number of sum-free sets in Abelian groups. Vestnik Moskovskogo Universiteta, ser. Math., Mech. 4, 14–18 (2002) (Russian) Google Scholar
19. 19.
Sapozhenko, A.A.: The Cameron-Erdos conjecture. Doklady of Russian Academy of Sciences 393(6), 749–752 (2003) (English Translation)Google Scholar
20. 20.
Sapozhenko, A.A.: On searcing upper zeroes of monotone functions on ranked posets. Journal of Mathematical Physics and Computational Mathematics 31(12), 1871–1884 (1991) (English translation)Google Scholar
21. 21.
Sapozhenko, A.A.: On the Number of Independent Sets in Graphs. Problems of theoretical cybernetics. In: Proceedings of XIII International Conference, Kazan, pp. 85–93, May 27-31 (2002)Google Scholar
22. 22.
Stepanov, V.E.: Phase transition in random graphs. Theory Probab. Applcs 15, 187–203Google Scholar