An asymptotic bound for the complexity of monotone graph properties

We present an application of the topological approach of Kahn, Saks and Sturtevant to the evasiveness conjecture for monotone graph properties. Although they proved evasiveness for every prime power of vertices, the best asymtotic lower bound for the (decision tree) complexity c(n) known so far is ¼n2, proved in the same paper. In case that the evasiveness conjecture holds, it is ½n(n−1).We demonstrate some techniques to improve the 1/4 bound and show \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ c(n) \geqslant \tfrac{8} {{25}}n^2 - o(n^2 ) $$\end{document}.