{"entities":{"Q791548":{"pageid":793396,"ns":120,"title":"Item:Q791548","lastrevid":64451604,"modified":"2026-04-11T19:57:46Z","type":"item","id":"Q791548","labels":{"en":{"language":"en","value":"On the definability of properties of finite graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3851158"}},"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":"Q791548$AC069414-1201-4639-ACEC-765E2AF9096A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7c8099ff5f6300acec47148570984cdf2d2cb3ec","datavalue":{"value":{"text":"On the definability of properties of finite graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q791548$3680F41B-68AE-4460-B5F9-ECF7AC66A8A0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3c538822bffba09a109fd49d30d1e9d9d27c91d5","datavalue":{"value":"0536.05060","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q791548$D627EC54-0DDD-42F3-A8E1-C67DC0A89462","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c8bf0e54f887eeb79fcb5373d17511667a403dd9","datavalue":{"value":"10.1016/0012-365X(84)90166-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q791548$C52F9588-4195-45E5-BBD5-119D50DD3803","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c66a437d74ae466cacad614cef92f8e5d71204e6","datavalue":{"value":{"entity-type":"item","numeric-id":239429,"id":"Q239429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q791548$335704DA-9100-479D-832F-C2826B3B02E2","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q791548$F31182CB-595E-4D25-9DFF-1B4E32F24D0D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ee0f220147ae8bc749a64db56839865dbc4f127","datavalue":{"value":{"time":"+1984-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q791548$23670B5D-EADE-4A25-B8FE-91FE1841D32D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8e895a121f52667304d6caee7168841b69dcaf7b","datavalue":{"value":"Let \\({\\mathcal D}\\) be the class of second-order logical sentences whose variables range over first-order variables, unary relations and binary relations; the author shows that several properties of finite graphs can be defined in some special subclasses of \\({\\mathcal D}\\). The set-theoretical relationship among those subclasses is presented in one of the main theorems (using analogues of the Fra\u00efss\u00e9-Ehrenfeucht games and ultraproducts).    The paper also obtains some upper and lower bounds on the number of quantifiers \\((QN_ n)\\) and on the quantifier rank \\((QR_ n)\\) of the formulas which define the above properties for the case of graphs with n vertices. The sequences of numbers \\(QN_ n\\) and \\(QR_ n\\) can be used to define a measure on the complexity of the definition of the properties he has characterized.","type":"string"},"datatype":"string"},"type":"statement","id":"Q791548$D5D20174-E26D-4AF4-A437-9A986E222FE6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e35cfda1c439de499de525a8a9009114d934bb37","datavalue":{"value":"05C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q791548$E88F4EF6-2D8E-4A7D-9243-06AD47165690","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q791548$B16BCA4E-D150-4DD1-BF3B-FCC16D078D36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"bd857b4d539debc924b23d4d2c029b3554136b84","datavalue":{"value":"03B99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q791548$AA791C47-5883-48ED-8917-22B36725F053","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"732cf601d07b8b6931ca8c21eec2fc8f19445840","datavalue":{"value":"3851158","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q791548$A2EFF1C4-07B1-477E-A12D-867B25B33475","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"655dab1b7436833d61fd4ae79468a459b8699603","datavalue":{"value":"definability of graph-properties","type":"string"},"datatype":"string"},"type":"statement","id":"Q791548$9D6CF8BC-E762-4D74-8A6F-1B941731956B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc4b29eca207e72ea970aece64a227fbe94ab989","datavalue":{"value":"Hamiltonian graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q791548$BEF45D53-D8FB-41F8-AEEA-60C07D067698","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q791548$68938601-EDD4-427B-A877-3AA9399ECB62","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":"Q791548$641B1943-B5DF-4F46-ADF3-CF07A7F33D89","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"fc60addb581e56a452accc6c1182e97a900e80e5","datavalue":{"value":{"entity-type":"item","numeric-id":3962468,"id":"Q3962468"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q791548$D3F128A1-7347-4E11-A6EB-76A02FF136CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bbd46e00e025849b54a0892b5e385ef0d563478f","datavalue":{"value":{"entity-type":"item","numeric-id":1393228,"id":"Q1393228"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q791548$CD8C06E4-9ED7-4069-AB01-6601621660A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e8fec6e175e6b5afb296e0379add32effab9009c","datavalue":{"value":{"entity-type":"item","numeric-id":4078009,"id":"Q4078009"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q791548$937B99B0-B5B7-4794-A83A-2E87DAB28517","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d0839e7e46510112865b452a6ed8d8dd889a4c60","datavalue":{"value":{"entity-type":"item","numeric-id":4058132,"id":"Q4058132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q791548$09062359-83FD-44C9-BAB6-4B2D8DE08F13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"29035f06020bdf6a821f5c6e4a2fac381017baf3","datavalue":{"value":{"entity-type":"item","numeric-id":1256445,"id":"Q1256445"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q791548$D23A8B05-CC96-47C9-8F63-6CE9FEA68BAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cca8ae3740fcfb5a7e9f346758fcdd72ac5497a7","datavalue":{"value":{"entity-type":"item","numeric-id":4082296,"id":"Q4082296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q791548$6B6209A5-DD30-47D8-8A7A-D2C104801FCF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"12018d0a9e97c6cf951a4ec0fa485747d4a7f934","datavalue":{"value":{"entity-type":"item","numeric-id":1243269,"id":"Q1243269"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q791548$E4F8D788-E449-4D23-8CB9-888AFB9AD688","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b67ee9815f7ab3c8b2b4907677d99ca915d101b0","datavalue":{"value":{"entity-type":"item","numeric-id":1164622,"id":"Q1164622"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q791548$9E823B0D-ACD1-42B7-BCA0-C0B81806C5D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d82240301bcdb1618adc9706e69c4f13d0963ca3","datavalue":{"value":{"entity-type":"item","numeric-id":4168070,"id":"Q4168070"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q791548$BA328A41-798B-4359-9489-823B348EB271","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6d835ccc7da104c96eb1a22d7d8e47a280dbf09","datavalue":{"value":{"entity-type":"item","numeric-id":1150632,"id":"Q1150632"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q791548$9BF52E01-2A1C-4CCD-B763-D689436A0C6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"124771d01d736dd80936a72eb581897bd4704012","datavalue":{"value":{"entity-type":"item","numeric-id":3938507,"id":"Q3938507"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q791548$7883695C-2116-451A-9C22-1C5342F04828","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4dca1c9324b4e8c38ecd7d948fcc0eb9b51929da","datavalue":{"value":{"entity-type":"item","numeric-id":3778739,"id":"Q3778739"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b15ac60d929408aa917833094cfeeab77bd2a890","datavalue":{"value":{"amount":"+0.8131104707717896","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":"Q791548$62ECA617-3970-48B4-826B-E5658CF8EBE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"88bf311ec05c54bb4ac0737c1814c8cf409ddb5b","datavalue":{"value":{"entity-type":"item","numeric-id":2368907,"id":"Q2368907"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"16f8520a7a6a7f30df5cbc4b2680f5eceb0fd8df","datavalue":{"value":{"amount":"+0.798248291015625","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":"Q791548$E292F596-8861-44E3-AD41-B6E5E088B072","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c87db2a86e185b48f4925e56a3b153248baadb6f","datavalue":{"value":{"entity-type":"item","numeric-id":3118383,"id":"Q3118383"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"176cc1a39cee77d6c0e87b23b572c7ab3deeeb00","datavalue":{"value":{"amount":"+0.7887415885925293","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":"Q791548$52264B36-510E-4D6B-B42E-A3EF7E67F21B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9c0d49aeef9a815474e44e8c4a918a4ab695551a","datavalue":{"value":{"entity-type":"item","numeric-id":4817187,"id":"Q4817187"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"efb496df47374888fdace596f4404c0ad143e2bc","datavalue":{"value":{"amount":"+0.7766577005386353","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":"Q791548$BEBAF36B-5623-4C5A-8707-DB2117368EC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b6e163f9ad9294411ecfd741e4f90c326e23bc40","datavalue":{"value":{"entity-type":"item","numeric-id":2641288,"id":"Q2641288"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0358268e61d39c8f0ada0182a6178d7e714e74b1","datavalue":{"value":{"amount":"+0.7744242548942566","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":"Q791548$ED609444-E0E3-45E7-9BAB-60A8AF133405","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the definability of properties of finite graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_definability_of_properties_of_finite_graphs"}}}}}