{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,24]],"date-time":"2025-10-24T08:27:40Z","timestamp":1761294460697,"version":"build-2065373602"},"reference-count":41,"publisher":"MDPI AG","issue":"5","license":[{"start":{"date-parts":[[2022,4,25]],"date-time":"2022-04-25T00:00:00Z","timestamp":1650844800000},"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>The present paper offers, in its first part, a unified approach for the derivation of families of inequalities for set functions which satisfy sub\/supermodularity properties. It applies this approach for the derivation of information inequalities with Shannon information measures. Connections of the considered approach to a generalized version of Shearer\u2019s lemma, and other related results in the literature are considered. Some of the derived information inequalities are new, and also known results (such as a generalized version of Han\u2019s inequality) are reproduced in a simple and unified way. In its second part, this paper applies the generalized Han\u2019s inequality to analyze a problem in extremal graph theory. This problem is motivated and analyzed from the perspective of information theory, and the analysis leads to generalized and refined bounds. The two parts of this paper are meant to be independently accessible to the reader.<\/jats:p>","DOI":"10.3390\/e24050597","type":"journal-article","created":{"date-parts":[[2022,4,25]],"date-time":"2022-04-25T21:16:28Z","timestamp":1650921388000},"page":"597","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Information Inequalities via Submodularity and a Problem in Extremal Graph Theory"],"prefix":"10.3390","volume":"24","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5681-1273","authenticated-orcid":false,"given":"Igal","family":"Sason","sequence":"first","affiliation":[{"name":"Andrew & Erna Viterbi Faculty of Electrical and Computer Engineering, Technion-Israel Institute of Technology, Haifa 3200003, Israel"},{"name":"Faculty of Mathematics, Technion-Israel Institute of Technology, Haifa 3200003, Israel"}]}],"member":"1968","published-online":{"date-parts":[[2022,4,25]]},"reference":[{"key":"ref_1","unstructured":"Cover, T.M., and Thomas, J.A. (2006). Elements of Information Theory, John Wiley & Sons. [2nd ed.]."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1501","DOI":"10.1109\/18.104312","article-title":"Information theoretic inequalities","volume":"37","author":"Dembo","year":"1991","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"379","DOI":"10.3390\/e13020379","article-title":"Recent progresses in characterising information inequalities","volume":"13","author":"Chan","year":"2011","journal-title":"Entropy"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"599","DOI":"10.1109\/TIT.2015.2500232","article-title":"Secret sharing, rank inequalities, and information inequalities","volume":"62","author":"Martin","year":"2016","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_5","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_6","doi-asserted-by":"crossref","unstructured":"Boucheron, S., Lugosi, G., and Massart, P. (2013). Concentration Inequalities - A Nonasymptotic Theory of Independence, Oxford University Press.","DOI":"10.1093\/acprof:oso\/9780199535255.001.0001"},{"key":"ref_7","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_8","first-page":"241","article-title":"On two problems of information theory","volume":"8","author":"Erdos","year":"1963","journal-title":"Publ. Math. Inst. Hung. Acad. Sci."},{"key":"ref_9","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_10","doi-asserted-by":"crossref","unstructured":"Jukna, S. (2011). Extremal Combinatorics with Applications in Computer Science, Springer. [2nd ed.].","DOI":"10.1007\/978-3-642-17364-6"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"3610","DOI":"10.1109\/TIT.2018.2806486","article-title":"A conditional information inequality and its combinatorial applications","volume":"64","author":"Kaced","year":"2018","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_12","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. Comput."},{"key":"ref_13","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_14","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1002\/rsa.20385","article-title":"Entropy and set cardinality inequalities for partition-determined functions","volume":"40","author":"Madiman","year":"2012","journal-title":"Random Struct. Algorithms"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Madiman, M., Marcus, A.W., and Tetali, P. (2010, January 6\u20138). Information\u2013theoretic inequalities in additive combinatorics. Proceedings of the 2010 IEEE Information Theory Workshop, Cairo, Egypt.","DOI":"10.1109\/ITWKSPS.2010.5503129"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/0097-3165(77)90083-8","article-title":"An information\u2013theoretic method in combinatorial theory","volume":"23","author":"Pippenger","year":"1977","journal-title":"J. Comb. 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. Computational Mathematics, Modelling and Algorithms, Narosa Publishers."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Sason, I. (2021). A generalized information\u2013theoretic approach for bounding the number of independent sets in bipartite graphs. Entropy, 23.","DOI":"10.3390\/e23030270"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Sason, I. (2021, January 12\u201320). Entropy-based proofs of combinatorial results on bipartite graphs. Proceedings of the 2021 IEEE International Symposium on Information Theory, Melbourne, Australia.","DOI":"10.1109\/ISIT45174.2021.9518068"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"2699","DOI":"10.1109\/TIT.2010.2046253","article-title":"Information inequalities for joint distributions, interpretations and applications","volume":"56","author":"Madiman","year":"2010","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1561\/2200000039","article-title":"Learning with submodular functions: A convex optimization perspective","volume":"6","author":"Bach","year":"2013","journal-title":"Found. Trends Mach. Learn."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Chen, Q., Cheng, M., and Bai, B. (2021). Matroidal entropy functions: A quartet of theories of information, matroid, design and coding. Entropy, 23.","DOI":"10.3390\/e23030323"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/S0019-9958(78)91063-X","article-title":"Polymatroidal dependence structure of a set of random variables","volume":"39","author":"Fujishige","year":"1978","journal-title":"Inf. Control."},{"key":"ref_26","unstructured":"Fujishige, S. (2005). Submodular Functions and Optimization, Elsevier. [2nd ed.]."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"752","DOI":"10.1109\/TIT.2021.3123944","article-title":"Generalized submodular information measures: Theoretical properties, examples, optimization algorithms, and applications","volume":"68","author":"Iyer","year":"2022","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_28","unstructured":"Krause, A., and Guestrin, C. (2005, January 26\u201329). Near-optimal nonmyopic value of information in graphical models. Proceedings of the Twenty-First Conference on Uncertainty in Artificial Intelligence (UAI 2005), Edinburgh, UK."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Bachem, A., Korte, B., and Grotschel, M. (1983). Submodular functions and convexity. Mathematical Programming The State of the Art, Springer.","DOI":"10.1007\/978-3-642-68874-4"},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Tian, C. (August, January 31). Inequalities for entropies of sets of subsets of random variables. Proceedings of the 2011 IEEE International Symposium on Information Theory, Saint Petersburg, Russia.","DOI":"10.1109\/ISIT.2011.6033893"},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Kishi, Y., Ochiumi, N., and Yanagida, M. (July, January 30). Entropy inequalities for sums over several subsets and their applications to average entropy. Proceedings of the 2014 IEEE International Symposium on Information Theory (ISIT 2014), Honolulu, HI, USA.","DOI":"10.1109\/ISIT.2014.6875349"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1002\/j.1538-7305.1948.tb01338.x","article-title":"A Mathematical Theory of Communication","volume":"27","author":"Shannon","year":"1948","journal-title":"Bell Syst. Tech. J."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1007\/978-1-4939-7005-6_14","article-title":"Forward and reverse entropy power inequalities in convex geometry","volume":"Volume 161","author":"Carlen","year":"2017","journal-title":"Convexity and Concentration"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/S0019-9958(78)90275-9","article-title":"Nonnegative entropy measures of multivariate symmetric correlations","volume":"36","author":"Han","year":"1978","journal-title":"Inf. Control."},{"key":"ref_35","unstructured":"Polyanskiy, Y., and Wu, Y. (2019, May 15). Lecture Notes on Information Theory, version 5. Available online: http:\/\/people.lids.mit.edu\/yp\/homepage\/data\/itlectures_v5.pdf."},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Bollob\u00e1s, B. (1978). Extremal Graph Theory, Academic Press.","DOI":"10.1007\/978-1-4612-9967-7"},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Madiman, M. (2008, January 5\u20139). On the entropy of sums. Proceedings of the 2008 IEEE Information Theory Workshop, Porto, Portugal.","DOI":"10.1109\/ITW.2008.4578674"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"603","DOI":"10.1017\/S0963548309990642","article-title":"Sumset and inverse sumset theory for Shannon entropy","volume":"19","author":"Tao","year":"2010","journal-title":"Comb. Comput."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"4503","DOI":"10.1109\/TIT.2014.2322861","article-title":"Sumset and inverse sumset inequalities for differential entropy and mutual information","volume":"60","author":"Kontoyiannis","year":"2014","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_40","first-page":"975","article-title":"Solution of Shannon\u2019s problem on the monotonicity of entropy","volume":"17","author":"Artstein","year":"2004","journal-title":"J. Am. Soc."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"2317","DOI":"10.1109\/TIT.2007.899484","article-title":"Generalized entropy power inequalities and monotonicity properties of information","volume":"53","author":"Madiman","year":"2007","journal-title":"IEEE Trans. Inf. Theory"}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/24\/5\/597\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T23:00:26Z","timestamp":1760137226000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/24\/5\/597"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4,25]]},"references-count":41,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2022,5]]}},"alternative-id":["e24050597"],"URL":"https:\/\/doi.org\/10.3390\/e24050597","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2022,4,25]]}}}