Combinatorics Seminar

When: Sunday, May 3, 10am Where: Schreiber 309 Speaker: Andrzej Kisielewicz, Univ. of Wroclaw Title: Symmetries of graphs and other combinatorial structures

Abstract:

It is known that every abstract group is isomorphic to the automorphism group of some graph. It is also known that not every permutation group is equal to the automorphism group of some graph. Describing those permutation groups that are the automorphism groups of graphs is known as a concrete version of the Konig problem. The problem is hard and open in its generality.

We argue that it is the knowledge on the concrete automorphism groups that is needed in many applications, and therefore the problem is important. We present some results and some interesting questions motivated by the general Konig problem. In particular we characterize graphs that (except for the complete graphs and their complements) have the highest degree of symmetry.