More than 30 years ago, Karp conjectured that all nontrivial monotone graph properties are evasive, i.e., have decision tree complexity $\binom{n}{2}$, where $n$ is the number of vertices. It was proved in 1984 by Kahn, Saks, and Sturtevant [Combinatorica, 4 (1984), pp. 297--306] if $n$ is a prime power by a topological approach. Using their method, we prove a lower bound of $\frac{1}{3}n^2-o(n^2)$ for general $n$.

This article proves several graph properties to be elusive. Two of the main results are l. If $\mathcal{P}$ is a decreasing graph property containing no graph of girth smaller than 5, then $\mathcal{P}$ is elusive. 2. The property of having matching number at most k, $k < \lfloor {{{|V|} / 2}} \rfloor $, is elusive. The proofs are all based on a topological method developed by Kahn, Saks, and Sturtevant.

Let G be a graph on n vertices. An irregular assignment of G is a weighting $ w:E ( G ) \to \{ 1, \cdots ,m \} $ of the edge-set of G such that all weighted degrees $w( v ) = \sum_{v \in e} w ( e ) $ are distinct. The minimal number m for which this is possible is called the irregularity strength$s( G )$ of G. Lehel and others have shown that $s ( G ) < \infty $ implies $s ( G )\leqq n- 1$ for connected graphs on $n \geqq 4$ vertices, and $s( G )\leqq 2n - 3$ for arbitrary graphs. By using decompositions of the additive group $\mathbf{Z}_r $ (integers mod r), these results are strengthened. Main Theorem: $s ( G )\leqq n + 1$ for any graph with $s( G ) < \infty $.