ProbXiv
Explorersign in
Problem archiveProblem record

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 n=6n=6 by Kahn, Saks, and Sturtevant; the paper studies possible counterexamples for n=10n=10.

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 in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.