Generalizing Körner’s graph entropy to graphons

Harangi, Viktor and Niu, Xueyan and Bai, Bo (2023) Generalizing Körner’s graph entropy to graphons. EUROPEAN JOURNAL OF COMBINATORICS, 114. No-103779. ISSN 0195-6698

Preview

Text Graphon_Entropy.pdf Available under License Creative Commons Attribution Non-commercial No Derivatives. Download (457kB) | Preview

Abstract

K¨orner 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.

Actions (login required)

Edit Item