{"entities":{"Q2404656":{"pageid":2415399,"ns":120,"title":"Item:Q2404656","lastrevid":57894534,"modified":"2026-04-02T23:56:50Z","type":"item","id":"Q2404656","labels":{"en":{"language":"en","value":"Monadic second-order properties of very sparse random graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6776245"}},"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":"Q2404656$4EBAE4CD-7517-46D1-AA64-535DDF94E0A0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d8196e9d1ee1055f475f39dfd89f1d095d578105","datavalue":{"value":{"text":"Monadic second-order properties of very sparse random graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2404656$ABBD1A52-BAF1-42C0-B877-40C765BF84F0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7fcbc7810d4ba9e280515f8f575b1844d700e3cd","datavalue":{"value":"1377.03022","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2404656$12F07017-424A-442E-AAFA-F764915F43CE","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":"Q2404656$497B453A-0207-4DDF-9502-AEF8C3A50820","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2ed5ea6e891b8f80ab792539b0d37b7e97a4b6de","datavalue":{"value":{"entity-type":"item","numeric-id":512508,"id":"Q512508"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2404656$BD154C08-F647-4611-A317-A043EF55BD66","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":"Q2404656$4B98F292-E5D2-4CEB-909B-A8685822AB92","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9c21d4747e37ac8a83681ed541df851bfe5d23ff","datavalue":{"value":{"time":"+2017-09-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2404656$393F7BA2-FB35-4D2A-A12A-E20908689FFE","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"42459595608e5dc05b142184c5cc674c11d61086","datavalue":{"value":"https://arxiv.org/abs/1609.01102","type":"string"},"datatype":"url"},"type":"statement","id":"Q2404656$7856D5FA-21C6-49BA-83B5-94A95AAA3F7C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d24f650fc8f4c063b541618c312951149005c001","datavalue":{"value":"This article extends results about zero-one laws, in particular zero-one restricted to quantifier rank \\(k\\), for graphs to very sparse graphs and to monadic second-order logic (MSO). The main results give almost complete information about when such zero-one laws hold and when they do not. The Ehrenfeucht game is a major tool in the proofs. In order to prove the main results, the authors establish bounds on the number of equivalence classes of the relation ``the graphs \\(G\\) and \\(H\\) satisfy the same MSO-sentences of quantifier rank at most \\(k\\)''.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2404656$50720007-FD1F-4129-979C-06F4CB5B6DA0","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":"Q2404656$265A7403-E991-43BE-B86D-1D7ECB4CA5A0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b58df756e27df0e7b4d6d54dbbfd9015b563e63d","datavalue":{"value":"03C13","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2404656$ED1B12CD-07F2-4E0F-9D77-1BED816E2A2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cd1ebd9dd665e7350d17a40eafa30f7b99b8c1e0","datavalue":{"value":"03C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2404656$EB4D39A6-BA1D-4B7E-B1C6-411AEEBB945D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2404656$9BEEB438-5ED2-40C1-8192-75A854F8F5BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"452a95d35f44102a74d715b25e83366927e66d9c","datavalue":{"value":"60F20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2404656$63AF09FA-DEBE-45DE-87A3-260CB37FBD15","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0290a489e488a182754d90bb06c595c1fe03218a","datavalue":{"value":"6776245","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2404656$F7AB8792-A883-4099-AC28-1F65257603DD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"717d5bfd80da74e47191652383a167a59b913d55","datavalue":{"value":"monadic second-order language","type":"string"},"datatype":"string"},"type":"statement","id":"Q2404656$2D5625FF-8436-4274-805F-9EFDF4C118CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e0446baf9c31d45b16691b35420e6e46c50f286","datavalue":{"value":"random graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2404656$BA679D7C-410E-4D39-AFBF-5264F7CCEDEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a4b23bbdf8572a173d58a1452d94018235035979","datavalue":{"value":"zero-one law","type":"string"},"datatype":"string"},"type":"statement","id":"Q2404656$9DD8B3D8-3B7D-4229-84D8-E521271FA097","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f66ac1238aba41ed60334d6cbd0154ced56b0bfd","datavalue":{"value":"Ehrenfeucht game","type":"string"},"datatype":"string"},"type":"statement","id":"Q2404656$73B90015-EA18-4FB0-BD93-A34280CD3E70","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":"Q2404656$1273A353-402E-4F2C-A198-DA9D0FA4A716","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a112fd6d17e2def5786bc8f0dc8948b1aa2e25ba","datavalue":{"value":"W2963657400","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2404656$EFEB0629-7637-4CF6-8202-2AFF0D375BA3","rank":"normal"}],"P223":[{"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":"Q2404656$B5D9DD12-BBA0-442F-88FC-CE99AA8CE8F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9f878f233476a2906e1851a12c3b560149c275ba","datavalue":{"value":{"entity-type":"item","numeric-id":4780288,"id":"Q4780288"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2404656$A3E70E33-2B5D-4463-8CC4-87E73B3F2EB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"caba0538ebe31b5e55a8f229a45c19c26bda2649","datavalue":{"value":{"entity-type":"item","numeric-id":2638642,"id":"Q2638642"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2404656$73451603-F3D0-4E9B-81F3-B448A07C14FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d2c20ebeed862feb6e0841b92fd1c342102e628d","datavalue":{"value":{"entity-type":"item","numeric-id":4255575,"id":"Q4255575"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2404656$6468EA09-47EE-42DD-A1B6-0B597082B2EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"668a8637c081f79751e1e57f52557e1f7bc7f98a","datavalue":{"value":{"entity-type":"item","numeric-id":3274971,"id":"Q3274971"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2404656$0F99F53B-03D6-4815-AE06-CA93DD6EB2F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"edd227013a96dd65d0289b90d93ff4bba0dd80ab","datavalue":{"value":{"entity-type":"item","numeric-id":3286850,"id":"Q3286850"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2404656$278A0489-FF99-4F44-A8CD-16D528A0FF58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"984b0790103c755d1e373d861a44bec66558001d","datavalue":{"value":{"entity-type":"item","numeric-id":5555420,"id":"Q5555420"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2404656$DC506177-A98F-4A83-9F28-053F54866A67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"18d639fb9d03ad258814bab0f3f43d6d28e28a1e","datavalue":{"value":{"entity-type":"item","numeric-id":1173404,"id":"Q1173404"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2404656$A8B080C0-11EF-4A1C-9743-1ACEEDF9A02A","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":"Q2404656$B18CE812-9733-41AF-B7E7-4A5829C0A26B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f2b884863289b9d37b4528f7c72bd221099d1c8e","datavalue":{"value":{"entity-type":"item","numeric-id":4359311,"id":"Q4359311"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2404656$EE3B9B18-9996-41C2-A1E6-A385D3D178FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2fa83ce08e81f681ff8711a2598a37848faf844d","datavalue":{"value":{"entity-type":"item","numeric-id":2368907,"id":"Q2368907"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2404656$9DE432D9-0ECF-441D-B171-CBDEC1C5AD58","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":"Q2404656$23FEE662-398D-4AF2-938A-6A9AB79427DC","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":"Q2404656$51D88B45-23C3-46E5-9E4B-D864CF1E27AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f0f4f5f54c975960218f2d8acbf472119dedeb64","datavalue":{"value":{"entity-type":"item","numeric-id":4283251,"id":"Q4283251"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2404656$86686A25-D24B-4408-AF49-805DAC39F287","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":"Q2404656$C05D112C-A3CE-4C6B-9A50-726B3E77D057","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":"Q2404656$D8A85733-FAA1-4467-818D-AABD05951DE6","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":"Q2404656$F9F86513-663B-4E34-98FD-BD3C99CEB585","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":"Q2404656$282807C2-88F5-4F93-A008-AB8350D0C622","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"dd845ece3ee3ff594c7faed1f831cb9f5df5dbc1","datavalue":{"value":"10.1016/J.APAL.2017.06.004","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2404656$B312F7D1-C787-44FF-9AA5-832B6EA1B5F9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"de1c49d1b5eb327fe54c3ef16d83e558ffe4f0b1","datavalue":{"value":{"entity-type":"item","numeric-id":512509,"id":"Q512509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d64b3c0c181cd1726a9b6cb45df39074d7aa2594","datavalue":{"value":{"amount":"+0.9137753844261168","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":"Q2404656$C36F569C-C55A-404A-8334-717391DEB848","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8fdcc776971b07ce5db15e22e285f52abea1f72f","datavalue":{"value":{"entity-type":"item","numeric-id":4562315,"id":"Q4562315"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8660c502a3f034ee51de7154bd77166af8113981","datavalue":{"value":{"amount":"+0.9129101037979126","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":"Q2404656$C83F33BE-3F09-4F81-AC80-9FF771C5E6C5","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":"72ea9666eaf0e8d100bc69edf2bfa4fa63264100","datavalue":{"value":{"amount":"+0.8764994740486145","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":"Q2404656$EFEB9FAD-D324-4619-8370-4DC61BF3891F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"95e2496ccd3e9e115826a04b0366d6a08a513239","datavalue":{"value":{"entity-type":"item","numeric-id":2358597,"id":"Q2358597"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6a8e23315bf0388a789c9cb38d74110cef1b9617","datavalue":{"value":{"amount":"+0.8642598986625671","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":"Q2404656$C742E88B-3C7A-4080-8FA8-46BAD08649A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"69ff0c8d275fa3b8d036c33908e67b3e2218a108","datavalue":{"value":{"entity-type":"item","numeric-id":4605739,"id":"Q4605739"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0714df4cebebc3cdd38870df95255e415587587b","datavalue":{"value":{"amount":"+0.8640174865722656","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":"Q2404656$A95811E2-DB63-4887-B6D0-C57F7F378F74","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2404656","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2404656"}}}}}