{"entities":{"Q986694":{"pageid":988542,"ns":120,"title":"Item:Q986694","lastrevid":65800620,"modified":"2026-04-12T05:27:57Z","type":"item","id":"Q986694","labels":{"en":{"language":"en","value":"How frequently is a system of 2-linear Boolean equations solvable?"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5769507"}},"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":"Q986694$9CDD9FB5-6FF9-4860-B3AD-755689625EF4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0dee2b880f74b75b2a54594b392d2b12dbe374e2","datavalue":{"value":{"text":"How frequently is a system of 2-linear Boolean equations solvable?","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q986694$E1BACFA7-B12B-4B31-96CF-2D3E759B5248","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ee4434b3440f111fa2bf6a7563488a8d926b7cba","datavalue":{"value":"1193.05147","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q986694$7612AEF3-2591-4FF6-964E-3E7F620664EE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"241084950af58d49291b720be1f2dcc717ecf3ea","datavalue":{"value":{"entity-type":"item","numeric-id":986693,"id":"Q986693"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q986694$2C5AC2D7-B085-4849-A495-6245F24C928D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"dc5c75446f79c1451425b519e32f93a97b58ceab","datavalue":{"value":{"entity-type":"item","numeric-id":1296593,"id":"Q1296593"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q986694$423886CC-2409-4DCF-8673-B18B4A000F91","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":"Q986694$5E659010-25DF-464B-B256-BE1D831ADC74","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f6b5ac8c966befde8319f99ffd0183d046c757ce","datavalue":{"value":{"time":"+2010-08-12T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q986694$421656F1-DA12-4CD5-8C58-5431C6C4AFD1","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"12ed8ee735194e037febf9c82052991b9335bc98","datavalue":{"value":"https://arxiv.org/abs/1005.1951","type":"string"},"datatype":"url"},"type":"statement","id":"Q986694$7319058B-E630-46BC-BE77-771EF238B2EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"cb413c0b7c98559c76c09cb7a50becdb88cec450","datavalue":{"value":"https://eudml.org/doc/230549","type":"string"},"datatype":"url"},"type":"statement","id":"Q986694$D5928AD6-97BC-4339-8CB6-994B275C8D57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"7a32e891ed2a50a82d91c10aafbbf9cc0d83f293","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_17/Abstracts/v17i1r92.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q986694$8A410CC4-ACF9-4671-B984-A83BEB268931","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2efdab8bf4c6aa1e64aad34e7666a66519ef67ca","datavalue":{"value":"Summary: We consider a random system of equations \\(x_i+x_j= b_{(i,j)}\\pmod 2\\), \\((x_u\\in\\{0,1\\}\\), \\(b_{(v,u)}\\in\\{0,1\\})\\), with the pairs \\((i,j)\\) from \\(E\\), a symmetric subset of \\([n]\\times [n]\\). \\(E\\) is chosen uniformly at random among all such subsets of a given cardinality \\(m\\); alternatively \\((i,j)\\in E\\) with a given probability \\(p\\), independently of all other pairs. Also, given \\(E\\), \\(\\text{Pr}\\{b_e=0\\}= \\text{Pr}\\{b_e=1\\}\\) for each \\(e\\in E\\), independently of all other \\(b_{e'}\\). It is well known that, as m passes through \\(n/2\\) (\\(p\\) passes through \\(1/n\\), resp.), the underlying random graph \\(G(n,\\# \\text{edges}=m)\\), \\((G(n, \\text{Pr(edge)}=p)\\), resp.) undergoes a rapid transition, from essentially a forest of many small trees to a graph with one large, multicyclic, component in a sea of small tree components. We should expect then that the solvability probability decreases precipitously in the vicinity of \\(m\\sim n/2\\) \\((p\\sim 1/n)\\), and indeed this probability is of order \\((1-2m/n)^{1/4}\\), for \\(m<n/2 ((1-pn)^{1/4}\\), for \\(p<1/n\\), resp.). We show that in a near-critical phase \\(m=(n/2)(1+\\lambda n^{-1/3})\\) \\((p= (1+\\lambda n^{-1/3})/n\\), resp.), \\(\\lambda= o(n^{1/12})\\), the system is solvable with probability asymptotic to \\(c(\\lambda)n^{-1/12}\\), for some explicit function \\(c(\\lambda)>0\\). Mike Molloy noticed that the Boolean system with \\(b_e\\equiv 1\\) is solvable iff the underlying graph is 2-colorable, and asked whether this connection might be used to determine an order of probability of 2-colorability in the near-critical case. We answer Molloy's question affirmatively and show that, for \\(\\lambda= o(n^{1/12})\\), the probability of 2-colorability is \\(\\lesssim 2^{-1/4}e^{1/8}c(\\lambda) n^{-1/12}\\), and asymptotic to \\(2^{-1/4}e^{1/8} c(\\lambda)n^{-1/12}\\) at a critical phase \\(\\lambda= O(1)\\), and for \\(\\lambda\\to-\\infty\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q986694$A28A2B5B-1030-4A6A-901A-60E52F118643","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q986694$FB081105-16EB-43CF-BCEE-DBB02C908C40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1de0493fc6f7fe4361a54e7c2f5546e4ec52adf0","datavalue":{"value":"05C30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q986694$1A58F416-63BB-4A90-AB40-0229F2CC8AEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83a94c21f789e058a8d583c524929f057579d6ea","datavalue":{"value":"34E05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q986694$7C933DDA-0D70-43E0-BD58-F12F4B1FC28A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4b7275e0d4b526075acce84a242d8537e929bb2d","datavalue":{"value":"60C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q986694$8CF0B893-2961-441A-B69F-8769165A849F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d7f040acb5c463f3855e7bbd69f180141ab0abde","datavalue":{"value":"5769507","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q986694$30546681-9B12-4E94-83FE-4BF3E32971D4","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":"Q986694$1D9D41ED-E1C8-48E2-8E64-2054C7557A21","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"9cae2dd661a033a6dd36daed254393349eca630c","datavalue":{"value":"bafkreiexggftyezd2wufim3rksgg5shmxpg7znohjy37np6vc4j4wdjshi","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q986694$E097B03E-E7D2-4586-9067-E6D8481CDA8C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c5de984112ef6b8972e2532f51a6cb88536a7296","datavalue":{"value":{"entity-type":"item","numeric-id":3364350,"id":"Q3364350"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d490e2bc1ae0887ff3cf082e543962fbd8a571ac","datavalue":{"value":{"amount":"+0.8177392482757568","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":"Q986694$FEB1FF00-82E9-49C1-AD9C-283129AFD868","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"42057796e75f44d1746e88fe1a53841b191cbf8f","datavalue":{"value":{"entity-type":"item","numeric-id":4856886,"id":"Q4856886"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"00e3ca055475715bd6f166ac124359d97d002d01","datavalue":{"value":{"amount":"+0.8094757199287415","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":"Q986694$92C7DCEA-87EE-4E8A-9A68-BBFCFC7CEF13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3c9e4eb6bd01a9c85b45694d492d16044ffb9524","datavalue":{"value":{"entity-type":"item","numeric-id":2737118,"id":"Q2737118"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"16d4ecb7f821d9658b33bb041d31dfa6373a6745","datavalue":{"value":{"amount":"+0.8001691699028015","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":"Q986694$67876140-BF36-4539-8E8A-C51EA329C512","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"497c76d6b1c427ea06219abb56745739990af23f","datavalue":{"value":{"entity-type":"item","numeric-id":4258794,"id":"Q4258794"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cd92dae54b29b43ebd269629f34a7064612bb472","datavalue":{"value":{"amount":"+0.7968657612800598","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":"Q986694$2F2031A2-C210-4D26-800D-8A7910895B97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ad15481025d6f59076df3925638c008485b06502","datavalue":{"value":{"entity-type":"item","numeric-id":4217670,"id":"Q4217670"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1b9e00e9eb4752b8a980c881ca29f9641e5f8e6d","datavalue":{"value":{"amount":"+0.7962660789489746","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":"Q986694$60E886A7-1693-4474-87CA-6C924B7D839C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"How frequently is a system of 2-linear Boolean equations solvable?","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/How_frequently_is_a_system_of_2-linear_Boolean_equations_solvable%3F"}}}}}