Atlantic Graph Theory Seminar

Speaker: Karen Meagher, University of Regina

Title: Derangement graphs and the intersection density of permutation groups

Two permutations are intersecting if they both map some $i$ to the same point, equivalently, permutations $\sigma$

and $\pi$ are intersecting if and only if $\pi^{-1}\sigma$ has a fixed point. A set of permutations is called intersecting if any two permutations in the set are intersecting. For any transitive group the stabilizer of a point is an intersecting set. The intersection density of a permutation group is the ratio of the size of the largest intersecting set in the group, to the size of the stabilizer of a point. If the intersection density of a group is 1, then the stabilizer of a point is an intersecting set of maximum size. Such groups are said to have the Erd\H{o}s-Ko-Rado property.

One effective way to determine the intersection density of a group is build a graph whose vertices are the elements of the group and the edges are defined so that the cocliques (or the independent sets) in the graph are exactly the intersecting sets in the group. This graph is called the derangement graph for the group. The focus on this talk is to demonstrate several ways we can use the derangement graph to find the intersection density of a group.

An easy example of how this can be done is if the graph has a clique with the size of the degree of the group, then the group has intersection density 1. We can also use graph homomorphisms to find bounds on the intersection density. For many small groups, the derangement graph has a very simple form and the intersection density of the group can be easily found simply from the structure of the derangement graph. In a surprising number of cases, eigenvalues of the derangement graph can be found using the representation theory of the group and, using tools from algebraic graph theory, these eigenvalues can be used to bound the size of a coclique.

Zoom link:

Meeting ID: 868 6149 9971

Passcode: 325258