Karp's evasiveness conjecture for monotone graph properties
Statement
Let a graph property be a partition of the unlabeled graphs on a fixed number of vertices into graphs with and without the property. The property is monotone if it is preserved under the removal of edges. Associate to it the simplicial complex whose vertices are graph edges and whose simplices are the graphs having the property. A simplicial complex is nonevasive if it is a point, or if it has a vertex whose link and deletion are both nonevasive; it is evasive if it is not nonevasive. Karp's conjecture. All nontrivial monotone graph properties are evasive. The conjecture concerns the decision-tree complexity of graph properties and has connections with combinatorial and algebraic topology. It was proved for a prime-power number of vertices and for by Kahn, Saks, and Sturtevant; the paper studies possible counterexamples for .
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.