Predavatelj: Gert Sabidussi (McGill University, Montreal and Universite de Montreal)
A classic result of Erdos and Renyi (1963) states that almost
all graphs are asymmetric (i.e. have no non-trivial automorphism).
Given the preponderance of asymmetric graphs, it is tempting to
believe that minimal asymmetric graphs (i.e. those asymmetric graphs
every proper non-trivial induced subgraph of which has a non-trivial
automorphism) are a common occurrence, at least in the crude sense
that there are infinitely many of them. We show that this is not the
case: there are very few (in fact, exactly 18) minimal asymmetric
graphs and they are surprisingly small, having 6, 7 or 8 vertices.
Moreover, it turns out that these graphs are also precisely the mini-
mal graphs that do not have involutory automorphisms. (Joint work
with Jarik Nesetril and Jerome Gagnon.)
