论文标题
一种通用的信息理论方法，用于界定双方图中的独立集数量
A Generalized Information-Theoretic Approach for Bounding the Number of Independent Sets in Bipartite Graphs
论文作者
论文摘要
本文研究了图表中独立集数量的上限的问题，该集合以其度分布表示。对于两分的常规图，Kahn（2001）使用信息理论方法建立了一个紧密的上限，他还猜想了一个上限用于一般图。 Sah等人最近证明了他的猜想界限。 （2019年），使用不涉及信息理论的不同技术。这项工作的主要贡献是Kahn的信息理论证明技术的扩展，以处理不规则的两分图。特别是，当两部分图在一侧是规则的，但另一侧可能是不规则的时，基于熵的证明技术会产生与Kahn（2001）猜想的相同结合，并由Sah等人证明。 （2019）。
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 it may be irregular in the other, the extended entropy-based proof technique yields the same bound that was conjectured by Kahn (2001) and proved by Sah et al. (2019).
