{"entities":{"Q329450":{"pageid":331217,"ns":120,"title":"Item:Q329450","lastrevid":61012845,"modified":"2026-04-10T20:36:37Z","type":"item","id":"Q329450","labels":{"en":{"language":"en","value":"The phase transition in random regular exact cover"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6642228"}},"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":"Q329450$C5010338-B274-4A2F-B939-FFC63515C318","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f48a47497b09f76235b85500b6a14f477ef99b1b","datavalue":{"value":{"text":"The phase transition in random regular exact cover","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q329450$06BC0ED9-2380-47AC-82A2-0E7F42B657D5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3e269f3f9a77d7d7226734739e54763e283e9672","datavalue":{"value":"1353.68210","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q329450$8F978857-CEF8-4FAD-9B66-57A6755BE071","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f30114264bb99ed602dd7898bf99dfc2aaac6327","datavalue":{"value":"10.4171/AIHPD/31","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q329450$C86B63E1-0186-4CE5-B0BA-CE5BB9CD02FF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7cfd9a39413360519196116a588605fc66450df0","datavalue":{"value":{"time":"+2016-10-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q329450$AA401513-000D-4A30-AA18-BCB47FE72D39","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"853fd347c78d4bdcafc9906469fcdd5ce82e5ca8","datavalue":{"value":"https://arxiv.org/abs/1502.07591","type":"string"},"datatype":"url"},"type":"statement","id":"Q329450$7450DBAB-F704-4B2A-8EB1-1EF68786569F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9838577be31065f95304da3763d34ecb6379561c","datavalue":{"value":"Summary: A \\(k\\)-uniform, \\(d\\)-regular instance of \\textsc{Exact Cover} is a family of \\(m\\) sets \\(F_{n,d,k}=\\{S_j\\subseteq\\{1,\\ldots,n\\}\\}\\), where each subset has size \\(k\\) and each \\(1\\leq i\\leq n\\) is contained in \\(d\\) of the \\(S_j\\). It is satisfiable if there is a subset \\(T\\subseteq\\{1,\\ldots,n\\}\\) such that \\(|T\\cap S_j|=1\\) for all \\(j\\). Alternately, we can consider it a \\(d\\)-regular instance of \\textsc{Positive} 1-\\textsc{in}-\\(k\\) SAT, i.e., a Boolean formula with \\(m\\) clauses and \\(n\\) variables where each clause contains \\(k\\) variables and demands that exactly one of them is true. We determine the satisfiability threshold for random instances of this type with \\(k>2\\). Letting  \\[ d^\\star=\\frac{\\ln k}{(k-1)(-\\ln(1-1/k))}+1 \\]  we show that \\(F_{n,d,k}\\) is satisfiable with high probability if \\(d<d^\\star\\) and unsatisfiable with high probability if \\(d>d^\\star\\). We do this with a simple application of the first and second moment methods, boosting the probability of satisfiability below \\(d^\\star\\) to \\(1-o(1)\\) using the small subgraph conditioning method.","type":"string"},"datatype":"string"},"type":"statement","id":"Q329450$7C3A5FA9-D2E9-4B7C-B386-2E54AF131606","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"0dd26fa594336927a7a04e8147a405d69e5da239","datavalue":{"value":"68Q87","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q329450$07499CBA-F662-42EA-A3B0-C29B77880E50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q329450$DEA29C28-A198-45AC-A802-E24CB6478667","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q329450$D17F470B-572C-42EC-BAF4-F8CC8DB15F52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q329450$81B7F5FD-3571-46B3-9A14-0B65AB7EB1A3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9a7ed85797f941f48ae83eafa452d90f8fcaa8eb","datavalue":{"value":"6642228","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q329450$E6E81991-FC30-46F9-9003-4C13B112D190","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"778348b169535f209fffb8dabbe107eba88f2241","datavalue":{"value":"random structures","type":"string"},"datatype":"string"},"type":"statement","id":"Q329450$EB5C4247-33DC-45DB-8158-085F73F87F5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d5f3e4ca58b2ed3663e2e3a4465f28160190050a","datavalue":{"value":"phase transitions","type":"string"},"datatype":"string"},"type":"statement","id":"Q329450$6262D12C-B6A9-43F5-B7A6-87DAF6F3E52E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3ba9b57c8aa017016096d074e724eb0d87e7253b","datavalue":{"value":"Boolean formulas","type":"string"},"datatype":"string"},"type":"statement","id":"Q329450$661B2A44-1439-42D0-8A72-B177E68A2E1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"252f9f9ed9fe8ca406cc19fba38a46c0414791ee","datavalue":{"value":"satisfiability","type":"string"},"datatype":"string"},"type":"statement","id":"Q329450$09464D49-5F4C-401B-9304-244C306F74CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1c8c9e80036612c21ad2ec3b6579e3228fd2ea1e","datavalue":{"value":"NP-complete problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q329450$7ADAB983-F76C-40A8-BF89-AEA451A789FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2b25a5a66786be30e1f9e76aa7171a8621315af0","datavalue":{"value":"second moment method","type":"string"},"datatype":"string"},"type":"statement","id":"Q329450$C98F2B61-7909-4296-A787-9AECB08F27BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"72d42075c9db0df6a468ac418941419be32a5946","datavalue":{"value":"small subgraph conditioning","type":"string"},"datatype":"string"},"type":"statement","id":"Q329450$F45C85D6-85B7-4DAC-9560-B3F78B57032C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"eae9a5c7376fab625180f58f20ebd6bb1b67e776","datavalue":{"value":{"entity-type":"item","numeric-id":162055,"id":"Q162055"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q329450$8CC89B50-78CA-4488-8CB2-15B86FF91F28","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":"Q329450$A501E6BC-A7C1-45E6-BA99-17055FBE291B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f136ba1bbebe5a2e8f35f1fc5dd64d3d1dbadf6e","datavalue":{"value":{"entity-type":"item","numeric-id":6081308,"id":"Q6081308"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q329450$831EA277-4D61-45F8-B8F2-B1D81BB41C89","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5bace7d5485335697c868447067cd35fe3ef8ea6","datavalue":{"value":{"entity-type":"item","numeric-id":5414568,"id":"Q5414568"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d1b3c095d74eee1a19cf62d45c68599d9885105d","datavalue":{"value":{"amount":"+0.8478630185127258","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":"Q329450$37215318-F385-4841-978D-841139BF5E41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dd065784386b6d160fbc130364ab5479e1cef902","datavalue":{"value":{"entity-type":"item","numeric-id":5259617,"id":"Q5259617"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9c0195f60739e12ec8c1cbbe4a32b29a757a8ed5","datavalue":{"value":{"amount":"+0.8338153958320618","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":"Q329450$624E5828-A553-4C95-B8AD-DA35986B45CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"755b56368b4cd9e9590dfe9c1728526bfbd56ede","datavalue":{"value":{"entity-type":"item","numeric-id":5963757,"id":"Q5963757"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3ee7a04f4ea82c74b34656b655736efbe57fddd2","datavalue":{"value":{"amount":"+0.8336455821990967","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":"Q329450$D92F08D1-0C13-46A4-A0B9-62D7C88328E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1d50a4c926fba5823993474f6f90660234ae0ffc","datavalue":{"value":{"entity-type":"item","numeric-id":3446816,"id":"Q3446816"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c654db2be0ab71dfce750856211bf609b0b74355","datavalue":{"value":{"amount":"+0.8061479926109314","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":"Q329450$1557EB27-D8E6-472D-8A30-9725AEE43AAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ffc87edc12877d89881cdf34d30704c2c4694198","datavalue":{"value":{"entity-type":"item","numeric-id":2990202,"id":"Q2990202"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0b88c590ed4f4f90e3afa34e2060613e2cd8543a","datavalue":{"value":{"amount":"+0.8014793395996094","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":"Q329450$3FA88CBF-92A4-47F0-AF4D-C90EC47E65DA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The phase transition in random regular exact cover","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_phase_transition_in_random_regular_exact_cover"}}}}}