Advertisement

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.

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

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)zbMATHCrossRefMathSciNetGoogle Scholar
  2. 2.
    Bollobas, B.: Random Graphs, 2nd edn., p. 495. Cambridge University Press, Cambridge (2001)zbMATHGoogle Scholar
  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)MathSciNetGoogle Scholar
  5. 5.
    Green, B.: The Cameron-Erdos conjecture. Bull. Lond. Math. Soc. 36(6), 769–778 (2004)zbMATHCrossRefGoogle Scholar
  6. 6.
    Hansel, G.: Sur le nombre des fonctions booleen monotonesde n variables. C.R. Acad. Sci. Paris 262, 1088–1090 (1966)MathSciNetGoogle Scholar
  7. 7.
    Katerinochkina, N.n.: Searcing of maximum upper zero of monotone Boolean functions. Doklady Acad. Nauk of URSS 224(3), 557–560 (1975) (in Russian)Google Scholar
  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)zbMATHCrossRefMathSciNetGoogle Scholar
  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)MathSciNetGoogle Scholar
  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

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Alexander Sapozhenko
    • 1
  1. 1.Lomonosov UniversityMoscow

Personalised recommendations