Cargando…
A Generalized Information-Theoretic Approach for Bounding the Number of Independent Sets in Bipartite Graphs
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 gen...
Autor principal: | |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
MDPI
2021
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7996360/ https://www.ncbi.nlm.nih.gov/pubmed/33668754 http://dx.doi.org/10.3390/e23030270 |
_version_ | 1783670099690913792 |
---|---|
author | Sason, Igal |
author_facet | Sason, Igal |
author_sort | Sason, Igal |
collection | PubMed |
description | 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’s 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). |
format | Online Article Text |
id | pubmed-7996360 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2021 |
publisher | MDPI |
record_format | MEDLINE/PubMed |
spelling | pubmed-79963602021-03-27 A Generalized Information-Theoretic Approach for Bounding the Number of Independent Sets in Bipartite Graphs Sason, Igal Entropy (Basel) Article 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’s 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). MDPI 2021-02-25 /pmc/articles/PMC7996360/ /pubmed/33668754 http://dx.doi.org/10.3390/e23030270 Text en © 2021 by the author. https://creativecommons.org/licenses/by/4.0/Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/ (https://creativecommons.org/licenses/by/4.0/) ). |
spellingShingle | Article Sason, Igal A Generalized Information-Theoretic Approach for Bounding the Number of Independent Sets in Bipartite Graphs |
title | A Generalized Information-Theoretic Approach for Bounding the Number of Independent Sets in Bipartite Graphs |
title_full | A Generalized Information-Theoretic Approach for Bounding the Number of Independent Sets in Bipartite Graphs |
title_fullStr | A Generalized Information-Theoretic Approach for Bounding the Number of Independent Sets in Bipartite Graphs |
title_full_unstemmed | A Generalized Information-Theoretic Approach for Bounding the Number of Independent Sets in Bipartite Graphs |
title_short | A Generalized Information-Theoretic Approach for Bounding the Number of Independent Sets in Bipartite Graphs |
title_sort | generalized information-theoretic approach for bounding the number of independent sets in bipartite graphs |
topic | Article |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7996360/ https://www.ncbi.nlm.nih.gov/pubmed/33668754 http://dx.doi.org/10.3390/e23030270 |
work_keys_str_mv | AT sasonigal ageneralizedinformationtheoreticapproachforboundingthenumberofindependentsetsinbipartitegraphs AT sasonigal generalizedinformationtheoreticapproachforboundingthenumberofindependentsetsinbipartitegraphs |