Simplicial complexes and the evasiveness conjecture

Andrés Angel and Jerson Borja – GJM, volume 1, issue 1 (2016), 1–8.

We review the topological approach to evasiveness in [5], study the sizes of automorphism groups of graphs, and use this to estimate the Euler characteristic of the simplicial complex associated to a nontrivial graph property \mathcal P on 6 vertices. The condition of being nonevasive implies that the Euler characteristic of these simplicial complexes is 1, and our estimate of \chi (\mathcal P ) obligates \mathcal P to contain some classes of special graphs. The use of Oliver groups (as in [5]) is essential to deal with the different cases that appear.

Milestones:

Received: September 2015
Published online: June 2016

Authors:

Andrés Angel, Jerson Borja
Departamento de Matemáticas
Cr 1 No 18a-12
Bogotá, Colombia

Download:

Print Version