{"entities":{"Q5961956":{"pageid":8138758,"ns":120,"title":"Item:Q5961956","lastrevid":58631493,"modified":"2026-04-06T02:27:17Z","type":"item","id":"Q5961956","labels":{"en":{"language":"en","value":"Gibbs rapidly samples colorings of \\(G(n, d/n)\\)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5786321"}},"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":"Q5961956$C03B18CC-F9CC-4BC9-BB49-567B31ABFA55","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"11b8193dadbe80355456be5b78c40e05020b4e76","datavalue":{"value":{"text":"Gibbs rapidly samples colorings of \\(G(n, d/n)\\)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5961956$8069A30A-8753-4C4D-8AC0-4806BB6EF684","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2487d58246ba902d5c8b2e64731f44e8286fcda3","datavalue":{"value":"1213.05239","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5961956$34F14EE8-E015-4A78-93CD-F485F56B4C1F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"95e03469b8abf1198e8e71d89e5f9540ea9718d3","datavalue":{"value":{"entity-type":"item","numeric-id":185102,"id":"Q185102"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5961956$77E082E8-E349-4A23-9385-B0A82AA9BB0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7da1c7aaa9c434b0782de58361705d7f238eecc1","datavalue":{"value":{"entity-type":"item","numeric-id":243556,"id":"Q243556"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5961956$F233DABA-5C51-48D8-B3F0-F6EEED2473A1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"baf45dbcb13e63028464b24262c188c8428a543a","datavalue":{"value":{"time":"+2010-09-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5961956$40108B6B-D2B3-4CF6-A537-EAFC2EC06DAE","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5eb9b7dcde2ecd960b12ef37d9d6eac84379cd7d","datavalue":{"value":"https://arxiv.org/abs/0707.3241","type":"string"},"datatype":"url"},"type":"statement","id":"Q5961956$47465CD5-8C1E-435D-917B-E6500BE717A3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"bbd3d15625d7bd04072174e9458bac6d49575449","datavalue":{"value":"The paper studies so-called Gibb's sampling, a popular technique for sampling high dimensional distributions defined on graphs. Of special interest is the behavior of Gibbs sampling on the Erd\u0151s--R\u00e9nyi random graph \\(G(n; d/n)\\), where each edge is chosen independently with probability \\(d/n\\), \\(d\\) is fixed. The authors give the first rapid convergence result of Gibbs samplers for the coloring model on Erd\u0151s--R\u00e9nyi random graphs in terms of the average degree and the number of colors only. These results yield the first fully polynomial randomized approximation scheme for sampling the coloring distribution in this case. Some related works and a sketch of the proof are given in the introduction. The remaining sections give a more detailed proof.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5961956$CB773438-A40E-4CA7-A14C-9B64DF6A0C08","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"0536959cfc4dfc92623370a89bdeee0eb0d487fe","datavalue":{"value":{"entity-type":"item","numeric-id":591057,"id":"Q591057"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5961956$93779711-FA26-4E9E-BDD6-E0AEFF1C6272","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5961956$AAA8C2AB-95E5-4343-A203-1BBD62E47E87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1cdf15533e26fc0c4c2e22d28e655c364dfe77a6","datavalue":{"value":"60J10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5961956$9D1B29BC-8A33-4870-BBDB-6093841EE17A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"63aec181f5f25f527f4a50518ef030353abadcda","datavalue":{"value":"65C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5961956$DB494BCC-F555-4AD0-BE56-7FB52B8CDEB0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a75351ce72d89d1d541e16e6b1a0393748e126c2","datavalue":{"value":"82C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5961956$43ADF74A-10BD-4341-9ACF-70D9896E0747","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ea86d5cfdd8aa7610d6f8c4384c6f2a098efb8de","datavalue":{"value":"5786321","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5961956$B7EDCF1C-5DC9-4141-9557-D6089D361034","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d36600971d479714ab42573e2b1035cc3b978684","datavalue":{"value":"Gibbs sampling","type":"string"},"datatype":"string"},"type":"statement","id":"Q5961956$F92F67CA-B382-43E9-A691-1C075AED06A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"245bb46b54951018ca725c73286f7f519e3b12ac","datavalue":{"value":"colorings","type":"string"},"datatype":"string"},"type":"statement","id":"Q5961956$49A5C459-3CB9-4246-B57C-83388C105038","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"47b1fb05e91c3d99539d61d86454a863295c2777","datavalue":{"value":"polynomial randomized approximation","type":"string"},"datatype":"string"},"type":"statement","id":"Q5961956$E84DD41E-23E2-4C8B-9E26-D38B175266D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3a4b9b217356f9bcb1d945cbe85d613ed1fdbd1a","datavalue":{"value":"Erd\u0151s--R\u00e9nyi random graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q5961956$92C910F0-DC84-4017-B4D7-4398D585F679","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":"Q5961956$DFE6E0EB-213C-478E-83F6-3F2F842C9ADA","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"1d42700191f30c966d01b81c60996bd0bc5c0d4d","datavalue":{"value":"W2113610073","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5961956$296E99F1-57B0-43AE-9AA0-D00F8F1219BB","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"78bd3a7c164c07ad0c9a81b6dff532926f3a9a46","datavalue":{"value":{"entity-type":"item","numeric-id":1780979,"id":"Q1780979"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5961956$B5DA838A-A4EA-47CB-8031-8EC2A5890831","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"31f63930b684171693616c70224f944186516556","datavalue":{"value":{"entity-type":"item","numeric-id":3838650,"id":"Q3838650"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5961956$6E1E96D0-A13E-4FCE-A2C9-9C5942D81357","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4aaf62d8b0dd458e9bc5f818a51a609edac9992f","datavalue":{"value":{"entity-type":"item","numeric-id":3419603,"id":"Q3419603"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5961956$58DD5004-FAA2-4B3A-921E-8584C7F2E66D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"67cb5311574c46b24cdba2766781523eebca97fa","datavalue":{"value":{"entity-type":"item","numeric-id":2852546,"id":"Q2852546"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5961956$0FF1B0B7-D33E-43C9-88A4-34CCA9AAEC1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b4a67cd2071947abe8bf31761a6c202712c13359","datavalue":{"value":{"entity-type":"item","numeric-id":3149880,"id":"Q3149880"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5961956$F682A594-EA52-489D-9696-C32F21720DDC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"734fd873b206ff7f5a87e3d1a77779673a0cd8c6","datavalue":{"value":{"entity-type":"item","numeric-id":4953244,"id":"Q4953244"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5961956$70D2625D-B73F-4AD0-BC86-39C73EFE65E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d3315894380497d70eba936d55f1b82213f5560","datavalue":{"value":{"entity-type":"item","numeric-id":3122905,"id":"Q3122905"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5961956$2B7E6592-EA69-46F6-9AE9-CFE328520535","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f510dc95435ae5bc886b3a1646fe55f24094a286","datavalue":{"value":{"entity-type":"item","numeric-id":4847401,"id":"Q4847401"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5961956$248B5BEF-3314-46D8-B5EE-830FFB8A14B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a998f318405fc477f47b3c0adacc0d1a8f1414c","datavalue":{"value":{"entity-type":"item","numeric-id":3211352,"id":"Q3211352"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5961956$795DE902-E9AF-4892-BC7E-5096EAD7F404","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"efcbeed35653bb79abd91537419405343c057f8f","datavalue":{"value":{"entity-type":"item","numeric-id":3069905,"id":"Q3069905"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5961956$E37D1965-FF77-408B-B505-EDAEE3DEACCD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b9667861398fa1cc73befa176d9aad2283318058","datavalue":{"value":{"entity-type":"item","numeric-id":4941948,"id":"Q4941948"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5961956$C33FCC71-A9D6-433E-A401-BD4803117E24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"26f797391d14db956e9f73504db20878678ca587","datavalue":{"value":{"entity-type":"item","numeric-id":3579472,"id":"Q3579472"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5961956$FA37FD71-21A4-4271-AACB-8F39F1F30379","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bf6e355580b0a243a890742adaf4cd81f269ea1c","datavalue":{"value":{"entity-type":"item","numeric-id":3055775,"id":"Q3055775"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5961956$39A35A15-CE5C-4CF9-AB95-8A8B291083B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3b777c1c0d3ab3beecc00078e9fd9a0a3182e1e0","datavalue":{"value":{"entity-type":"item","numeric-id":1017883,"id":"Q1017883"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5961956$C89AC60D-53E6-4A10-88AE-80933989D7BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b620e0c231ec0ee06b746eeaa690896d2abbdb23","datavalue":{"value":{"entity-type":"item","numeric-id":3677786,"id":"Q3677786"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5961956$00465479-99EE-4071-8D47-200684D973C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9658975023ae96db6624a6d65c654131f577c38d","datavalue":{"value":{"entity-type":"item","numeric-id":1594581,"id":"Q1594581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5961956$E8457C98-634E-4818-A48D-9240D0C2078B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"17f2b45686c9e19d11823814e9ab7dcc5a33bad3","datavalue":{"value":{"entity-type":"item","numeric-id":2931378,"id":"Q2931378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5961956$177BABBC-20AC-48E9-B406-1D660B12D212","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2794a7021de9a852e7b7bdc487b481322915d12e","datavalue":{"value":"10.1007/S00440-009-0222-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5961956$1D9DC50F-8F02-4AB1-81B2-9B2EDD1E4317","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3e4ddda27c7b76772b0a1708a44a37e8574d8b29","datavalue":{"value":{"entity-type":"item","numeric-id":3036360,"id":"Q3036360"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5961956$F4A6A3DA-A61B-4166-9FD0-A6A1CCFF8C30","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dd40c07cdc94e663436d430fd628cf56a90035b8","datavalue":{"value":{"entity-type":"item","numeric-id":2921423,"id":"Q2921423"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d481df565895243185ae9d897e6580d63bb660b8","datavalue":{"value":{"amount":"+0.8743852376937866","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":"Q5961956$295416DE-2D5E-43C5-9919-905CA707ED62","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8f0b2fc65c2747754f6d978142a2ea80e2cfc01b","datavalue":{"value":{"entity-type":"item","numeric-id":5506696,"id":"Q5506696"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e7fcbd1e808cf7eafd6296a26f8c47174c6f8105","datavalue":{"value":{"amount":"+0.8683094382286072","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":"Q5961956$F92468DA-B1B0-44B0-910E-CBED317C20B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"35dc166e5d0f73afa53ac2ff5dbe3ccb18ca22cf","datavalue":{"value":{"entity-type":"item","numeric-id":5383981,"id":"Q5383981"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"562afe7cc4f2142e8ca0abb3affbbb6d8cd1f3ab","datavalue":{"value":{"amount":"+0.8629903793334961","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":"Q5961956$FA637D1A-9660-4727-B374-0CD5B612E5C8","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":"5503356544499ade956d638d803210c036a9f823","datavalue":{"value":{"amount":"+0.8326369524002075","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":"Q5961956$DBAF79FE-422C-4AB4-8684-F5D7A485C045","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d3ccc87fc678e4fc16c2d4be629d0ff817af4d75","datavalue":{"value":{"entity-type":"item","numeric-id":3055775,"id":"Q3055775"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4acbf36e7e05d80afb40fff49199091575b34a2e","datavalue":{"value":{"amount":"+0.8244102597236633","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":"Q5961956$9D5754BB-70D9-49E5-82A9-C5D5E0BC97D1","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"4c66a088fc8c0a1239ebe28dff00605b7aa23672","datavalue":{"value":{"entity-type":"item","numeric-id":6830583,"id":"Q6830583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5961956$658ABA0C-B351-492E-84AB-728506800E40","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5961956","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5961956"}}}}}