{"entities":{"Q1715478":{"pageid":1726219,"ns":120,"title":"Item:Q1715478","lastrevid":57503958,"modified":"2026-03-31T04:52:12Z","type":"item","id":"Q1715478","labels":{"en":{"language":"en","value":"Existential monadic second order logic of undirected graphs: the Le Bars conjecture is false"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7011463"}},"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":"Q1715478$0E0D2ED0-F692-4DA2-B457-9971C355E7A0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"fb18c0ea7221fc32756f1027dc95d08cdbe613cf","datavalue":{"value":{"text":"Existential monadic second order logic of undirected graphs: the Le Bars conjecture is false","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1715478$90196405-E14C-4CEA-BE84-608C88FF17EE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"73674bbd5e75134fd6e31f7550fad4abbeb3cd55","datavalue":{"value":"1477.03157","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1715478$2B45D9C3-EC13-4F2B-93C6-AC95C6A6CC40","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ebcd18de5a1bbac2ea8df4823219ae8d2679caf9","datavalue":{"value":{"entity-type":"item","numeric-id":1714510,"id":"Q1714510"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1715478$BBABC29E-55CD-4EFD-AA46-CCC51BA29026","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f91a4bcbc93435aed71775d25a4c5cd09e26f12d","datavalue":{"value":{"entity-type":"item","numeric-id":122505,"id":"Q122505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1715478$0295DE47-1158-43D5-8D40-DBE515E16CA4","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ca7cadbea416389ec58d41faac46d14282f7824a","datavalue":{"value":{"time":"+2019-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":"Q1715478$D90BEF71-2241-4E74-9C24-423ADDABA12C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"19dd9e8223a444e27d7b826201967be1f5833e07","datavalue":{"value":"https://arxiv.org/abs/1807.01794","type":"string"},"datatype":"url"},"type":"statement","id":"Q1715478$D155736B-7DCF-4EDB-AFA3-411081423170","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e65bf0fb045430f780348caa9c9cb56329c123ba","datavalue":{"value":"The authors construct a sentence \\(\\varphi\\) in existential monadic second-order logic (EMSO) with two monadic variables and first-order quantifier depth 2 and with the following property. The probability that a random (labelled undirected) graph with vertex set \\(\\{1, \\ldots, n\\}\\) satisfies \\(\\varphi\\) does not converge as \\(n \\to \\infty\\). The probability distribution used is the uniform one, or equivalently, every edge has probability \\(1/2\\) independently of other edges. This result refines earlier non-convergence results for monadic second-order logic. Then it is proved that there is a dense set \\(D \\subseteq (0, 1)\\) such that, for every \\(p \\in D\\), a similar non-convergence result holds for EMSO and for graphs where each edge has probability \\(p\\) independently of other edges. The first result disproves a conjecture of [\\textit{J.-M. Le Bars}, Inf. Process. Lett. 77, No. 1, 43--48 (2001; Zbl 1003.03035)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q1715478$A1BF67C9-F658-41AB-A112-18EEDFE36211","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"63d582552c02fffafb280152e2d5e020473417a2","datavalue":{"value":{"entity-type":"item","numeric-id":494646,"id":"Q494646"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1715478$6E8F8050-0C12-43DE-B022-A260D0D7EBDF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"cd1ebd9dd665e7350d17a40eafa30f7b99b8c1e0","datavalue":{"value":"03C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1715478$ECCA91C0-F459-46B9-AAEC-862671A168C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b58df756e27df0e7b4d6d54dbbfd9015b563e63d","datavalue":{"value":"03C13","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1715478$EFA1C5E8-0B14-4548-9760-D9A14E1693AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4b7275e0d4b526075acce84a242d8537e929bb2d","datavalue":{"value":"60C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1715478$D9738962-3008-45C6-81EE-E09916405EAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1715478$65929798-0F56-479A-A55C-085A9AE8B533","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a5c4477da66ef4a910dc40c98acc2296fb0ae424","datavalue":{"value":"7011463","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1715478$06AD5E16-55AF-405E-977A-DC4A3C494D81","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a4b23bbdf8572a173d58a1452d94018235035979","datavalue":{"value":"zero-one law","type":"string"},"datatype":"string"},"type":"statement","id":"Q1715478$63637325-BDEC-47FC-8F5C-501E91694641","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"02d85bf10e66b3ded258af07af9fff60d566a297","datavalue":{"value":"binomial random graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1715478$266566F5-B879-46DF-90A1-CB90669D64A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6126605359c39008e33dc69a7938db4ea7e388a6","datavalue":{"value":"existential monadic second-order logic","type":"string"},"datatype":"string"},"type":"statement","id":"Q1715478$917B10DC-FD06-4063-A559-084C5969A28E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"335a020566a6949dcd3399476e2bd340098e7503","datavalue":{"value":"Le Bars conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q1715478$27D88479-FCE1-43E9-AEFD-269678E65071","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":"Q1715478$CAAADD18-8A36-44CB-A15E-5B61A1F6EBE6","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"bfebc0766d9d3e6f6978cfa8411fb3215d89ad1f","datavalue":{"value":"W2903902999","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1715478$71CA638D-5C79-4AA3-9795-313DA4B01A02","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"7d30ef4202445db7e7368af4b90f68c8cbc89347","datavalue":{"value":"Q122899678","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1715478$3F752912-EE9A-4163-9A25-1237F428548E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c9208528a9398d42022a83d3910fdcc8477ab6c6","datavalue":{"value":{"entity-type":"item","numeric-id":2784326,"id":"Q2784326"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1715478$5639ACE8-8FBE-4BA4-9A9A-E6DEAFE6E69E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b07d6ae8072ec0b52d1a52248f558d67752e38c","datavalue":{"value":{"entity-type":"item","numeric-id":2743189,"id":"Q2743189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1715478$99B1B9F3-E5B0-4266-9331-C3B87973E589","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":"Q1715478$5B1B3753-25E0-4E5D-94C5-3ACD3EDD5352","rank":"normal"},{"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":"Q1715478$EEEA9744-F3AA-434C-ADA2-86709A614D5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ab109aff41e40d68910d72146e4e0627a15a5d2","datavalue":{"value":{"entity-type":"item","numeric-id":1066878,"id":"Q1066878"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1715478$7D4A27A2-FA8F-4AA8-8BED-2C5D824488A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"688b0cee3c92baa2de2c620b936b2f160eafc18c","datavalue":{"value":{"entity-type":"item","numeric-id":1607080,"id":"Q1607080"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1715478$8496B98F-2F02-427D-8557-CA3D3682F4D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d3e58bac6208e0b257239f199b4609b34b8219a6","datavalue":{"value":{"entity-type":"item","numeric-id":703864,"id":"Q703864"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1715478$D38661B9-21C1-474D-B7F6-8602B52918E3","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":"Q1715478$9A5F3300-CE57-4805-A5DB-7A7EF2D02550","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dcb64ecc40f26522d78aa4932d80380ec33e44bd","datavalue":{"value":{"entity-type":"item","numeric-id":5939775,"id":"Q5939775"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1715478$F014CAB6-2836-44EC-8B28-12A55B405C53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"089612e461289e61f4437f786b15141dd858d63a","datavalue":{"value":{"entity-type":"item","numeric-id":1707156,"id":"Q1707156"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1715478$2B00058C-9167-4B48-AF23-574B42571913","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0809d99709b0d0a3bc3c504fa8529bb9e319e6f9","datavalue":{"value":"10.1016/J.APAL.2018.12.001","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1715478$A762D7B5-F8B2-42D3-8D34-93AF516A8BBD","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0b9a960594d263c057d7fcda9269d9b666457b0e","datavalue":{"value":{"entity-type":"item","numeric-id":5118048,"id":"Q5118048"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"307ee305295524c18fb046872d52c3fa89bccfe7","datavalue":{"value":{"amount":"+0.8964403867721558","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":"Q1715478$BC80D1EC-A31F-4CF9-B23B-549B93A0EE3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5d9ebcea435f3dfecad9f43b48842dfef314642a","datavalue":{"value":{"entity-type":"item","numeric-id":1732077,"id":"Q1732077"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"50db2eb7c8387b732b783f7e5b114b9302b25784","datavalue":{"value":{"amount":"+0.8689337968826294","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":"Q1715478$E95A8534-5C56-4FBD-BE7B-874D09EB0B8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9cf44954d265d55f2286f130b2310b3169fc9f20","datavalue":{"value":{"entity-type":"item","numeric-id":5096587,"id":"Q5096587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e4e77582e815707418b3d7ef45f69628f7a51187","datavalue":{"value":{"amount":"+0.8494566679000854","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":"Q1715478$6E89758C-53A3-41D7-ADC9-756D81D85ACD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"05dc9b9f38a32c3d45fbd103bfbb180c25538b7f","datavalue":{"value":{"entity-type":"item","numeric-id":2638642,"id":"Q2638642"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4cf37235e997e451613cff3c823569f51eaf2283","datavalue":{"value":{"amount":"+0.847521960735321","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":"Q1715478$6FA55AAC-8E4C-4965-BC71-50B63D1FF300","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fe62439728c0305a83381cd354d72ab276861257","datavalue":{"value":{"entity-type":"item","numeric-id":1707156,"id":"Q1707156"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7112c63ce14080a849576e58f072cd89daaf3829","datavalue":{"value":{"amount":"+0.834204375743866","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":"Q1715478$4546C660-D38F-4FBE-831C-63560BF8CC40","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1715478","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1715478"}}}}}