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 on 6 vertices. The condition of being nonevasive implies that the Euler characteristic of these simplicial complexes is 1, and our estimate of
obligates
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 BorjaDepartamento de Matemáticas
Cr 1 No 18a-12
Bogotá, Colombia