Hostname: page-component-74656f9884-j7cmm Total loading time: 0 Render date: 2026-11-09T06:04:30.325Z Has data issue: false hasContentIssue false
  • English
  • Français

The Number of Independent Sets in a Regular Graph

Published online by Cambridge University Press:  13 November 2009

YUFEI ZHAO
YUFEI ZHAO*
Affiliation:
Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA 02139, USA (e-mail: yufeiz@mit.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We show that the number of independent sets in an N-vertex, d-regular graph is at most (2d+1 − 1)N/2d, where the bound is sharp for a disjoint union of complete d-regular bipartite graphs. This settles a conjecture of Alon in 1991 and Kahn in 2001. Kahn proved the bound when the graph is assumed to be bipartite. We give a short proof that reduces the general case to the bipartite case. Our method also works for a weighted generalization, i.e., an upper bound for the independence polynomial of a regular graph.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 19 , Issue 2 , March 2010 , pp. 315 - 320
Copyright
Copyright © Cambridge University Press 2009

References

[1]Alon, N. (1991) Independent sets in regular graphs and sum-free subsets of finite groups. Israel J. Math. 73 247–256.CrossRefGoogle Scholar
[2]van den Berg, J. and Steif, J. E. (1994) Percolation and the hardcore lattice gas model. Stoch. Proc. Appl. 59 179–197.CrossRefGoogle Scholar
[3]Cameron, P. J. and Erdős, P. (1990) On the number of sets of integers with various properties. In Number Theory (Banff, AB, 1988), de Gruyter, Berlin, pp. 61–79.Google Scholar
[4]Carroll, T., Galvin, D. and Tetali, P. (2009) Matchings and independent sets of a fixed size in regular graphs. J. Combin. Theory Ser. A 116 1219–1227.CrossRefGoogle Scholar
[5]Galvin, D. Personal communication.Google Scholar
[6]Galvin, D. An upper bound for the number of independent sets in regular graphs. Discrete Math., to appear.Google Scholar
[7]Galvin, D. and Tetali, P. (2004) On weighted graph homomorphisms. In Graphs, Morphisms and Statistical Physics, Vol. 63 of DIMACS Ser. Discrete Math. Theoret. Comput. Sci., AMS, Providence, RI, pp. 97–104.CrossRefGoogle Scholar
[8]Galvin, D. and Zhao, Y. The number of independent sets in a graph with small maximum degree. Submitted.Google Scholar
[9]Green, B. (2004) The Cameron–Erdős conjecture. Bull. London Math. Soc. 36 769–778.CrossRefGoogle Scholar
[10]Gutman, I. and Harary, F. (1983) Generalizations of the matching polynomial. Utilitas Math. 24 97–106.Google Scholar
[11]Häggström, O. (1997) Ergodicity of the hard-core model on 2 with parity-dependent activities. Ark. Mat. 35 171–184.CrossRefGoogle Scholar
[12]Kahn, J. (2001) An entropy approach to the hard-core model on bipartite graphs. Combin. Probab. Comput. 10 219–237.Google Scholar
[13]Kahn, J. (2002) Entropy, independent sets and antichains: A new approach to Dedekind's problem. Proc. Amer. Math. Soc. 130 371–378 (electronic).CrossRefGoogle Scholar
[14]Madiman, M. and Tetali, P. Information inequalities for joint distributions, with interpretations and applications. IEEE Trans. Information Theory, to appear.Google Scholar
[15]Sapozhenko, A. A. (2001) On the number of independent sets in extenders. Diskret. Mat. 13 56–62.Google Scholar
[16]Sapozhenko, A. A. (2003) The Cameron–Erdős conjecture. Dokl. Akad. Nauk 393 749–752.Google Scholar