{"entities":{"Q1775018":{"pageid":1785760,"ns":120,"title":"Item:Q1775018","lastrevid":48478492,"modified":"2026-01-04T22:57:22Z","type":"item","id":"Q1775018","labels":{"en":{"language":"en","value":"Torpid mixing of the Wang-Swendsen-Koteck\u00fd algorithm for sampling colorings"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2165396"}},"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":"Q1775018$86E8079B-9254-4EBD-A3D4-4DCB228C067A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c543af7abe62ad1cf21cb6d9372269b57d9f7cee","datavalue":{"value":{"text":"Torpid mixing of the Wang-Swendsen-Koteck\u00fd algorithm for sampling colorings","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1775018$66E525DF-4663-4D3C-B6C0-EB56200341C1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"aeae3e207063c676ceb509aba9ccd6387fa89c62","datavalue":{"value":"1089.68135","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1775018$42A0A313-D40D-4AA8-A3CA-7930F2AB63AB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"93a3904bbec182d67e761f38904a81bb2531b67d","datavalue":{"value":{"entity-type":"item","numeric-id":178704,"id":"Q178704"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1775018$6E97FE15-8096-4A8F-BC07-0781A9BD97C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d86f9778a8e93d0b33d1d3ea5f2034f68d5009bd","datavalue":{"value":{"entity-type":"item","numeric-id":269469,"id":"Q269469"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1775018$99304856-9EE6-4510-B059-BA865CF37EA7","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"0a33251796f18919242eb286ef1f888e5d6e79da","datavalue":{"value":{"entity-type":"item","numeric-id":350720,"id":"Q350720"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1775018$F30EC8D3-213C-43EA-976B-002B0A4E4B87","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"87c9e290fe6a50f86e719ce6413845bc3314f33a","datavalue":{"value":{"time":"+2005-05-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1775018$9D4AFA62-7DE6-4F85-BD32-A982BF759782","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e63cd5c61300da2575306c3a1aeb06b68f6abf48","datavalue":{"value":"As in the related paper by \\textit{E. Vigoda} [J.\\ Math.\\ Phys.\\ 41, 1555--1569 (2000; Zbl 0978.60083)] the authors sample uniformly at random from the set of proper vertex \\(k\\)-colourings of a graph. Two algorithms are considered: \\textit{R. J. Glauber} dynamics [J.\\ Math.\\ Phys.\\ 4, 294--307 (1963; Zbl 0145.24003)] and the WSK algorithm introduced by \\textit{Wang, Swendsen} and \\textit{Koteck\u00fd} [Phys.\\ Rev.\\ Lett.\\ 63, 109--112 (1989) and Phys.\\ Rev.\\ B 42, 2465--2474 (1990)]. Such an algorithm is rapidly mixing if the mixing time of the Markov chain is polynomial in the number \\(n\\) of vertices, and torpidly mixing if it is exponential in \\(n^{\\epsilon}\\) for some \\(\\epsilon>0\\). There is an infinite family of 3-colourable planar graphs such that the WSK algorithm is torpidly mixing for every fixed \\(k \\geq 3\\). There is a constant \\(k_0\\) and an infinite family of graphs with maximum degree \\(\\Delta\\) such that the WSK algorithm is not ergodic for every \\(k\\) with \\(k_0 \\leq k \\leq \\Delta/2\\). And there is an infinite family of bipartite graphs with maximum degree \\(\\Delta\\) such that the WSK algorithm is torpidly mixing when \\(3 \\leq k < \\Delta/(20\\log\\Delta)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1775018$AC375112-02F3-4BFC-BA37-05DC5180C875","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e01671c873d801b913451010c0981a684c101d40","datavalue":{"value":"68W20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1775018$FA291369-597D-49BE-BAEF-375861E7294F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1775018$D2968564-8244-4CF3-93F3-85F9BD79773E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4b7275e0d4b526075acce84a242d8537e929bb2d","datavalue":{"value":"60C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1775018$A25EBD4C-0551-446B-A624-ADA2CE56F521","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1cdf15533e26fc0c4c2e22d28e655c364dfe77a6","datavalue":{"value":"60J10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1775018$86F65AA2-210B-44AE-86DF-299F65E793E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6a9ff1a146ff44dca747e334413377c148d2df3d","datavalue":{"value":"60J20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1775018$E23D88E0-AC3F-40BC-A939-EEB5E7316735","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7ddaa80bf0a693a36c1113ff6b7ad576f729940","datavalue":{"value":"68W40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1775018$3DB77699-0019-40E9-89C5-6960F9F14F8F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f2425e4c2f9a797034008d19fb4d3d510ea04457","datavalue":{"value":"2165396","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1775018$ECFCFAAE-7972-4972-9913-404FA3169C00","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f2832e5ae4fc414c772c86f6023e26d563dd35e6","datavalue":{"value":"randomized algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1775018$FB5BBD91-A6C6-4FD9-94E9-778BCF15F0C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"397d9252ef89819a92633d8502b4000f6e56c083","datavalue":{"value":"Markov chain","type":"string"},"datatype":"string"},"type":"statement","id":"Q1775018$919914CB-B849-48F5-9FA7-9872583D7F7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d52aea7ff51ef97ce73bc8495bb71dd754d0b1d3","datavalue":{"value":"Monte Carlo method","type":"string"},"datatype":"string"},"type":"statement","id":"Q1775018$452072D1-594E-41AB-B133-9A12D2AAE96A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b999a30face15aad7449f079f4627b1e5e0eb2bc","datavalue":{"value":"coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1775018$EFB14EEF-5901-4381-9D69-23540F39EA26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"26c80219ca98861a97e9c3a2f1fffbf03990a7b9","datavalue":{"value":"torpid mixing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1775018$8644D4B6-259E-4E4E-A392-36086F983A22","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":"Q1775018$37F1A61F-3818-41AA-9EF1-5487DC256F29","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"15ef6920473f5a066e515a2b69adf7d3571b07e5","datavalue":{"value":"https://doi.org/10.1016/j.jda.2004.05.002","type":"string"},"datatype":"url"},"type":"statement","id":"Q1775018$43B8BC8D-7B09-4CA2-9F26-8A47F1E5F1E7","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"059875423bff4456acb1c49c92527dd0e93af9f4","datavalue":{"value":"W2062105278","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1775018$026C71BD-9D02-40A1-BEF6-0BC9D3AB0A21","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d9e9f865b3e6c71136151f56d4563dfc77b771e4","datavalue":{"value":{"entity-type":"item","numeric-id":4255674,"id":"Q4255674"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1775018$68210FAC-4492-4F51-A871-3B8D547DE02A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"911ece6532e7c5fb36b1f68ff14f865f3253e460","datavalue":{"value":{"entity-type":"item","numeric-id":1308697,"id":"Q1308697"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1775018$0B163F36-2BB5-495E-A18F-FDDAFD6B79B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d9a2995b075c18ad6186d3d9013972914702cc6a","datavalue":{"value":{"entity-type":"item","numeric-id":1964520,"id":"Q1964520"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1775018$30F7C88B-2444-4C82-B1BC-69468F22C0EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"793406e301ed8f755acb1ff74ac8e006c2099f8c","datavalue":{"value":{"entity-type":"item","numeric-id":5522184,"id":"Q5522184"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1775018$71997534-1864-4887-99D6-5E61D695E405","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"28588578bb09af0b4bf0a3281ab6c8d321eb619b","datavalue":{"value":{"entity-type":"item","numeric-id":4519896,"id":"Q4519896"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1775018$A6CCCD62-9F5B-4033-9BEF-78CD8BCDF4C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"07a4b9e3035d903b8626c3066fac7a06ebe016e1","datavalue":{"value":{"entity-type":"item","numeric-id":4852428,"id":"Q4852428"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1775018$DF6EDDBF-679C-4005-97C5-FF27ED7A2717","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0a8ace61553a8d4fdb380c06002e681b85a927d0","datavalue":{"value":{"entity-type":"item","numeric-id":5815557,"id":"Q5815557"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1775018$7BD3D126-73B3-4762-AF3B-5DF52F914C5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a4036ff68c821883acff7fe514aa217343cd5775","datavalue":{"value":{"entity-type":"item","numeric-id":3140234,"id":"Q3140234"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1775018$24DB291A-3405-47F0-A981-BC6D324E2D45","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ee00110fd1d217328cdd63da28229fa0ea3f9df1","datavalue":{"value":"10.1016/J.JDA.2004.05.002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1775018$6183546B-C0FC-4818-B083-FDBCAD387537","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"df3481ca88f43e1b59b83221d2db946ec4164c20","datavalue":{"value":{"entity-type":"item","numeric-id":5387664,"id":"Q5387664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"996106a3631281fa802b39068ff4cdefc9428a6f","datavalue":{"value":{"amount":"+0.804298460483551","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":"Q1775018$17E57D53-AFAE-4879-8696-0E58F27FD684","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"12755e3b46df5bbff612b7b442059e1d1522043b","datavalue":{"value":{"entity-type":"item","numeric-id":4534221,"id":"Q4534221"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"847e822a842b1936dc942c6dfb8af0eba67d70b9","datavalue":{"value":{"amount":"+0.799856424331665","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":"Q1775018$6118D982-6298-4B7A-A9F3-55F11F513DBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4556269b02fcf6875af683ab213bfd9419837e58","datavalue":{"value":{"entity-type":"item","numeric-id":954987,"id":"Q954987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"74c47de2e5e425c97c3a52d0d56e6d75d1d45663","datavalue":{"value":{"amount":"+0.7910284996032715","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":"Q1775018$8C7C1A06-4236-4799-924F-11057BD91B8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aed8d29a42fa8ab6a2430358c7767b3625e02236","datavalue":{"value":{"entity-type":"item","numeric-id":2921767,"id":"Q2921767"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e9461370d14faf260d103e66d19a21d7d6353c14","datavalue":{"value":{"amount":"+0.7888576984405518","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":"Q1775018$E7007C70-53D9-47A3-813B-0B1B3C74DE81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f3f1f78a8f74c07c83e515e7b5fdfd8637a56e76","datavalue":{"value":{"entity-type":"item","numeric-id":4608004,"id":"Q4608004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"50d234d3aebc2ba7b257e976b6c0ad7bedf79fe8","datavalue":{"value":{"amount":"+0.7867634892463684","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":"Q1775018$41798F35-5E68-4824-AB1B-C75C4C86125C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1775018","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1775018"}}}}}