论文标题
将Körner的图形熵概括为图形
Generalizing Körner's graph entropy to graphons
论文作者
论文摘要
科尔纳（Körner）在1973年介绍了图形熵的概念，这是自然编码问题的最小代码率，在该字母中，并非所有的字母对都可以在字母中区分。后来，事实证明，它可以表示为在所谓的顶点包装的多层室上的最小化问题的解决方案。 在本文中，我们将此概念推广到图形。我们表明，类似的最小化问题为Graphon熵提供了上限。我们还给出了最大化问题形状的下限。本文的主要结果是，对于大多数图形，这两个边界实际上是重合的，因此精确地确定了所讨论的熵。此外，Graphon熵与分数色数和分数集团数具有良好的连接。
Körner introduced the notion of graph entropy in 1973 as the minimal code rate of a natural coding problem where not all pairs of letters can be distinguished in the alphabet. Later it turned out that it can be expressed as the solution of a minimization problem over the so-called vertex-packing polytope. In this paper we generalize this notion to graphons. We show that the analogous minimization problem provides an upper bound for graphon entropy. We also give a lower bound in the shape of a maximization problem. The main result of the paper is that for most graphons these two bounds actually coincide and hence precisely determine the entropy in question. Furthermore, graphon entropy has a nice connection to the fractional chromatic number and the fractional clique number.
