{"entities":{"Q2094876":{"pageid":2105619,"ns":120,"title":"Item:Q2094876","lastrevid":56689665,"modified":"2026-03-18T21:12:02Z","type":"item","id":"Q2094876","labels":{"en":{"language":"en","value":"Comparison of two convergence criteria for the variable-assignment lopsided Lov\u00e1sz local lemma"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7613665"}},"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":"Q2094876$65BDFC8B-5039-43E7-9DCF-5EA1E27CF92D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f4d713cb65a576ca107f41c93b17e21346481b6b","datavalue":{"value":{"text":"Comparison of two convergence criteria for the variable-assignment Lopsided Lov\u00e1sz Local Lemma","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2094876$4C36E739-0D23-4C80-8803-3CD582530F35","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4a8cd4a154ef159e76b904faa672ce392dd39ddb","datavalue":{"value":"10.37236/9899","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2094876$CA32000C-4A71-46C6-8019-030D30B2DD59","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"713605a893dcd5b7b7a364752ee074a0e9521f35","datavalue":{"value":{"entity-type":"item","numeric-id":666680,"id":"Q666680"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094876$4FA24E95-1A69-46F4-87AD-AE5A179EE26F","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":"Q2094876$0BAF65E5-F35F-4BF2-A02E-20D773B6964A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"41c2d4b2b9eee3d1d4724659108ff6928154d594","datavalue":{"value":{"time":"+2022-11-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2094876$51104F2E-0297-4B42-A284-0ABD6D67632B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"792a6d3532c3bcbcd8559d4da09160c7c7c737e5","datavalue":{"value":"https://arxiv.org/abs/1610.01926","type":"string"},"datatype":"url"},"type":"statement","id":"Q2094876$57F2CE60-DF62-4A02-A6BA-2F2C939C8532","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"88aa088a45c46830ee7f08de53405ad5134cee5d","datavalue":{"value":"Summary: The Lopsided Lov\u00e1sz Local Lemma (LLLL) is a probabilistic tool which is a cornerstone of the probabilistic method of combinatorics, which shows that it is possible to avoid a collection of ``bad'' events as long as their probabilities and interdependencies are sufficiently small. The strongest possible criterion that can be stated in these terms is due to \\textit{J. B. Shearer} [Combinatorica 5, 241--245 (1985; Zbl 0587.60012)], although it is technically difficult to apply to constructions in combinatorics.  The original formulation of the LLLL was non-constructive; a seminal algorithm of \\textit{R. A. Moser} and \\textit{G. Tardos} [J. ACM 57, No. 2, Article No. 11, 15 p. (2010; Zbl 1300.60024)] gave an efficient constructive algorithm for nearly all applications of it, including applications to \\(k\\)-SAT instances with a bounded number of occurrences per variables. \\textit{D. G. Harris} [ACM Trans. Algorithms 13, No. 1, Article No. 17, 26 p. (2016; Zbl 1446.68108)] later gave an alternate criterion for this algorithm to converge, which appeared to give stronger bounds than the standard LLL. Unlike the LLL criterion or its variants, this criterion depends in a fundamental way on the decomposition of bad-events into variables.  In this note, we show that the criterion given by Harris can be stronger in some cases even than Shearer's criterion. We construct \\(k\\)-SAT formulas with bounded variable occurrence, and show that the criterion of Harris is satisfied while the criterion of Shearer is violated. In fact, there is an exponentially growing gap between the bounds provable from any form of the LLLL and from the bound shown by Harris.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2094876$C93F5C4E-28BC-438F-B1B4-F6B3A985F673","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"4b7275e0d4b526075acce84a242d8537e929bb2d","datavalue":{"value":"60C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2094876$B0711DC8-7D6E-42F3-B4EA-BA47E3A05857","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"95aaddb5778e6eb703cb07af43e67828cf3485d4","datavalue":{"value":"7613665","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2094876$72064527-7235-4155-B1BA-9E0704BC0303","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":"Q2094876$3261112F-6E0C-4691-8F77-947B5EEA039C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ec91209bebb44a2810257b238c3760dd702050d7","datavalue":{"value":"W2805256348","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2094876$D29FD5EC-0186-496A-84F0-29D2BDA0BF88","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"a6d21b7dc2936ffd5bdeaaf8baf5d3eb95516544","datavalue":{"value":"Q124999221","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2094876$4D29BC54-822F-47DD-9E5F-C3A403AADA2F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"bea8ef7821b5fc6d71652f11099bd43951d62ce9","datavalue":{"value":{"entity-type":"item","numeric-id":1890827,"id":"Q1890827"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094876$A92CD00B-15EC-489F-8D58-5EC96B88E58F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8478326124c15649d699f336d0566dbd41995f78","datavalue":{"value":{"entity-type":"item","numeric-id":3103621,"id":"Q3103621"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094876$3C7784B5-64DA-46C4-8A23-0AFF25A5A3E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a118f4c4372e51856c754957bd9b998c241312b","datavalue":{"value":{"entity-type":"item","numeric-id":753819,"id":"Q753819"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094876$541D18DC-11F7-454F-BB8D-679AA9D04B85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bef669c10ae338a40d1eb7cc69ea68f5a8c5b206","datavalue":{"value":{"entity-type":"item","numeric-id":377802,"id":"Q377802"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094876$A67D9A46-E678-40E1-899D-6813DF8D97CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3bc25749e672229bc3ef1f67ddd079c8611bcc3e","datavalue":{"value":{"entity-type":"item","numeric-id":3177819,"id":"Q3177819"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094876$702518C5-5B0F-419A-AB81-57E67DC72809","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eff4dab511fa8a50e2307dc2f7e5efb805af0ca4","datavalue":{"value":{"entity-type":"item","numeric-id":4962634,"id":"Q4962634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094876$1D3D7D2C-412F-471F-BE02-D1B2FB1E9D79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf108ee6f4fd821b6c4c5958b129f6fea555bd8a","datavalue":{"value":{"entity-type":"item","numeric-id":5212787,"id":"Q5212787"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094876$A6411E46-5523-4AEF-B27F-5EB54F66A32B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4aac3166833b1071eff04bf2728ae72a8cbc72a4","datavalue":{"value":{"entity-type":"item","numeric-id":557836,"id":"Q557836"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094876$BD7B6F71-A1CD-44A3-BFFE-CC398150BD6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d42b079529a46cddd357f565d469dea5f09a5315","datavalue":{"value":{"entity-type":"item","numeric-id":5419093,"id":"Q5419093"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094876$3EC5A51D-3DC7-42FA-81A3-71CAB8764F30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6f187be9ccfc13d0d1b3d118bc39bd7d87122308","datavalue":{"value":{"entity-type":"item","numeric-id":3167430,"id":"Q3167430"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094876$B6260ECF-FBEF-4C3A-893A-2D744FE646AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3b5fa8fb11c78aae21b2eb5b72be3dfa58615b97","datavalue":{"value":{"entity-type":"item","numeric-id":4037693,"id":"Q4037693"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094876$FC2B0EF7-71FC-4C38-B29F-09F45F34A8DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d6f053ad11d1bff5592b7b77665fd28d39d0680","datavalue":{"value":{"entity-type":"item","numeric-id":1010623,"id":"Q1010623"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094876$83674194-205B-4AC0-9AC1-8080198C6993","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9718c8082b1944980e11d46a26f5f5c2b2375317","datavalue":{"value":{"entity-type":"item","numeric-id":1356486,"id":"Q1356486"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094876$D9F8FD68-4E08-4854-B95B-37E02295BB94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3d06f971812093fe6317243e078dd346e71338f6","datavalue":{"value":{"entity-type":"item","numeric-id":3578191,"id":"Q3578191"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094876$E5D52B67-9BA6-42F3-88E9-DDC5F3BB4629","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c70a12ca3ff5889b40c73f59ae18188c0482a987","datavalue":{"value":{"entity-type":"item","numeric-id":1072210,"id":"Q1072210"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094876$CD51E7D7-96AD-465E-89E6-428C663952ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2e8b3043a749599c818e819583afcfaa93c3165","datavalue":{"value":{"entity-type":"item","numeric-id":1575269,"id":"Q1575269"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094876$E94954AA-F999-4E59-9826-7A7E8D18761E","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"075ea0cbfe1bb089df346e9d63c2ebf2f63c56ab","datavalue":{"value":"bafkreidhha6xkxcmss35vm3ym5x2xghwc37tgrn5ssglzoeu5kkf7bnb7i","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2094876$BA001BD0-370C-456E-9A8F-34F25351CF70","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"94119f7819a77f431bbb0d3d9587299d9f94f1d7","datavalue":{"value":{"entity-type":"item","numeric-id":5363066,"id":"Q5363066"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"233a6ffe495c001258ccbf7d7ee0742593a0f4f9","datavalue":{"value":{"amount":"+0.8924130201339722","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":"Q2094876$A6EB33DD-EE70-479A-BAC5-275A0C71D26C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5520443357ff2500e3dfd86a1bc8acf564a843ff","datavalue":{"value":{"entity-type":"item","numeric-id":4962634,"id":"Q4962634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cd775b96f83c8775ddb79599c96de4b55c1b6378","datavalue":{"value":{"amount":"+0.8782169222831726","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":"Q2094876$4ECD94DC-09E0-48F4-BE76-A790547951B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7cf9ecc8c48115f52ec5a369ce2b8232ba1cf5b0","datavalue":{"value":{"entity-type":"item","numeric-id":5419093,"id":"Q5419093"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4c3b19a478fa282f80c53866c96f5da2472f48c2","datavalue":{"value":{"amount":"+0.8385522365570068","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":"Q2094876$DDDE6CDA-0ABA-4FFB-8A7C-67F2C154F641","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6f20f8df94b5f3dd36ce27a08b6d3eca263a6573","datavalue":{"value":{"entity-type":"item","numeric-id":2294597,"id":"Q2294597"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b35f682b0c0874feba6c1bbf0c73acaba21313b2","datavalue":{"value":{"amount":"+0.826160728931427","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":"Q2094876$288B944A-974B-48F9-AFBF-ED43837C8E44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d6fd8a7114162e62e23fa29a9a6054451c1b649c","datavalue":{"value":{"entity-type":"item","numeric-id":5395672,"id":"Q5395672"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"73671897c2c39aaa46193e62f99c07a21d7c6f53","datavalue":{"value":{"amount":"+0.82599937915802","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":"Q2094876$1A7B14AA-AA7B-45C5-8B8C-C94D335DC604","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094876$571779AD-CE9B-47D8-986B-BF27EA2121B2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2094876","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2094876"}}}}}