Some Results Related to the Evasiveness Conjecture

摘要

The Evasiveness Conjecture for graph properties has natural generalizations to simplicial complexes and to set systems. In this paper we show that the Evasiveness Conjecture for simplicial complexes holds in dimension 2 and 3. We also present an infinite class of counterexamples to the Generalized Aanderaa-Rosenberg Conjecture (the Evasiveness Conjecture for set systems). The smallest member of this class is the only previously known counterexample by ILLIES.