On Sidorenko's conjecture for determinants and Gaussian Markov random fields

2017/01/13 by Balázs Szegedy, Szegedy, Balazs
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.1701.03632

openalex publication_date 2017/01/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study a class of determinant inequalities that are closely related to Sidorenko's famous conjecture (Also conjectured by Erd\H os and Simonovits in a different form). Our results can also be interpreted as entropy inequalities for Gaussian Markov random fields (GMRF). We call a GMRF on a finite graph G homogeneous if the marginal distributions on the edges are all identical. We show that if G satisfies Sidorenko's conjecture then the differential entropy of any homogeneous GMRF on G is at least |E(G)| times the edge entropy plus |V(G)|-2|E(G)| times the point entropy. We also prove this inequality in a large class of graphs for which Sidorenko's conjecture is not verified including the so-called Möbius ladder: K_5,5∖ C₁₀. The connection between Sidorenko's conjecture and GMRF's is established via a large deviation principle on high dimensional spheres combined with graph limit theory.

Related

• On Sidorenko's conjecture for determinants and Gaussian Markov random fields
• An approximate version of Sidorenko's conjecture
• Sidorenko's conjecture for a class of graphs: an exposition
• Subgraph densities in signed graphons and the local Sidorenko conjecture
• Sparse graph limits, entropy maximization and transitive graphs