On Sidorenko's conjecture for determinants and Gaussian Markov random fields. Issue 2 (5th September 2022) - Csikvári, Péter; Szegedy, Balázs
Abstract: We study a class of determinant inequalities that are closely related to Sidorenko's famous conjecture (also conjectured by Erdős and Simonovits in a different form). Our main result can also be interpreted as an entropy inequality for Gaussian Markov random fields (GMRF). We call a GMRF on a finite graph G $$ G $$ homogeneous if the marginal distributions on the edges are all identical. We show that if G $$ G $$ is bipartite, then the differential entropy of any homogeneous GMRF on G $$ G $$ is at least | E ( G ) | $$ \mid E(G)\mid $$ times the edge entropy plus | V ( G ) | − 2 | E ( G ) | $$ \mid V(G)\mid -2\mid E(G)\mid $$ times the point entropy. We also show that in the case of non‐negative correlation on edges, the result holds for an arbitrary graph G $$ G $$ . 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. It is also observed that the system we study exhibits a phase transition on large girth regular graphs. Connection with Ihara zeta function and the number of spanning trees is also discussed.