Marco Barbieri: Fixed point ratios for vertex-primitive graphs

Date of publication: 30. 11. 2023
Discrete mathematics seminar
Tuesday
5
December
Time:
10:15
Location:
Plemljev seminar, Jadranska 19

Abstract/Povzetek

The fixed point ratio of a permutation group is the maximum portion of points that are not moved by an element of the group. This notion was originally introduced by Liebeck and Shalev as a key ingredient in the probabilistic approach for bounding the base size of a finite permutation group, and it was firstly applied in the context of strongly regular graphs by Babai as a step towards his algorithm for the graph isomorphism problem in quasipolynomial time. In the present talk, we are discussing what is known for less symmetric graphs, focusing our attention on the classification of vertex-primitive graphs with fixed point ratio exceeding 1/3.