{"entities":{"Q510305":{"pageid":512072,"ns":120,"title":"Item:Q510305","lastrevid":62415699,"modified":"2026-04-11T05:55:40Z","type":"item","id":"Q510305","labels":{"en":{"language":"en","value":"Sidorenko's conjecture, colorings and independent sets"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6686255"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q510305$0FFF679C-7F3D-4041-82D7-D0E863354ED9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"379203cb05913aa48ef3152b53204ee3f0fbb2fd","datavalue":{"value":{"text":"Sidorenko's conjecture, colorings and independent sets","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q510305$B748D5F0-97F2-4A54-9E29-7EF7F5BD3149","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2186dc00114765abe3345984f5e77f0ec6805cd8","datavalue":{"value":"1355.05105","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q510305$E3D5F1C6-12AF-4E97-ADF1-065A6FB7C14A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3ba32d32bb779f623048f513cf2e42c655f233b9","datavalue":{"value":{"entity-type":"item","numeric-id":412252,"id":"Q412252"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q510305$0041437D-89AA-468E-AA04-1AAC33186852","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2f3eca0f02d026e6e1fc9bfe37fe5b2571a93125","datavalue":{"value":{"entity-type":"item","numeric-id":311508,"id":"Q311508"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q510305$C6D087AE-9594-417F-AA17-D76DFC6CDF78","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q510305$710D3EAF-AB1E-47C9-80BB-41A584CE8542","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3a051f678ce9f4f7380cf2de9c6018ea50fabc5c","datavalue":{"value":{"time":"+2017-02-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q510305$8868EE9A-385A-424A-B401-FB65D2BF592A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"100a6b478332b4ef49464be09ef3acd8e76acb4a","datavalue":{"value":"https://arxiv.org/abs/1603.05888","type":"string"},"datatype":"url"},"type":"statement","id":"Q510305$2B758789-EE84-4D42-8B75-D9237BCF6974","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"c82e60560808c2f8ad8c5d55f41a8527e7bbdaf1","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p2","type":"string"},"datatype":"url"},"type":"statement","id":"Q510305$201D7257-CC43-4765-A545-7C3D053DC2B3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"007fa08e8cf130634a26e9bab2ffcc3b365508fc","datavalue":{"value":"Summary: Let \\(\\hom(H,G)\\) denote the number of homomorphisms from a graph \\(H\\) to a graph \\(G\\). Sidorenko's conjecture asserts that for any bipartite graph \\(H\\), and a graph \\(G\\) we have  \\[ \\hom(H,G)\\geqslant v(G)^{v(H)}\\left(\\frac{\\hom(K_2,G)}{v(G)^2}\\right)^{e(H)}, \\]  where \\(v(H),v(G)\\) and \\(e(H),e(G)\\) denote the number of vertices and edges of the graph \\(H\\) and \\(G\\), respectively.~In this paper we prove Sidorenko's conjecture for certain special graphs \\(G\\): for the complete graph \\(K_q\\) on \\(q\\) vertices, for a \\(K_2\\) with a loop added at one of the end vertices, and for a path on \\(3\\) vertices with a loop added at each vertex. These cases correspond to counting colorings, independent sets and Widom-Rowlinson colorings of a graph \\(H\\). For instance, for a bipartite graph \\(H\\) the number of \\(q\\)-colorings \\(\\mathrm{ch}(H,q)\\) satisfies  \\[ \\mathrm{ch}(H,q)\\geq q^{v(H)}\\left(\\frac{q-1}{q}\\right)^{e(H)}. \\]  In fact, we will prove that in the last two cases (independent sets and Widom-Rowlinson colorings) the graph \\(H\\) does not need to be bipartite. In all cases, we first prove a certain correlation inequality which implies Sidorenko's conjecture in a stronger form.","type":"string"},"datatype":"string"},"type":"statement","id":"Q510305$6E643110-8237-4D5C-89BC-7573C454C595","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q510305$7D83A7C4-95CD-4C9B-9F5A-6DF6045BA3EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q510305$236D599F-EE68-4024-A412-3861579B5823","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"05389b96c23a6695eab15a0aefa0b53f97715490","datavalue":{"value":"6686255","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q510305$775BFA01-2A4D-4C95-B1E6-1AAA75F75A96","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"245bb46b54951018ca725c73286f7f519e3b12ac","datavalue":{"value":"colorings","type":"string"},"datatype":"string"},"type":"statement","id":"Q510305$A4492356-16F0-4D3C-90F2-ED8E13D39CDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9890d2d31de82fcf86b74b799289b36efeaabea2","datavalue":{"value":"independent sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q510305$B98A0CF0-82C7-4501-A9F5-15690D66F4DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4d9ebd4d20748ad48203d24278b31695246412e9","datavalue":{"value":"large girth graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q510305$9C4610F8-79FC-4E48-BDE3-DB1BD5274E9E","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q510305$8858DA35-B8A7-41DB-BE4C-664DB0A2746A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"5c9b5137d7413c95363c18066c493c39ec0f128e","datavalue":{"value":{"entity-type":"item","numeric-id":313432,"id":"Q313432"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q510305$89F12DA1-83BE-45ED-A949-98B625008D92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20498c21b4e98cb0f3bf8d71c64f46b728abd9fc","datavalue":{"value":{"entity-type":"item","numeric-id":3581598,"id":"Q3581598"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q510305$AA6834C5-6212-4A59-B5A4-404FFD8922B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f56760be6c8faf06365155dda708fd0d045f4962","datavalue":{"value":{"entity-type":"item","numeric-id":5517742,"id":"Q5517742"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q510305$C3E7F3CA-2468-4F96-A30D-A4ABAB235E61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6194e14d6c050a27f97b474f4243de632f8b4a89","datavalue":{"value":{"entity-type":"item","numeric-id":1809678,"id":"Q1809678"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q510305$C68D0C35-822B-4737-A9EE-782021331F48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"819a38718d27840893f6fa7c6e8ab2a0c83e7535","datavalue":{"value":{"entity-type":"item","numeric-id":5366940,"id":"Q5366940"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q510305$EDD2BDBF-0924-4966-8142-F7099EB720B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6851dcc32090425cf81c7a794b91c3259e433628","datavalue":{"value":{"entity-type":"item","numeric-id":727170,"id":"Q727170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q510305$30AC9B3B-6A9F-436A-94CD-5D618F87A989","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b6e479cef98cd0dc2664d39e15bc30cc76e9c22","datavalue":{"value":{"entity-type":"item","numeric-id":616156,"id":"Q616156"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q510305$FC42AB7D-5635-4C62-9ABE-A900C690A304","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7edb30168fa0e4eae80a3dd65959ae51d8d35826","datavalue":{"value":{"entity-type":"item","numeric-id":4646248,"id":"Q4646248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q510305$BB8016FC-4BE1-4DA0-97A8-4F4609347CFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"96fb9da37ba4e8c65688c646ed0fec8b9e7cac0d","datavalue":{"value":{"entity-type":"item","numeric-id":382272,"id":"Q382272"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q510305$795AAB63-3851-409B-9D22-769A8822E0ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bf42effaa99703dbd576ff415e18804d7c5442a8","datavalue":{"value":{"entity-type":"item","numeric-id":2852613,"id":"Q2852613"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q510305$ED4DE88C-07DC-4C79-95C7-1CFE4AB7A1DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f0cf77af371445c4022c8a951e5fc07a382d8eb4","datavalue":{"value":{"entity-type":"item","numeric-id":463048,"id":"Q463048"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q510305$78909FD2-D5BB-4104-88E5-DF1648F687ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c42399b7fac0541e4112b6e670bf60bcb3a44c8","datavalue":{"value":{"entity-type":"item","numeric-id":5199417,"id":"Q5199417"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q510305$0AB6BB8C-4746-495C-9D87-7EB6A1685685","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b985a626d3f8dceba9a158d188f71927dbb5e609","datavalue":{"value":{"entity-type":"item","numeric-id":3512601,"id":"Q3512601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q510305$46D08B2D-B4B6-4D15-9C7D-EAE523E84E95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b0c1daddb79315c935d13d5f9fab4b18a27c5dd4","datavalue":{"value":{"entity-type":"item","numeric-id":5962247,"id":"Q5962247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q510305$F04B22D6-755D-4750-9BA0-AFA0F9EE608D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f0c1d9b54e67001b91d5654b94b0879e024db749","datavalue":{"value":{"entity-type":"item","numeric-id":2790648,"id":"Q2790648"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q510305$5232B0E4-9FEE-4749-86F9-6FE6E514C386","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ec582542a47076e93e672d1e45574526ad529d86","datavalue":{"value":{"entity-type":"item","numeric-id":2521557,"id":"Q2521557"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q510305$48221329-CF53-474D-AF29-148663228AF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed8e4dcb8b77d6df17f554bf6f1d8f3441b0a375","datavalue":{"value":{"entity-type":"item","numeric-id":547787,"id":"Q547787"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q510305$9F4D7976-6C5E-40EB-B5E6-FD3435A2F949","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0024b1b312c18e9ff551ab9a54c7ab698137f372","datavalue":{"value":{"entity-type":"item","numeric-id":3931424,"id":"Q3931424"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q510305$F3CCE1FB-7D8D-41B6-8E8F-30F67864C32F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a74ae225fc555eb81f4e5c170f572b8459f594fd","datavalue":{"value":{"entity-type":"item","numeric-id":3363325,"id":"Q3363325"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q510305$6BEC3884-1111-4E19-89FF-3B4E82C69ACD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1758d7b3bd2c41aa3b42e01008f4d1d8dae2d14d","datavalue":{"value":{"entity-type":"item","numeric-id":2366960,"id":"Q2366960"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q510305$513EF4E9-BAC5-4305-801D-E19AEEC6A99B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"63035f667bb83d7376e59d7cfe44a458da98f97d","datavalue":{"value":{"entity-type":"item","numeric-id":2722657,"id":"Q2722657"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q510305$3DE55384-DCFE-4A11-BE60-E11A18437B0F","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"40aafacc06d612eb7d10a5562ab3b0ac19348945","datavalue":{"value":"bafkreifp3k6dyyzgb5ywa4jvtwkeogdb43vxxomxwg4gpgicb62zfn5sxq","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q510305$42B3CA47-6ADF-445D-888E-4BF480BB14AA","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"60d2bba99bd76c94f69961270daf536eeb95f119","datavalue":{"value":{"entity-type":"item","numeric-id":4646248,"id":"Q4646248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"16b6a0f77030a5c9cde4fa12b59ea1665cc3588c","datavalue":{"value":{"amount":"+0.8452891707420349","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q510305$8BE1BFCA-D1CC-4127-A045-EA02C7D1875B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7137d3ef3e7aa9f278f793f33c29563c4c20b3fc","datavalue":{"value":{"entity-type":"item","numeric-id":2790648,"id":"Q2790648"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"014eac1464f1a607701bd9fffeb52052d247c68a","datavalue":{"value":{"amount":"+0.8366026282310486","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q510305$06B8C9DC-0E65-4D6D-8E1F-89ACCFC6CD45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"99d67bb3b0ecf26298d64729827351703b088ae1","datavalue":{"value":{"entity-type":"item","numeric-id":616156,"id":"Q616156"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"376b41115d5f39e595de7c0c0c283b8a0bf409dd","datavalue":{"value":{"amount":"+0.813146710395813","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q510305$2C00F2E2-F073-4BB7-8093-E3F9B8656313","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"49c72e88b78714f86c3383fa45d96c4cb71b069a","datavalue":{"value":{"entity-type":"item","numeric-id":5962247,"id":"Q5962247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cecd11bd5559d4ff26c4b2ebac9a1920599bf8b8","datavalue":{"value":{"amount":"+0.81153804063797","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q510305$9D01A185-1436-4EB5-85E1-3C6A91AFCA3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2575b17a5d45f5c07cdf3a0e70f2191976c4b2e6","datavalue":{"value":{"entity-type":"item","numeric-id":3382237,"id":"Q3382237"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d6da44df94df7d798d4417eebd1aff302d096cd4","datavalue":{"value":{"amount":"+0.8055340647697449","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q510305$FB97E74D-729F-45F7-8877-2D3A6661F27E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Sidorenko's conjecture, colorings and independent sets","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Sidorenko%27s_conjecture,_colorings_and_independent_sets"}}}}}