{"entities":{"Q325618":{"pageid":327385,"ns":120,"title":"Item:Q325618","lastrevid":60974778,"modified":"2026-04-10T20:21:22Z","type":"item","id":"Q325618","labels":{"en":{"language":"en","value":"When does the zero-one \\(k\\)-law fail?"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6640367"}},"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":"Q325618$1651FF79-2AA0-4944-90D1-03439C5BB604","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"20c7ceab845fc54f9951b43427295f2941fc617a","datavalue":{"value":{"text":"When does the zero-one \\(k\\)-law fail?","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q325618$BD570CDE-1383-43AF-8080-65618CB9D40D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"df734f282e3f4520d451816fb721dd531c2b3140","datavalue":{"value":"1352.05170","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q325618$01D0AC0E-4D54-4C2F-9B90-EDBA7B6C8C6C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6c9fca472643a1b9914d5ac1c0eae62405941869","datavalue":{"value":"10.1134/S0001434616030032","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q325618$39AAED5C-575E-443B-9F4F-6CD240DD36DC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"214e732b9ee41b2396f55de0fe64813983a0ad39","datavalue":{"value":{"entity-type":"item","numeric-id":265976,"id":"Q265976"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q325618$CF15AA86-0860-49FF-8EEE-3C415BF28E70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8656664e017a07f612d5e30bee7bd70e454cd1dd","datavalue":{"value":{"entity-type":"item","numeric-id":325617,"id":"Q325617"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q325618$451099A0-01D0-40A7-A8DB-0A4B0D9DB33D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"00de3e6b6cfff0576fe0e1d6bc63c05579d2cb43","datavalue":{"value":{"entity-type":"item","numeric-id":173953,"id":"Q173953"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q325618$D8CA8C68-D0E9-4F9F-83F2-AE3DD29D3765","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c3dffc83549f21e2c283de8c856df086bf123c91","datavalue":{"value":{"time":"+2016-10-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q325618$EA9E5F51-B344-4A01-84AB-8FC40D1D86E1","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f3ab6d6a3298cd2d4834204a264d2a1e1e6ace81","datavalue":{"value":"The authors of this paper consider the range of edge-densities in a binomial random graph \\(G(n,p)\\) for which the 0-1 law holds within the class of properties that can be expressed by first-order formulae. That is, for any property that belongs to this class, the probability that \\(G(n,p)\\) has it tends either to 0 or to 1 as \\(n\\to \\infty\\). It is now a classic result that as long as \\(\\min \\{p, 1-p \\} n^{\\alpha} \\to \\infty\\) for any \\(\\alpha >0\\), the 0-1 law holds. This condition was weakened to all \\(p\\) that satisfy \\(p=n^{-\\alpha}\\) but for \\(\\alpha\\) irrational. However, if \\(\\alpha \\in (0,1]\\cap \\mathbb{Q}\\), then \\(G(n,n^{-\\alpha})\\) fails to satisfy the 0-1 law.  This notion can be extended to the so-called 0-1 \\(k\\)-law, which regards the class of properties that can be expressed through first-order formulae where the depth of their quantifiers is bounded by \\(k\\). The first author showed that for any \\(k\\geq 3\\) and any \\(\\alpha \\in (0, 1/(k-2))\\), the random graph \\(G(n,p)\\) obeys the 0-1 \\(k\\)-law, whereas this is not the case for \\(\\alpha = 1/(k-2)\\). When \\(\\alpha\\) is close to 1, it has been shown that the 0-1 \\(k\\)-law holds when \\(\\alpha = 1 - \\frac{1}{2^{k-1} + \\beta}\\), where \\(\\beta\\) is a rational fraction whose numerator exceeds \\(2^{k-1}\\). The main result of this paper settles the case where \\(\\beta = a/b\\) with \\(a,b \\in \\mathbb{N}\\) and \\(a\\leq 2^{k-1}\\). In fact, it is shown that for \\(k\\geq 5\\) if \\(a =1,2,\\ldots, 2^{k-1} -(b+1)^2\\), then \\(G(n,n^{-\\alpha})\\) does not satisfy the 0-1 \\(k\\)-law.","type":"string"},"datatype":"string"},"type":"statement","id":"Q325618$001F16E7-C8B2-4A3C-9D56-61A0C1B30428","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"eee5ba7f50bd271f0d45cb8360d5c0d385d238ae","datavalue":{"value":{"entity-type":"item","numeric-id":490411,"id":"Q490411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q325618$D0C02F6E-529E-47FC-969F-0D89F71314FF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q325618$34004C1F-1243-429B-B738-20D29D4CD826","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8b3f06f340043e697dc29c45b8aa27e061c315c7","datavalue":{"value":"6640367","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q325618$B55AAF96-FA5D-4F90-A879-5752E9F29F93","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f4f51776dadcb1bfead92cdaa8c678dc729e342b","datavalue":{"value":"random graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q325618$CBA39AF5-6ECC-4482-8130-292F73A80B9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a4b23bbdf8572a173d58a1452d94018235035979","datavalue":{"value":"zero-one law","type":"string"},"datatype":"string"},"type":"statement","id":"Q325618$4A866C0D-B44B-4487-AA33-DAEDD1B2A26F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5146197544fe093e923256ee62ebd13e1f6b2dc1","datavalue":{"value":"zero-one \\(k\\)-law","type":"string"},"datatype":"string"},"type":"statement","id":"Q325618$8FF0D65F-42D7-4D10-8E04-E5621A9EC9C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f01cdb5a9278ae69b8d7ab57f37299005d17bb8c","datavalue":{"value":"first-order formulae of depth \\(k\\)","type":"string"},"datatype":"string"},"type":"statement","id":"Q325618$B4405740-BFB2-4802-8389-5112126A8DAC","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":"Q325618$7D731FB8-4BA0-4300-8314-07357794D261","rank":"normal"}],"P223":[{"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":"Q325618$647B8B39-A3A9-4B8B-BD1C-707DFF159935","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bb323a3203eed200505585f88ebee68fb4d2664c","datavalue":{"value":{"entity-type":"item","numeric-id":5262204,"id":"Q5262204"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q325618$704D266E-C79A-41A6-BD4B-F41B4CF6471C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e95c136524f0a1150db97c4e268570b5db4ee744","datavalue":{"value":{"entity-type":"item","numeric-id":656220,"id":"Q656220"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q325618$080D3928-F592-4C96-BA20-4423E87B8D75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"12b882e3506ced99f538b0223081445c39cbea76","datavalue":{"value":{"entity-type":"item","numeric-id":418871,"id":"Q418871"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q325618$61FA305A-28A2-4A4C-B2A6-B875416C6110","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c169084346da6876d4a458095600583ccb1e439","datavalue":{"value":{"entity-type":"item","numeric-id":403914,"id":"Q403914"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q325618$DE4A5152-9EDB-49AC-8D24-2559EA0FB7A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ee37aa1d909457228cb511498821cdc2123f6ffe","datavalue":{"value":{"entity-type":"item","numeric-id":5264436,"id":"Q5264436"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q325618$4825BFD5-98B7-459B-A099-F248AED127A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"977f79e25621a7cdd24d8b5a4dba4b34a561a0aa","datavalue":{"value":{"entity-type":"item","numeric-id":3791190,"id":"Q3791190"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q325618$D5A0BA12-90B5-4642-9EDB-0926E469CCB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"33afbc51b0ae483cf98129919b737178588848f3","datavalue":{"value":{"entity-type":"item","numeric-id":5611005,"id":"Q5611005"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q325618$520F21E9-F9A1-4334-8F97-7799D57EAF37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1a740b6e9e652b2fb5fe827ec941309ed6af62f7","datavalue":{"value":{"entity-type":"item","numeric-id":4108321,"id":"Q4108321"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q325618$8A2672B7-B46E-4294-836C-8604A91C7A99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"651a4aa30931dcdb0297c04c91de143fc6eb69e9","datavalue":{"value":{"entity-type":"item","numeric-id":3931444,"id":"Q3931444"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q325618$F290127C-0709-47E6-9633-5A6EB175E1EC","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"38a043bde01b72537de9bcdcd6f0b2ad71dd5a8c","datavalue":{"value":"https://doi.org/10.1134/s0001434616030032","type":"string"},"datatype":"url"},"type":"statement","id":"Q325618$D3B88A70-3E58-41A4-9120-88987D2AF7A3","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"489e78c4dbbaeec8d3e3a1acb8b173606ac3d638","datavalue":{"value":"W2408522096","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q325618$AAF8BF64-A1CE-4631-83EA-924D2DA42C98","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8b868dc4d2e312f98be47dd5866383ab72e57bb4","datavalue":{"value":{"entity-type":"item","numeric-id":3979555,"id":"Q3979555"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b9d195ce12bb428c2c944da4f9af94e8edc9527e","datavalue":{"value":{"amount":"+0.8562733","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q325618$13B60BC5-3276-4A5B-B5D9-422D0DEC3F25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8258a9f0d1e6df4d78d0429f470a251032525cad","datavalue":{"value":{"entity-type":"item","numeric-id":418871,"id":"Q418871"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5d141d18803b02d1f461a2f0ed6d6a919ba6313f","datavalue":{"value":{"amount":"+0.80781364","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q325618$61B16247-A0FB-414B-93FA-36A03DFCF3EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"58cf06e36e122e96ab2df5932ab784543749d631","datavalue":{"value":{"entity-type":"item","numeric-id":2947181,"id":"Q2947181"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4a565016eccc8bb49237cafd01cccc66c41f8002","datavalue":{"value":{"amount":"+0.80605316","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q325618$404140FE-4A26-400D-A1EF-7A7179982EED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"41332694f84fdd0693ba89f99d65627bf77a70c1","datavalue":{"value":{"entity-type":"item","numeric-id":403914,"id":"Q403914"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"15fb3a2dd5b6a71fb7dfa5e9685d8b9449f25dc6","datavalue":{"value":{"amount":"+0.77942127","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q325618$67192BE6-6B7D-4C8E-BA59-C3BFF7D0341C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0b0050458185f6f0a1118386dacffb5bb71ad0cb","datavalue":{"value":{"entity-type":"item","numeric-id":325661,"id":"Q325661"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"105f516979461bfd3c22de43fd3e07950c00a4f7","datavalue":{"value":{"amount":"+0.7693068","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q325618$CC0A26AF-6495-4AB8-8FA5-C799AA1C6268","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7db29e2399f869ce6738b97ca1fc339b653220f5","datavalue":{"value":{"entity-type":"item","numeric-id":3733884,"id":"Q3733884"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f20e854aeff8f8a981baf23a95865a6dba4f610a","datavalue":{"value":{"amount":"+0.74166334","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q325618$CA9D3F2A-4FA6-44AC-9CDD-1E75066B93A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5815ce27bed02db6c3b68771ac08a5034d9b6720","datavalue":{"value":{"entity-type":"item","numeric-id":338576,"id":"Q338576"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bb9d0a4cce91c306aa217c30a45b506ae3da94e2","datavalue":{"value":{"amount":"+0.73158646","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q325618$DA399EE6-195C-440C-B3C5-D70FD6C9389C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"01220e982c64659d10e828701f9d788c7f2afb18","datavalue":{"value":{"entity-type":"item","numeric-id":645528,"id":"Q645528"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e13323a6ab4208cbdb4470a8779ce27ff3430dad","datavalue":{"value":{"amount":"+0.725287","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q325618$FB0E2F1D-661F-4483-9E43-104B09EA1B02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"402c33fdccc4d69cc381145aba9240f83cc24266","datavalue":{"value":{"entity-type":"item","numeric-id":4005187,"id":"Q4005187"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d37586061bb792d4430aaf8e965b94db4403ccaa","datavalue":{"value":{"amount":"+0.72284997","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q325618$99A9BB83-F43E-46BB-A006-8895C6B5F29F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"72c00cb90d2c87276fe5bcc6949106959980de04","datavalue":{"value":{"entity-type":"item","numeric-id":642420,"id":"Q642420"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"63deb2c46dcc5001db5a7bbab0c0b67dc5de2a09","datavalue":{"value":{"amount":"+0.7174114","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q325618$3ECDE150-D14F-4370-9AE7-B65BA8277DAD","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"When does the zero-one \\(k\\)-law fail?","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/When_does_the_zero-one_%5C(k%5C)-law_fail%3F"}}}}}