{"entities":{"Q2254100":{"pageid":2264843,"ns":120,"title":"Item:Q2254100","lastrevid":55898398,"modified":"2026-02-20T23:13:44Z","type":"item","id":"Q2254100","labels":{"en":{"language":"en","value":"Zero-one laws for random distance graphs with vertices in \\(\\{0,1\\}^n\\)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6397155"}},"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":"Q2254100$F1516260-0D29-4AF7-9C71-FB3E8154A505","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4e1b4905019f2681144d86e79b7d19520ea6d9cb","datavalue":{"value":{"text":"Zero-one laws for random distance graphs with vertices in \\(\\{0,1\\}^n\\)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2254100$9D067502-2104-4D96-A18A-75F13BE4F466","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b694df553f7f10afd2b0a174701e1086df1b7bdc","datavalue":{"value":"1311.05172","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2254100$CB1FCDC6-F20F-418D-B782-C6E00F0E2545","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f47aa3e9de8704d6542c3c516d34a71192959fb7","datavalue":{"value":"10.1134/S1064562414060040","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2254100$E6930155-5DFC-4711-BE7D-5ECB4F3CDD01","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cc45e6b9322bed7360e4aac2a42f8c73614b44f3","datavalue":{"value":{"entity-type":"item","numeric-id":1787138,"id":"Q1787138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2254100$2F945C13-001B-4399-A6B2-7E3B9C46F797","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"2bbc31fcaa3dcf49d82403ba391044fdfb104e43","datavalue":{"value":{"entity-type":"item","numeric-id":161529,"id":"Q161529"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2254100$903076CB-35D2-4A27-8CCB-CFFB56F1DA5F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"fa47d3e0ba2062e2ce661f751109363b14b792ea","datavalue":{"value":{"time":"+2015-02-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2254100$1B33564A-56A4-4E8B-8FA8-9B4A15F65AF4","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f044a218b6b9c5bfe411a94fa5e097fe8706acec","datavalue":{"value":"Given a natural number \\(k\\) and a rational number \\(\\alpha=s/q\\) with \\(s<q\\) and \\(s\\) and \\(q\\) coprime, we set \\(n=n(k)=q^{2}k\\), \\(a=a(k)=sqk\\) and \\(c=c(k)=s^{2}k\\) and consider the distance graph \\(G_{k}\\) whose vertex set is the set of \\(n\\)-vectors with all components 0 or 1, with \\(a\\) of the components being ones, two such vectors being adjacent if and only if their inner product is equal to \\(c\\). We then form a random distance graph \\({\\mathcal G}(G_{k},p)\\) by retaining each edge of \\(G_{k}\\) with probability \\(p\\) independent of all other edges.  Recall that a model of random graphs is said to satisfy the zero-one law if, as the number of vertices tends to infinity, for every first-order property \\(L\\). (i.e. property expressible by a first order sentence) the probability the random graph has \\(L\\) tends to either 0 or 1. For example, it is well-known that the usual Erd\u0151s-R\u00e9nyi random graphs have this property.  The paper under review considers the situation for random distance graphs. It is known by work of Zhukovskii that random distance graphs do not satisfy the zero-one law. However one can speak of the extended zero-one \\(j\\)-law holding if, for all first-order formulae with quantifier depth bounded by \\(j\\) we have all limits of subsequences of \\(\\mathbb{P}\\) (\\({\\mathcal G}(G_{k},p)\\in L\\)) being 0 or 1, and of the extended zero-one law holding if for all first-order formulae, all limits of subsequences are 0 or 1. The paper states (but does not prove in detail) theorems which characterise the values of \\(j\\) and sequences \\({\\mathcal G}(G_{k_{i}},p)\\) for which the extended zero-one law holds, the extended zero-one \\(j\\)-law holds but the extended zero-one law does not, and for which the extended zero-one \\(j\\)-law does not hold.  By way of some flavour of the results, the extended zero-one 4-law always holds but when \\(j\\geq 6\\) the situation is more complicated, with divisibility criteria on the numbers \\(a(k)-c(k)\\). The results are stated to depend, as so often in this area, on the Ehrenfeucht game; in particular, they use the notion of a special set of vertices.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2254100$834B11D6-E2DB-4CAA-89BC-93892D4896FB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2254100$22031C5C-9042-4938-B2CD-B8D66EDC55E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"49b058fb3bbcf2e2c0b60d335491b1fb69531246","datavalue":{"value":"05C12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2254100$CA18496C-7545-44C0-AB94-9FE90547B297","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ee70b5c2f21c6e7c638c9de57f9a150921c55d02","datavalue":{"value":"6397155","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2254100$81DA81BA-76D3-4C7A-BB22-3CD5E0F1AEE1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e0446baf9c31d45b16691b35420e6e46c50f286","datavalue":{"value":"random graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2254100$EDD28E41-EBB4-42AB-9689-C268DAA8160D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b8f727868f76cd65551ab90a4b47073ece535ad8","datavalue":{"value":"random distance graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2254100$D539A57D-0C92-4176-BAA8-CCBAFCF8312B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5fc69c7af6dacb4baf163c5f7d647d4b1aa0abef","datavalue":{"value":"first-order property","type":"string"},"datatype":"string"},"type":"statement","id":"Q2254100$9C4C1610-2063-4CB4-BA80-EBD3BB35491A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b0a1c45f186413ef0d035aab9ecb90c1ce8c8579","datavalue":{"value":"0-1 law","type":"string"},"datatype":"string"},"type":"statement","id":"Q2254100$03098F14-96E2-4F0E-96DE-D4CEFEB698B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f66ac1238aba41ed60334d6cbd0154ced56b0bfd","datavalue":{"value":"Ehrenfeucht game","type":"string"},"datatype":"string"},"type":"statement","id":"Q2254100$4BD6B338-6E66-4EB3-AE21-9846E7FA0321","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"b0b0cea8603b4de1ffd54cda6d37d129691a25c2","datavalue":{"value":{"entity-type":"item","numeric-id":590772,"id":"Q590772"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2254100$7052A2D9-EB15-4CAC-843A-9A73F06203F1","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":"Q2254100$3A8F6383-AE4B-477A-90B4-62194EB5AEBB","rank":"normal"}],"P223":[{"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":"Q2254100$58821E7A-EA0C-4BFC-817E-BC68D0508BFF","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":"Q2254100$13221FBA-AAED-4929-8419-E8B77F106C9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5df9b56de5cd5e32489426b15e7a88d31f3725e8","datavalue":{"value":{"entity-type":"item","numeric-id":606499,"id":"Q606499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2254100$2B531244-788A-4841-A770-87FA20D093C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7bd64b2ecdd0089ce677d595d086c4164de360a1","datavalue":{"value":{"entity-type":"item","numeric-id":4650141,"id":"Q4650141"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2254100$FA877737-6266-45AB-B68D-872F04E308E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a7fa5b93d5c6ceb01963726e33a0f163886165b","datavalue":{"value":{"entity-type":"item","numeric-id":2262994,"id":"Q2262994"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2254100$C80AC830-E839-46A3-9E9F-40D07BA19D64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1a41ad67a719cd1a05f711afeb8d12711030e196","datavalue":{"value":{"entity-type":"item","numeric-id":2847920,"id":"Q2847920"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2254100$B828C3A6-C075-4EB9-8D04-63FE939C1BE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0bbaef82e8eb92dc4676d651d32794ea23b80ec1","datavalue":{"value":{"entity-type":"item","numeric-id":2798999,"id":"Q2798999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2254100$516CEF9A-660B-48BD-989B-F623996DFDE6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2b2a568bbd49d5145fa0a8025356eb5399736edb","datavalue":{"value":"https://doi.org/10.1134/s1064562414060040","type":"string"},"datatype":"url"},"type":"statement","id":"Q2254100$1631157F-06E7-47B1-854B-CBD4F7D08645","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"4a7a6404c0e582eea4e1585bec05936203d0679f","datavalue":{"value":"W1985440074","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2254100$88CAEFAF-E919-4B7A-84C7-95F5B88FE559","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6b84c3dc81a93ce5d9bca16b35521a805c744255","datavalue":{"value":{"entity-type":"item","numeric-id":2262992,"id":"Q2262992"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"99ec00aca961bbfebd2b39c3f57d9e6381dece09","datavalue":{"value":{"amount":"+0.99017394","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":"Q2254100$BB92001A-4AA1-4864-891F-B135972BA842","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"67f26ac70409558b39b42de367c047251f66ff84","datavalue":{"value":{"entity-type":"item","numeric-id":2817574,"id":"Q2817574"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f2d180bb1698ba556fddfbd28f69f5f7cf18f7e7","datavalue":{"value":{"amount":"+0.96347904","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":"Q2254100$14151FF8-B4F6-4180-91A0-DF51E7E0E583","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5d1e6bf7e28b8f401473707938f8d3b7ad95a3fd","datavalue":{"value":{"entity-type":"item","numeric-id":606499,"id":"Q606499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"856ee923fc9d857ce2f60280125ad797204c10b5","datavalue":{"value":{"amount":"+0.9613656","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":"Q2254100$41223A4D-BF6E-4498-A281-B36BDDF2963E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"25df84445ca4ceac07e99da97f3cfde2f09c16c4","datavalue":{"value":{"entity-type":"item","numeric-id":5198654,"id":"Q5198654"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"421ef150d63979b867da6b1e038157951ae41414","datavalue":{"value":{"amount":"+0.9593609","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":"Q2254100$DC70BE32-E5FA-4556-A190-E49A99CBFE4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5c1860dce36da7246222997cfd5432303c5c881c","datavalue":{"value":{"entity-type":"item","numeric-id":764404,"id":"Q764404"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"377b14535c304a29938d274e731d8d407b840a20","datavalue":{"value":{"amount":"+0.9554997","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":"Q2254100$BB1970EA-5AAC-428B-B5DE-39E003076C46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0dbce67b8a70bc0277c8fb6bbffeafc9ed6a89d4","datavalue":{"value":{"entity-type":"item","numeric-id":4650141,"id":"Q4650141"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3551cb4abb1e15a0783b0c3308a1f5be1b79f611","datavalue":{"value":{"amount":"+0.9441598","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":"Q2254100$C67BEA90-1B06-4237-BF67-7EFAD4DAC57D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"39c9e791cf31fa7795923112f5b17acc3b31bb35","datavalue":{"value":{"entity-type":"item","numeric-id":4790195,"id":"Q4790195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f37e2833beeeb52fbcb6bb70fee8d5517f8afed9","datavalue":{"value":{"amount":"+0.94232756","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":"Q2254100$14F91626-7985-4F71-9C17-D90A4C720777","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f86dfdddf1d2e7557f5104be163c45e0de20a817","datavalue":{"value":{"entity-type":"item","numeric-id":5694279,"id":"Q5694279"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"44eb00a0f9b7c5d0e7faa3b7bc6231b4ccb4b3fc","datavalue":{"value":{"amount":"+0.9410063","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":"Q2254100$35F9CC93-328A-404C-B9F2-C3A96FAB132F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ac1a55188c2f8a446efca90e52d9d50dd3f332a4","datavalue":{"value":{"entity-type":"item","numeric-id":2077282,"id":"Q2077282"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"641ab8b135427915879e87b36b90ce0a002552db","datavalue":{"value":{"amount":"+0.93704534","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":"Q2254100$D54DA2D1-AE37-4B57-A6B1-B4E16440F71D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b25e86d333598b88096bfaec2645168ff4f91165","datavalue":{"value":{"entity-type":"item","numeric-id":3791190,"id":"Q3791190"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2b99fdffeb16fe3b002752a65409c297bdf6f6fd","datavalue":{"value":{"amount":"+0.9282119","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":"Q2254100$5420776E-3A0C-4E64-B51B-77A30ADFCD38","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2254100","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2254100"}}}}}