2018/01/25 by Csikvári, Péter, Szegedy, Balázs
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1801.08425
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 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 homogeneous if the marginal distributions on the edges are all identical. We show that if G is bipartite 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 show that in the case of non-negative correlation on edges, the result holds for an arbitrary graph 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. Connection with Ihara zeta function and the number of spanning trees is also discussed.