{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,8,21]],"date-time":"2023-08-21T04:45:43Z","timestamp":1692593143088},"reference-count":44,"publisher":"Wiley","issue":"2","license":[{"start":{"date-parts":[[2022,9,5]],"date-time":"2022-09-05T00:00:00Z","timestamp":1662336000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"funder":[{"DOI":"10.13039\/100010663","name":"European Research Council","doi-asserted-by":"publisher","award":["617747"],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Random Struct Algorithms"],"published-print":{"date-parts":[[2023,3]]},"abstract":"Abstract<\/jats:title>We study a class of determinant inequalities that are closely related to Sidorenko's famous conjecture (also conjectured by Erd\u0151s 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 homogeneous if the marginal distributions on the edges are all identical. We show that if is bipartite, then the differential entropy of any homogeneous GMRF on is at least times the edge entropy plus times the point entropy. We also show that in the case of non\u2010negative correlation on edges, the result holds for an arbitrary graph . 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.<\/jats:p>","DOI":"10.1002\/rsa.21112","type":"journal-article","created":{"date-parts":[[2022,9,5]],"date-time":"2022-09-05T12:35:26Z","timestamp":1662381326000},"page":"335-375","update-policy":"http:\/\/dx.doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On Sidorenko's conjecture for determinants and Gaussian Markov random fields"],"prefix":"10.1002","volume":"62","author":[{"given":"P\u00e9ter","family":"Csikv\u00e1ri","sequence":"first","affiliation":[{"name":"Alfr\u00e9d R\u00e9nyi Institute of Mathematics Budapest Hungary"},{"name":"Department of Computer Science, Institute of Mathematics E\u00f6tv\u00f6s Lor\u00e1nd University Budapest Hungary"}]},{"given":"Bal\u00e1zs","family":"Szegedy","sequence":"additional","affiliation":[{"name":"Alfr\u00e9d R\u00e9nyi Institute of Mathematics Budapest Hungary"}]}],"member":"311","published-online":{"date-parts":[[2022,9,5]]},"reference":[{"key":"e_1_2_15_2_1","article-title":"The real positive definite completion problem: Cycle completability","volume":"584","author":"Barrett W.","year":"1996","journal-title":"Memoirs Am. Math. Soc."},{"key":"e_1_2_15_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(93)90234-F"},{"key":"e_1_2_15_4_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129167X92000357"},{"key":"e_1_2_15_5_1","unstructured":"I.BenjaminiandY.Peres A correlation inequality for tree\u2010indexed Markov chains Seminar Stoch. Processes Proc. Semin. Los Angeles\/CA 1991."},{"key":"e_1_2_15_6_1","first-page":"1244","article-title":"A H\u00f6lder type inequality for symmetric matrices with nonnegative entries","volume":"16","author":"Blakley G. R.","year":"1965","journal-title":"Proc. Am. Math. Soc."},{"key":"e_1_2_15_7_1","first-page":"49","article-title":"Probability inequalities for the multivariate normal with nonnegative partial correlations","volume":"9","author":"B\u00f8lviken E.","year":"1982","journal-title":"Scand. J. Stat."},{"key":"e_1_2_15_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TASSP.1985.1164641"},{"key":"e_1_2_15_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.67648"},{"key":"e_1_2_15_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-010-0097-0"},{"key":"e_1_2_15_11_1","doi-asserted-by":"publisher","DOI":"10.2307\/2528966"},{"key":"e_1_2_15_12_1","doi-asserted-by":"crossref","unstructured":"J.Ding J. R.Lee andY.Peres Cover times blanket times and majorizing measures Proc. 43rd Annu. ACM Sympos. Theory Comput. 2011 pp. 61\u201370.","DOI":"10.1145\/1993636.1993646"},{"key":"e_1_2_15_13_1","volume-title":"Statistical distributions","author":"Forbes C.","year":"2011"},{"key":"e_1_2_15_14_1","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/063\/07"},{"key":"e_1_2_15_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-0163-9"},{"key":"e_1_2_15_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(84)90207-6"},{"key":"e_1_2_15_17_1","doi-asserted-by":"publisher","DOI":"10.2969\/aspm\/01510211"},{"key":"e_1_2_15_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-010-0005-1"},{"key":"e_1_2_15_19_1","volume-title":"Matrix analysis","author":"Horn R. A.","year":"2013"},{"key":"e_1_2_15_20_1","volume-title":"Topics in matrix analysis","author":"Horn R. A.","year":"1994"},{"key":"e_1_2_15_21_1","doi-asserted-by":"publisher","DOI":"10.2969\/jmsj\/01830219"},{"key":"e_1_2_15_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0047-259X(80)90065-2"},{"key":"e_1_2_15_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(83)80027-5"},{"key":"e_1_2_15_24_1","doi-asserted-by":"publisher","DOI":"10.1090\/tran\/6487"},{"key":"e_1_2_15_25_1","article-title":"The sandwich theorem","volume":"1","author":"Knuth D. E.","year":"1994","journal-title":"Electron. J. Comb."},{"key":"e_1_2_15_26_1","first-page":"7","article-title":"Zeta functions of finite graphs","volume":"7","author":"Kotani M.","year":"2000","journal-title":"J. Math. Sci. Univ. Tokyo"},{"key":"e_1_2_15_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(95)00741-5"},{"key":"e_1_2_15_28_1","unstructured":"S. L.Lauritzen Clarendon Press England 1996."},{"key":"e_1_2_15_29_1","doi-asserted-by":"publisher","DOI":"10.1214\/17-AOS1668"},{"key":"e_1_2_15_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1979.1055985"},{"key":"e_1_2_15_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2006.05.002"},{"key":"e_1_2_15_32_1","article-title":"Subgraph densities in signed graphons and the local Simonovits\u2010Sidorenko conjecture","volume":"18","author":"Lov\u00e1sz L.","year":"2011","journal-title":"Electron. J. Comb."},{"key":"e_1_2_15_33_1","unstructured":"X.LiandB.Szegedy On the logarithmic calculus and Sidorenko's conjecture to appear."},{"key":"e_1_2_15_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/0047-259X(88)90040-1"},{"key":"e_1_2_15_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(83)80045-6"},{"key":"e_1_2_15_36_1","doi-asserted-by":"publisher","DOI":"10.1201\/9780203492024"},{"key":"e_1_2_15_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02988307"},{"key":"e_1_2_15_38_1","first-page":"419","volume-title":"Progress in graph theory (Waterloo, Ont., 1982)","author":"Simonovits M.","year":"1984"},{"key":"e_1_2_15_39_1","doi-asserted-by":"publisher","DOI":"10.1214\/11-AOS957"},{"key":"e_1_2_15_40_1","unstructured":"C.Uhler Gaussian graphical models: An algebraic and geometric perspective. arXiv preprint arXiv:1707.04345."},{"key":"e_1_2_15_41_1","doi-asserted-by":"publisher","DOI":"10.1006\/aima.1996.0050"},{"key":"e_1_2_15_42_1","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176349846"},{"key":"e_1_2_15_43_1","unstructured":"B.Szegedy Sparse graph limits entropy maximization and transitive graphs. arXiv preprint arXiv:1504.00858."},{"key":"e_1_2_15_44_1","unstructured":"B.Szegedy An information theoretic approach to Sidorenko's conjecturearXiv preprint arXiv:1406.6738."},{"key":"e_1_2_15_45_1","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/20A.1-2.32"}],"container-title":["Random Structures & Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/rsa.21112","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/full-xml\/10.1002\/rsa.21112","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/rsa.21112","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,21]],"date-time":"2023-08-21T02:34:23Z","timestamp":1692585263000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/rsa.21112"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,5]]},"references-count":44,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,3]]}},"alternative-id":["10.1002\/rsa.21112"],"URL":"https:\/\/doi.org\/10.1002\/rsa.21112","archive":["Portico"],"relation":{},"ISSN":["1042-9832","1098-2418"],"issn-type":[{"value":"1042-9832","type":"print"},{"value":"1098-2418","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,9,5]]},"assertion":[{"value":"2019-11-29","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-09-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}