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

DOI10.1002/RSA.21112MaRDI QIDQ6074867zbMATH OpenWikidataFDO

Authors Péter Csikvári, Balázs Szegedy

Publication date 19 October 2023

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1801.08425, http://real.mtak.hu/153957/1/1701.03632.pdf

zbMATH Keywords

Gaussian random Markov fieldgraph homomorphismspositive definite matrix

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Other Dirichlet series and zeta functions (11M41) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Abstract: We study a class of determinant inequalities that are closely related to Sidorenko's famous conjecture (Also conjectured by ErdH 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.

Recommendations

• Markov Random Fields, Homomorphism Counting, and Sidorenko’s Conjecture
• Mod-Gaussian convergence for random determinants
• scientific article; zbMATH DE number 3879836
• On the Markov property for certain Gaussian random fields
• Random determinants, mixed volumes of ellipsoids, and zeros of Gaussian random fields
• Gaussian limit for determinantal random point fields.
• Markov properties for Gaussian fields associated with Dirichlet forms
• Determinantal probability measures on Grassmannians
• scientific article; zbMATH DE number 3969788

Cites work

• A correlation inequality for bipartite graphs
• A Holder Type Inequality for Symmetric Matrices with Nonnegative Entries
• An approximate version of Sidorenko's conjecture
• Classes of orderings of measures and related correlation inequalities. I. Multivariate totally positive distributions
• Cover times, blanket times, and majorizing measures
• Gaussian Markov distributions over finite graphs
• Gaussian Markov Random Fields
• Geometry of maximum likelihood estimation in Gaussian graphical models
• Graph norms and Sidorenko's conjecture
• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 3885945 (Why is no real title available?)
• scientific article; zbMATH DE number 4165188 (Why is no real title available?)
• scientific article; zbMATH DE number 3770781 (Why is no real title available?)
• scientific article; zbMATH DE number 125748 (Why is no real title available?)
• scientific article; zbMATH DE number 635657 (Why is no real title available?)
• scientific article; zbMATH DE number 1495995 (Why is no real title available?)
• scientific article; zbMATH DE number 6125590 (Why is no real title available?)
• Limits of dense graph sequences
• M-matrices as covariance matrices of multinormal distributions
• Maximum likelihood estimation in Gaussian models under total positivity
• Multi-dimensional multivariate Gaussian Markov random fields with application to image processing
• On discrete subgroups of the two by two projective linear group over \(p\)-adic fields
• On the Shannon capacity of a graph
• On weighted graph homomorphisms
• Positive definite completions of partial Hermitian matrices
• Spanning trees in regular graphs
• Statistical distributions.
• Subgraph densities in signed graphons and the local Simonovits-Sidorenko conjecture
• THE IHARA-SELBERG ZETA FUNCTION OF A TREE LATTICE
• The real positive definite completion problem for a simple cycle
• The real positive definite completion problem: cycle completability
• The real positive semidefinite completion problem for series-parallel graphs
• The sandwich theorem
• Two approaches to Sidorenko's conjecture
• Zeta functions of finite graphs and coverings

Cited in

(2)

• On the local approach to Sidorenko's conjecture
• Gaussian Markov random fields and totally positive matrices

This page was built for publication: On Sidorenko's conjecture for determinants and Gaussian Markov random fields

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6074867)