On Sidorenko's conjecture for determinants and Gaussian Markov random fields. Issue 2 (5th September 2022)

• Record Type: Journal Article
• Authors: Csikvári, Péter; Szegedy, Balázs
• Is Part Of: Random structures & algorithms. Volume 62:Issue 2(2023)
• Page Start: 335
• Page End: 375
• Publication Date: 2022-09-05
• Subjects: Gaussian random Markov field -- graph homomorphisms -- positive definite matrix; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.21112
• Languages: English
• ISSNs: 1042-9832

Abstract

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.