Hostname: page-component-78c5997874-dh8gc Total loading time: 0 Render date: 2024-11-16T15:20:32.482Z 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: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

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.

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

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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