2015/04/03 by Balázs Szegedy, Szegedy, Balazs
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Group Theory (math.GR) #Limits and Structures in Graph Theory #Probability (math.PR)
paper · pdf · doi:10.48550/arxiv.1504.00858
openalex publication_date 2015/04/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper we describe a triple correspondence between graph limits, information theory and group theory. We put forward a new graph limit concept called log-convergence that is closely connected to dense graph limits but its main applications are in the study of sparse graph sequences. We present an information theoretic limit concept for k-tuples of random variables that is based on the entropy maximization problem for joint distributions of random variables where a system of marginal distributions is prescribed. We give a fruitful correspondence between the two limit concepts that has a group theoretic nature. Our applications are in graph theory and information theory. We shows that if H is a bipartite graph, P1 is the edge and t is the homomorphism density function then the supremum of log t(H,G)/log t(P1,G) in the set of all graphs G is the same as in the set of graphs that are both edge and vertex transitive. This result gives a group theoretic approach to Sidorenko's famous conjecture. We obtain information theoretic inequalities regarding the entropy maximization problem. We investigate the limits of sparse random graphs and discuss quasi-randomness in our framework.