{"entities":{"Q653841":{"pageid":655690,"ns":120,"title":"Item:Q653841","lastrevid":63352434,"modified":"2026-04-11T12:17:52Z","type":"item","id":"Q653841","labels":{"en":{"language":"en","value":"An asymptotic bound for the complexity of monotone graph properties"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5990611"}},"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":"Q653841$EE824545-C307-4CCB-BF10-C4621656F9E9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0908511164b4d92d5227c0c04f6e3ff8894a26e3","datavalue":{"value":{"text":"An asymptotic bound for the complexity of monotone graph properties","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q653841$A7DA3820-4D3A-45B2-988C-412C03CC7881","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2a6cae821ab0a60722c3e82e8adfe4a096b90463","datavalue":{"value":"1231.05222","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q653841$98369527-61CA-49CE-81CA-7F32F6B15FE1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"02f16208e983f6c8d02cd87409430d8566c94d5d","datavalue":{"value":{"entity-type":"item","numeric-id":653840,"id":"Q653840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653841$6A4DBEC4-A54A-47FF-92AD-964B058124A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3f608b3eb8b967f499e211b27ac20bd2aaaca99c","datavalue":{"value":{"entity-type":"item","numeric-id":213186,"id":"Q213186"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653841$33A37F10-BBE3-48F2-BC65-43BE9A5C6D39","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653841$3C9460F6-D28A-4082-8F08-901CE65C43B6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5e7c33876f49da64580f033b95b71f550b669c2d","datavalue":{"value":{"time":"+2011-12-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":"Q653841$146024A7-9D7F-4D10-9239-E3E9CDB355A5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9d6cf44147cc4a196f4ceae0650f3e2e3d0d82a3","datavalue":{"value":"A graph property \\(P\\) on \\(V\\) is a set of graphs with vertex set \\(V\\), that is invariant under permutation of the vertices. Given such a property, in order to decide if an unknown graph \\(G\\) has the property, i.e., \\(G\\in P\\), some algorithm \\(A\\) is allowed to pose questions of the form ``Is \\(e\\in E(G)\\)?'' for any edge \\(e \\in E\\), where \\(E\\) is the set of all 2-element subsets of \\(V\\), called the edge set. On receiving the answer `yes' or `no', \\(A\\) computes the next question of this kind and continues until it can decide whether \\(G \\in P\\) or not. Let \\(c(G,A,P)\\) denote the number of questions. \\(G\\) is a worst case for \\(A\\) if \\(c(G,A,P) = c(A,P) = \\max_{G'} c(G' ,A,P)\\), the maximum taken over all possible graphs \\(G'\\) on the vertex set \\(V\\). \\(c(P) = \\min_{A} c(A,P)\\) is called the recognition complexity of \\( P\\), the minimum taken over all possible algorithms \\(A\\). If \\(c(P) = | E| \\), then \\( P\\) is called evasive. A graph property \\( P\\) is called monotone (decreasing) if for \\(G \\in P\\) all subgraphs of \\(G\\) have property \\(P\\), too. \\(P\\) is called nontrivial, if \\(P \\neq \\emptyset \\) and \\(P \\neq 2^{E}\\). The most famous conjecture in this context is attributed to Karp stating that any monotone nontrivial graph property is evasive. That means \\(c(n) = n(n - 1)/2 = n^{2}/2-o(n^{2})\\), where \\(c(n) = \\min_{P} c(P)\\), the minimum taken over all nontrivial monotone graph properties \\(P\\). In this paper an application of the topological approach of \\textit{J. Kahn}, \\textit{M. Saks} and \\textit{D. Sturtevant} [Combinatorica 4, 297--306 (1984; Zbl 0577.05061)] is used to the evasiveness conjecture for monotone graph properties. Although Kahn, Saks and Sturtevant proved evasiveness for every prime power of vertices, the best asymptotic lower bound for the (decision tree) complexity \\(c(n)\\) known so far is \\(n^{2}/4\\), proved in the same paper. In case that the evasiveness conjecture holds, it is \\(n(n-1)/2\\). The authors use the topological method to improve the 1/4 bound and show \\(c(n) \\geq 8n^{2}/25-o(n^{2})\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q653841$CD18C270-B915-456B-AE9A-D1300B6891D9","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"af6f91027425e6a3e182e3068da26575ef8e093e","datavalue":{"value":{"entity-type":"item","numeric-id":190560,"id":"Q190560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653841$056C96E8-14C6-4BC9-9175-DCB9316AE9AE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q653841$248C9B22-2913-48E4-9707-E8BFBF39C89D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e35cfda1c439de499de525a8a9009114d934bb37","datavalue":{"value":"05C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q653841$B84C1E0A-C0B2-4338-8959-75C6F1E90484","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q653841$8899A758-E64C-4709-A1D9-B015F3E27921","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q653841$478B6088-3952-4BB2-96C9-CA02F11A17D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q653841$3E827BC0-38E4-4090-9F3B-ACF064F64CA2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f73efdc32002167a7b804259dc6351c41ab5c104","datavalue":{"value":"5990611","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q653841$22059349-7C75-4116-903C-05321758C751","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3f61d55d78bde6169baca08e096bd2a96f91698a","datavalue":{"value":"asymptotic bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q653841$FEDDD4F3-788C-41DC-A2F1-269B60203349","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2c2330eda786d86cc40d8841f24af952276d11d1","datavalue":{"value":"monotone graph property","type":"string"},"datatype":"string"},"type":"statement","id":"Q653841$B4F6B276-CDFD-4600-881C-DEAE83120E4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5ace884256de87a5bf96e7ff991b41eec1eae247","datavalue":{"value":"evasiveness conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q653841$B93358CB-FF86-4A04-AB60-5772225ED6A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b882679a518a4d57c211097699c317189303db17","datavalue":{"value":"topological property","type":"string"},"datatype":"string"},"type":"statement","id":"Q653841$482E05B1-4879-44C8-84E0-D4A0D62C6EDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"78b826843ab20a87c9262e0d558d414868bdd4a5","datavalue":{"value":"simplicial complex","type":"string"},"datatype":"string"},"type":"statement","id":"Q653841$0379943F-64E0-4F99-ACA4-63F5E83D97A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5c3aba8d8e3b4d81ea3576067d672cf31071bd03","datavalue":{"value":"group of Oliver-type","type":"string"},"datatype":"string"},"type":"statement","id":"Q653841$8AF4B15D-BD2B-452E-9652-E82C39FBFF9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b87d7fc48c526f3af094f6b96557684b388465a5","datavalue":{"value":"complete bipartite graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q653841$02DA8CC2-78F7-429E-ABF5-AA399548273B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"952f21178d1a225b51df1682ef92b4d9e390d96b","datavalue":{"value":"prime number theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q653841$E124F5E3-A4D5-4A11-AE95-BB72CC2E6E2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f677c29e635ceff06abb2186fae53f4b4789e64a","datavalue":{"value":"recognition complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q653841$B35E73EB-B8F8-44D9-B277-6C13197C627A","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":"Q653841$9632C611-06BC-4AF6-8FA3-3B41716CA46D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"131dfab2b9374a526bb3642429f84617b1dff249","datavalue":{"value":"https://doi.org/10.1007/s00493-010-2485-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q653841$B86168BC-E4EC-4262-A3CF-9DF4ECAC4390","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6075755d01943edfa3ddc39bdc2e1d0c3c875696","datavalue":{"value":"W1983880126","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q653841$6064BD72-713E-4259-AD28-72B61E1333AB","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"e22bdc15c8aeb9646d59a58747a170e64cd75e5b","datavalue":{"value":"Q56701661","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q653841$3BB5AE70-F797-41DE-BBDF-CC60D5E221A9","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d8e29cec8786ca251bbacb83b140ec1f440a0490","datavalue":{"value":{"entity-type":"item","numeric-id":4871782,"id":"Q4871782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653841$DF9594E5-8977-468E-8949-09D0DF1F20B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"42a627346f3b58cf835906d7573c2ea08bd99e89","datavalue":{"value":{"entity-type":"item","numeric-id":4046079,"id":"Q4046079"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653841$10501BA4-CFC5-4E8E-B574-585F795746E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2364de4bf587f8bf647e21465187ed12e39e485a","datavalue":{"value":{"entity-type":"item","numeric-id":2784484,"id":"Q2784484"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653841$6FCD5794-0CB2-4387-A3CC-37733626A752","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c28903e6085f325f83f6c2f8674c9e4abb77407","datavalue":{"value":{"entity-type":"item","numeric-id":1065831,"id":"Q1065831"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653841$31FE965B-E704-4AE7-94EE-B8BB2F45AFF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ada5e833849256e7c6c4ed899b4b7ff6538b0a3","datavalue":{"value":{"entity-type":"item","numeric-id":810043,"id":"Q810043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653841$DBA5ADCA-57D1-4E6C-9A6B-680B6A148751","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da076d31b85049ed80c18404d1e826383b07b223","datavalue":{"value":{"entity-type":"item","numeric-id":1216889,"id":"Q1216889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653841$A96216F3-297A-40E8-98A4-2F1D2EDB0F13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7be7ec776afc6ad8ad178675a434e62027116713","datavalue":{"value":{"entity-type":"item","numeric-id":1238421,"id":"Q1238421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653841$EA7E247E-B9B3-452A-B0AA-75999141A3D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"465d3d91e9c619710494e58600d45f7ef993e5f8","datavalue":{"value":{"entity-type":"item","numeric-id":5778455,"id":"Q5778455"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653841$F3C095C9-46A8-4520-8F0D-6594CB47EF5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"967cfd82c02979daedba5432b2f7c61571fe301f","datavalue":{"value":{"entity-type":"item","numeric-id":4291554,"id":"Q4291554"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653841$12C07945-EADB-4F7B-81A2-05672EE83C2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4d03e534d757ba7b288af1766b490e8ecb28c226","datavalue":{"value":{"entity-type":"item","numeric-id":1924495,"id":"Q1924495"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653841$090CF75A-8BB1-4E40-9234-11A25D2F0CEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cefcb0d68060735568a4211c0151369b4dfb2c05","datavalue":{"value":{"entity-type":"item","numeric-id":3792707,"id":"Q3792707"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653841$3EED3C63-7859-4E12-AF00-83CCD44B23A6","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"7629095a11fbf58a07633d1d6433842ff57cfd55","datavalue":{"value":"journals/combinatorica/KorneffelT10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q653841$67664E0D-BC45-4B23-9FD2-D8FC6DF7A421","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"cedcce319673bda79415e5e2e850b7e342aa86b4","datavalue":{"value":"10.1007/S00493-010-2485-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q653841$B610AD9F-E21B-4395-B110-D929A38CD40E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"452006fb27b19c9cb59c6708b212a54d1c8944b5","datavalue":{"value":{"entity-type":"item","numeric-id":5300493,"id":"Q5300493"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"93ed85c35c1fdeeaf8fec96b42a3b87ea4a12d1f","datavalue":{"value":{"amount":"+0.9170268177986144","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":"Q653841$C9E26F1B-CB3E-4720-ADAF-8F3E226D8497","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"24709fddc65465bbdc6e1125f58c9062dd38014e","datavalue":{"value":{"entity-type":"item","numeric-id":2872493,"id":"Q2872493"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"24c16d448ce328300b43c9169cfdfb3dabf6576b","datavalue":{"value":{"amount":"+0.8736526370048523","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":"Q653841$82A584B3-8077-44A1-A7D4-ADAE260E0E25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"53c401999652a460e3c45e78bcf3874d8cd37adc","datavalue":{"value":{"entity-type":"item","numeric-id":1587333,"id":"Q1587333"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6a806127d9b887602ba167bd5ff174e37f82941b","datavalue":{"value":{"amount":"+0.8532432913780212","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":"Q653841$869E50A4-5502-415A-B4B7-4BD5342B429B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"47c8f40aeaea62a74910a92af92b60a9d1a3f72b","datavalue":{"value":{"entity-type":"item","numeric-id":1065831,"id":"Q1065831"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"44cfdd110e0d44ea28e22ece77cd895cd9d397d9","datavalue":{"value":{"amount":"+0.8511333465576172","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":"Q653841$859A6359-3C18-443E-8215-8F621421F04C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"70bbdb4557d0590d5081bbc3603c3616a198127f","datavalue":{"value":{"entity-type":"item","numeric-id":810043,"id":"Q810043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"099f1eedfb4e58abf1d8c54d5e20ca1aaaedf3dc","datavalue":{"value":{"amount":"+0.8360362648963928","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":"Q653841$F9181921-0524-4A05-ABB4-48E8F8D0A819","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An asymptotic bound for the complexity of monotone graph properties","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/An_asymptotic_bound_for_the_complexity_of_monotone_graph_properties"}}}}}