Generalizing Körner's graph entropy to graphons

DOI10.1016/J.EJC.2023.103779MaRDI QIDQ6080368zbMATH OpenOpenAlexFDO

Authors Viktor Harangi, Xueyan Niu, Bo Bai

Publication date 2 October 2023

Published in European Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://arxiv.org/abs/2208.14899

zbMATH Keywords

minimal code ratevertex-packing polytope

Mathematics Subject Classification ID

Graph theory (05C99) Information theory (general) (94A15) Measures of information, entropy (94A17) Source coding (94A29)

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.

Recommendations

• The entropy of random-free graphons and properties
• Perfect graphs and graph entropy: An updated survey
• Independent sets, cliques, and colorings in graphons
• scientific article; zbMATH DE number 780788
• Graphs that Split Entropies

Cites work

• \(\Sigma\Pi\Sigma\) threshold formulas
• Entropy and sorting.
• Entropy splitting for antiblocking corners and perfect graphs
• Graphons, cut norm and distance, couplings and rearrangements
• scientific article; zbMATH DE number 3896009 (Why is no real title available?)
• scientific article; zbMATH DE number 3468645 (Why is no real title available?)
• scientific article; zbMATH DE number 780788 (Why is no real title available?)
• Independent sets, cliques, and colorings in graphons
• Large networks and graph limits
• New bounds for perfect hashing via information theory
• Perfect graphs and graph entropy: An updated survey
• The entropy of random-free graphons and properties
• The fractional chromatic number of infinite graphs

Cited in

(2)

• Independent sets, cliques, and colorings in graphons
• The entropy of random-free graphons and properties

This page was built for publication: Generalizing Körner's graph entropy to graphons

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6080368)