{"entities":{"Q2211263":{"pageid":2222006,"ns":120,"title":"Item:Q2211263","lastrevid":73589493,"modified":"2026-04-14T16:34:05Z","type":"item","id":"Q2211263","labels":{"en":{"language":"en","value":"First-order definitions of subgraph isomorphism through the adjacency and order relations"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7272350"}},"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":"Q2211263$F579498F-CCC5-4BCA-AD93-3B2A10CA70EA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"63a14b73503728a3f496a9e03dc7228e123b0e12","datavalue":{"value":{"text":"First-order definitions of subgraph isomorphism through the adjacency and order relations","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2211263$177595A9-82CB-4651-89F3-388177B9AA8F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"63256ee5317f5e594da545e4820a86d1ccaefe65","datavalue":{"value":"1472.03026","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2211263$289CEB3A-7BEC-462F-A0E3-C2F87AFFDAC2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"581e0a90574db2dfeef91664f143bbcb3d09ae4b","datavalue":{"value":{"entity-type":"item","numeric-id":2211261,"id":"Q2211261"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2211263$1E30978D-2BBE-4FA0-A3E4-0A02AE67754F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"77706e6a554a2411c13f2d0638b1a27614abbfcf","datavalue":{"value":{"entity-type":"item","numeric-id":2211262,"id":"Q2211262"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2211263$7302F3A4-14B6-48A7-8D78-09F1A2BD0702","rank":"normal"},{"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":"Q2211263$FFD076E0-E4DF-41C7-B153-08694553E843","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"96d61287f253fc18075a19b52e9e24b787406c3d","datavalue":{"value":{"entity-type":"item","numeric-id":266692,"id":"Q266692"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2211263$B2F02D3D-881C-4876-A5E4-0FE249C8BC68","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d9f22268837797e046dca0302ad58b944858f292","datavalue":{"value":{"time":"+2020-11-10T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2211263$0B3F7395-1136-41BC-8433-BC42732EE8A3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7487470ae9ec69374c47dc99f9e7c8e49674c856","datavalue":{"value":"Given a graph \\(F\\), let \\(\\mathcal S(F)\\) be the graphical property of having \\(F\\) as a (not necessarily induced) subgraph. If \\(\\sim\\) is the vertex adjacency relation symbol, let \\(\\Sigma = \\{ \\sim, < \\}\\) be the signature for linearly ordered finite graphs. A first-order sentence \\(\\varphi\\) of signature \\(\\Sigma\\) defines \\(\\mathcal S(F)\\) if, for any graph \\(G\\), and any linear ordering of \\(G\\)'s vertices, if \\(G'\\) is \\(G\\) expanded by that linear ordering, then \\(G' \\models \\varphi\\) iff \\(G\\) has \\(F\\) as a (not necessarily induced) subgraph. Let \\(D_< (F)\\) be the minimum quantifier depth of any \\(\\Sigma\\)-sentence defining \\(\\mathcal S(F)\\) and let \\(W_< (F)\\) be the minimum number of variables of any \\(\\Sigma\\)-sentence defining \\(\\mathcal S(F)\\).  The primary result of this paper is that if \\(F\\) is a tree of \\(\\ell\\) vertices, then \\(D_< (F) \\leq \\ell/2 + \\lceil \\log_2 (\\ell + 2) \\rceil - 1\\); they also observe that \\(W_< (F) \\leq \\ell/2 + 2\\). In addition, using Fra\u00efsse-Ehrenfeucht games, \\(D_<(F)\\) is computed for each graph \\(F\\) of order less than \\(5\\).  There are some typos, so readers should take care.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2211263$9F38A604-CB57-4D2F-BA8F-E6C4A3C3FC2A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b58df756e27df0e7b4d6d54dbbfd9015b563e63d","datavalue":{"value":"03C13","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2211263$EDB54E8B-50AA-4D7F-A0AB-8ACCA128C415","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2e742a171e2cc4a4f154f55124e2a34e0da3eb3e","datavalue":{"value":"05C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2211263$A340C0AB-6C81-4983-9B50-65E366FACEFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8b0f166240d9dc937c89dbc2241079deae14191f","datavalue":{"value":"68Q19","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2211263$046F62A4-5868-4760-8FF3-B71F0400C436","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"71d8576c688d7aa63eb54dd5677343d50c2dd739","datavalue":{"value":"7272350","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2211263$CE4297ED-3EFD-46DC-9644-C1561F3D87AC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"420132b0a86bb9bedd0eeeab0b7b74055a6e96fb","datavalue":{"value":"descriptive complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2211263$7E930656-7047-458C-86F2-70C32280DA1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e2e80a7123e4ea6d0418cb24d37b1837f13e3514","datavalue":{"value":"first-order logic","type":"string"},"datatype":"string"},"type":"statement","id":"Q2211263$B284F01B-1199-4700-A05F-DD12890CBFB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"269f1710096a92fcd487f9b3d4f982f60a492a11","datavalue":{"value":"linearly ordered graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2211263$EEFEE114-490B-4039-9C64-991396C4FD05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8582c9c9734eff214e5b5db65e867b5c228e500c","datavalue":{"value":"logical complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2211263$741D267B-15C8-4B2F-B4A4-9DA2BB0DEE04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c6a26c619f3c34107172c32ab1d29a17af19378d","datavalue":{"value":"order","type":"string"},"datatype":"string"},"type":"statement","id":"Q2211263$F4064F2A-E669-4F79-B6C9-F08793FAC5EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c942b924ef6815a15ef16fab58fd6b52038863cb","datavalue":{"value":"quantifier depth","type":"string"},"datatype":"string"},"type":"statement","id":"Q2211263$C9DD7FEC-7694-49AF-B25A-BEF067BF3F25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e50d5f5383452bd2adcef1d921f570ccfd70e04f","datavalue":{"value":"subgraph isomorphism","type":"string"},"datatype":"string"},"type":"statement","id":"Q2211263$0211062A-5CC2-444C-9427-499B28CBB121","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4f9b31f62fd7a97ff488d61ff311b8af96719461","datavalue":{"value":"subtree","type":"string"},"datatype":"string"},"type":"statement","id":"Q2211263$DB54500D-AF62-4759-841B-EC9966EA336D","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"f4c2e453a383fe1e064f27e4ca3ff49f8a1646b9","datavalue":{"value":{"entity-type":"item","numeric-id":587174,"id":"Q587174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2211263$0DFC2B28-A9FC-43A0-A2BC-9A1A37035DE7","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":"Q2211263$7B7A5043-2885-4C50-8C0B-E28E0EC517DB","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"50cd828a6fd7f30776fd571c2ddc2600ef146190","datavalue":{"value":"https://doi.org/10.2140/moscow.2020.9.293","type":"string"},"datatype":"url"},"type":"statement","id":"Q2211263$69D80826-2367-4967-B1AB-C1DA894EE9F6","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"68ca123ad071e0bc13ebe2c8bd99255254c5683d","datavalue":{"value":"W3099028489","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2211263$C5CBE9AC-A48F-4AE7-8710-B44334AAD350","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"42451d9b2f091244b010a7dc1fc6a0f53a57abc4","datavalue":{"value":{"entity-type":"item","numeric-id":4369883,"id":"Q4369883"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2211263$C08DE58B-1612-4E75-A74B-E5C21CBF3729","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"84ed68bb82322138e41236c78cc7522d16decb13","datavalue":{"value":{"entity-type":"item","numeric-id":3452408,"id":"Q3452408"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2211263$821A6AF7-7CD6-4BF0-B9F9-89E7D3376684","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a533c85d71673e7ede6c73cb98ee5493ea601bf8","datavalue":{"value":{"entity-type":"item","numeric-id":3688439,"id":"Q3688439"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2211263$740C9E94-E8AA-4B91-8E21-D60A1150CC4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"66523b27bb84ab786e255b752e704e217b2f2452","datavalue":{"value":{"entity-type":"item","numeric-id":4928477,"id":"Q4928477"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2211263$C3DF4087-AC25-419B-A3B2-9550EC56555F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"47e1c7851d8fc5c12f4d59263bc3e959c54ebb30","datavalue":{"value":{"entity-type":"item","numeric-id":3121527,"id":"Q3121527"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2211263$7EA2A43E-1218-49A2-999F-568C355930EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"86e802a109f6c7b3d486f9c45461be2e97e6111b","datavalue":{"value":{"entity-type":"item","numeric-id":5222874,"id":"Q5222874"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2211263$83321EAE-CA8C-45CC-B90D-D99EF04F8CF8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1f58b3d352be57703086400389e55c3bcd203a9d","datavalue":{"value":"10.2140/MOSCOW.2020.9.293","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2211263$50D3AAAD-A61F-4AD3-9883-43C4DE2B1BEF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"929ae5512342aa0c515d27c68dc4cf0bd3a22e58","datavalue":{"value":{"entity-type":"item","numeric-id":679970,"id":"Q679970"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"679fc50b2ab3b1dcfabd62d8204ec375c8d5b6a2","datavalue":{"value":{"amount":"+0.8525359630584717","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":"Q2211263$12DBC03E-43DD-4722-B7D8-C8F116798B83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c88fc18850961f38617353c53a51dfd4fffd29ae","datavalue":{"value":{"entity-type":"item","numeric-id":5003303,"id":"Q5003303"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c4f9b082cef7c44cd4d0fc36f71939d20dc1f423","datavalue":{"value":{"amount":"+0.8324486613273621","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":"Q2211263$113D2822-A108-465C-8116-C841FBC56E0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ac9db67bf90dcb16b92c149cb761af0dfec68970","datavalue":{"value":{"entity-type":"item","numeric-id":3121527,"id":"Q3121527"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0577fe6a0b272921441a98796d68f0ea1afe8eeb","datavalue":{"value":{"amount":"+0.8016866445541382","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":"Q2211263$D537EEE1-EA32-43C1-B252-46E4562B1732","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"First-order definitions of subgraph isomorphism through the adjacency and order relations","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/First-order_definitions_of_subgraph_isomorphism_through_the_adjacency_and_order_relations"}}}}}