An asymptotic bound for the complexity of monotone graph properties (Q653841)

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})\).