{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T01:50:02Z","timestamp":1760233802884,"version":"build-2065373602"},"reference-count":26,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2021,2,25]],"date-time":"2021-02-25T00:00:00Z","timestamp":1614211200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>This paper studies the problem of upper bounding the number of independent sets in a graph, expressed in terms of its degree distribution. For bipartite regular graphs, Kahn (2001) established a tight upper bound using an information-theoretic approach, and he also conjectured an upper bound for general graphs. His conjectured bound was recently proved by Sah et al. (2019), using different techniques not involving information theory. The main contribution of this work is the extension of Kahn\u2019s information-theoretic proof technique to handle irregular bipartite graphs. In particular, when the bipartite graph is regular on one side, but may be irregular on the other, the extended entropy-based proof technique yields the same bound as was conjectured by Kahn (2001) and proved by Sah et al. (2019).<\/jats:p>","DOI":"10.3390\/e23030270","type":"journal-article","created":{"date-parts":[[2021,2,25]],"date-time":"2021-02-25T05:20:08Z","timestamp":1614230408000},"page":"270","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["A Generalized Information-Theoretic Approach for Bounding the Number of Independent Sets in Bipartite Graphs"],"prefix":"10.3390","volume":"23","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5681-1273","authenticated-orcid":false,"given":"Igal","family":"Sason","sequence":"first","affiliation":[{"name":"Department of Electrical Engineering, Technion\u2014Israel Institute of Technology, Haifa 3200003, Israel"}]}],"member":"1968","published-online":{"date-parts":[[2021,2,25]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Agrawal, M., and Arvind, V. (2014). An entropy-based proof for the Moore bound for irregular graphs. Perspectives on Computational Complexity, Birkh\u00e4user.","DOI":"10.1007\/978-3-319-05446-9"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/0097-3165(86)90019-1","article-title":"Some intersection theorems for ordered sets and graphs","volume":"43","author":"Chung","year":"1986","journal-title":"J. Comb. Theory Ser. A"},{"key":"ref_3","unstructured":"Cover, T.M., and Thomas, J.A. (2006). Elements of Information Theory, John Wiley & Sons. [2nd ed.]."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"2505","DOI":"10.1109\/18.720546","article-title":"The method of types","volume":"44","year":"1998","journal-title":"IEEE Trans. Inform. Theory"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Csisz\u00e1r, I., and K\u00f6rner, J. (2011). Information Theory: Coding Theorems for Discrete Memoryless Systems, Cambridge University Press. [2nd ed.].","DOI":"10.1017\/CBO9780511921889"},{"key":"ref_6","first-page":"241","article-title":"On two problems of information theory","volume":"8","author":"Erdos","year":"1963","journal-title":"Publ. Mathematical Inst. Hung. Acad. Sci."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"749","DOI":"10.1080\/00029890.2004.11920139","article-title":"Hypergraphs, entropy and inequalities","volume":"111","author":"Friedgut","year":"2004","journal-title":"Am. Math. Mon."},{"key":"ref_8","unstructured":"Galvin, D. (2014). Three tutorial lectures on entropy and counting. First Lake Michigan Workshop on Combinatorics and Graph Theory, Western Michigan University."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1002\/rsa.20532","article-title":"A tail bound for read-k families of functions","volume":"47","author":"Gavinsky","year":"2015","journal-title":"Random Struct. Algorithms"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"3610","DOI":"10.1109\/TIT.2018.2806486","article-title":"A conditional information inequality and its combinatorial applications","volume":"5","author":"Kaced","year":"2018","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1017\/S0963548301004631","article-title":"An entropy approach to the hard-core model on bipartite graphs","volume":"10","author":"Kahn","year":"2001","journal-title":"Comb. Probab. Comput."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1090\/S0002-9939-01-06058-0","article-title":"Entropy, independent sets and antichains: A new approach to Dedekind\u2019s problem","volume":"130","author":"Kahn","year":"2001","journal-title":"Proc. Am. Math. Soc."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Madiman, M., and Tetali, P. (2007, January 24\u201329). Sandwich bounds for joint entropy. Proceedings of the 2007 IEEE International Symposium on Information Theory, Nice, France.","DOI":"10.1109\/ISIT.2007.4557276"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"2699","DOI":"10.1109\/TIT.2010.2046253","article-title":"Information inequalities for joint distributions with interpretations and applications","volume":"56","author":"Madiman","year":"2010","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1109\/TIT.1974.1055150","article-title":"On the fractional weight of distinct binary n-tuples","volume":"20","author":"Massey","year":"1974","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/0097-3165(77)90083-8","article-title":"An information-theoretic method in combinatorial theory","volume":"23","author":"Pippenger","year":"1977","journal-title":"J. Comb. Theory Ser. A"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"2096","DOI":"10.1109\/18.782146","article-title":"Entropy and enumeration of boolean functions","volume":"45","author":"Pippenger","year":"1999","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1006\/jcta.1996.2727","article-title":"An entropy proof of Bregman\u2019s theorem","volume":"77","author":"Radhakrishnan","year":"1997","journal-title":"J. Comb. Theory Ser. A"},{"key":"ref_19","unstructured":"Radhakrishnan, J. (2001). Entropy and counting. Proceedings of the IIT Kharagpur, Golden Jubilee Volume on Computational Mathematics, Modelling and Algorithms, Narosa Publishers."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"679","DOI":"10.1090\/S0002-9947-1985-0784009-0","article-title":"Six standard deviations suffice","volume":"289","author":"Spencer","year":"1985","journal-title":"Trans. Am. Math. Soc."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1007\/BF02772952","article-title":"Independent sets in regular graphs and sum-free subsets of finite groups","volume":"73","author":"Alon","year":"1991","journal-title":"Isr. J. Math."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1016\/j.ejc.2015.02.005","article-title":"Counting independent sets in graphs","volume":"48","author":"Samotij","year":"2015","journal-title":"Eur. J. Comb."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1017\/S0963548309990538","article-title":"The number of independent sets in a regular graph","volume":"19","author":"Zhao","year":"2010","journal-title":"Comb. Probab. Comput."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1007\/s00373-010-0976-z","article-title":"The number of independent sets in a graph with small maximum degree","volume":"27","author":"Galvin","year":"2011","journal-title":"Graphs Comb."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1016\/j.jctb.2019.01.007","article-title":"The number of independent sets in an irregular graph","volume":"138","author":"Sah","year":"2019","journal-title":"J. Comb. Theory Ser. B"},{"key":"ref_26","unstructured":"Sah, A., Sawhney, M., Stoner, D., and Zhao, Y. (2019). Independence Problem Solved through Collaboration, Department of Mathematics, MIT."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/23\/3\/270\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T05:28:13Z","timestamp":1760160493000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/23\/3\/270"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,25]]},"references-count":26,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2021,3]]}},"alternative-id":["e23030270"],"URL":"https:\/\/doi.org\/10.3390\/e23030270","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2021,2,25]]}}}