{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,22]],"date-time":"2026-01-22T11:55:27Z","timestamp":1769082927414,"version":"3.49.0"},"reference-count":16,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2009,11,13]],"date-time":"2009-11-13T00:00:00Z","timestamp":1258070400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2010,3]]},"abstract":"<jats:p>We show that the number of independent sets in an <jats:italic>N<\/jats:italic>-vertex, <jats:italic>d<\/jats:italic>-regular graph is at most (2<jats:sup><jats:italic>d<\/jats:italic>+1<\/jats:sup> \u2212 1)<jats:sup><jats:italic>N<\/jats:italic>\/2<jats:italic>d<\/jats:italic><\/jats:sup>, where the bound is sharp for a disjoint union of complete <jats:italic>d<\/jats:italic>-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, <jats:italic>i.e.<\/jats:italic>, an upper bound for the independence polynomial of a regular graph.<\/jats:p>","DOI":"10.1017\/s0963548309990538","type":"journal-article","created":{"date-parts":[[2009,11,13]],"date-time":"2009-11-13T10:42:46Z","timestamp":1258108966000},"page":"315-320","source":"Crossref","is-referenced-by-count":70,"title":["The Number of Independent Sets in a Regular Graph"],"prefix":"10.1017","volume":"19","author":[{"given":"YUFEI","family":"ZHAO","sequence":"first","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2009,11,13]]},"reference":[{"key":"S0963548309990538_ref16","first-page":"749","article-title":"The Cameron\u2013Erd\u0151s conjecture","volume":"393","author":"Sapozhenko","year":"2003","journal-title":"Dokl. Akad. Nauk"},{"key":"S0963548309990538_ref15","first-page":"56","article-title":"On the number of independent sets in extenders","volume":"13","author":"Sapozhenko","year":"2001","journal-title":"Diskret. Mat."},{"key":"S0963548309990538_ref13","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-01-06058-0"},{"key":"S0963548309990538_ref12","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548301004631"},{"key":"S0963548309990538_ref11","doi-asserted-by":"publisher","DOI":"10.1007\/BF02559597"},{"key":"S0963548309990538_ref9","doi-asserted-by":"publisher","DOI":"10.1112\/S0024609304003650"},{"key":"S0963548309990538_ref6","unstructured":"[6] Galvin D. An upper bound for the number of independent sets in regular graphs. Discrete Math., to appear."},{"key":"S0963548309990538_ref4","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2008.12.008"},{"key":"S0963548309990538_ref5","unstructured":"[5] Galvin D. Personal communication."},{"key":"S0963548309990538_ref3","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1515\/9783110848632-008","volume-title":"Number Theory","author":"Cameron","year":"1990"},{"key":"S0963548309990538_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-4149(94)90132-5"},{"key":"S0963548309990538_ref10","first-page":"97","article-title":"Generalizations of the matching polynomial","volume":"24","author":"Gutman","year":"1983","journal-title":"Utilitas Math."},{"key":"S0963548309990538_ref1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02772952"},{"key":"S0963548309990538_ref14","unstructured":"[14] Madiman M. and Tetali P. Information inequalities for joint distributions, with interpretations and applications. IEEE Trans. Information Theory, to appear."},{"key":"S0963548309990538_ref8","unstructured":"[8] Galvin D. and Zhao Y. The number of independent sets in a graph with small maximum degree. Submitted."},{"key":"S0963548309990538_ref7","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/063\/07"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548309990538","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,28]],"date-time":"2019-04-28T20:32:20Z","timestamp":1556483540000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548309990538\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,11,13]]},"references-count":16,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2010,3]]}},"alternative-id":["S0963548309990538"],"URL":"https:\/\/doi.org\/10.1017\/s0963548309990538","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,11,13]]}}}