Project: Intersection Density for Transitive Permutation Groups

Again, let \(G\leq\text{Sym}([n])\) be a transitive group. The derangement graph of \(G\), denoted \(\Gamma_G\), is an undirected graph whose

• vertices are elements of the group, and
• two vertices \(\sigma, \pi\) are adjacent if \(\sigma \pi^{-1}\) has no fixed points.

Keen-eyed readers will recognize this as a Cayley graph \(\text{Cay}(G, Der(G))\). It turns out that the size of the largest intersecting set in \(G\) corresponds to the size of a maximum coclique (independence number) of \(\Gamma_G\). Then we can restate our problem as \[ \rho(G) = \frac{\alpha(\Gamma_G)}{|G_i|} \]

Since \(\Gamma_G = \text{Cay}(G, \text{Der}(G))\) is a normal Cayley graph (\(\text{Der}(G)\) is closed under conjugation), the eigenvalues of the adjacency matrix \(A(\Gamma_G)\) are found via irreducible representations of \(G\): \[ \eta_{\chi} = \frac{1}{\chi(1)}\sum_{D \in Der(G)}^{} \chi(D) \] Where \(\chi\) ranges over all irreducible characters of \(G\). Most of our computational methods rely on the eigenvalues of \(\Gamma_{G}\), and the above calculation is typically where we start.

The first 'cheap and easy' test we can use is the Hoffman Ratio Bound. In the the words of derangement graphs, this bound says \[ \alpha(\Gamma_G) \leq \frac{|G|}{1-\frac{d}{\tau}} \] where \(d\) is the largest eigenvalue (degree of a vertex in \(\Gamma_G\)) and \(\tau\) is the smallest eigenvalue of \(\Gamma_G\). A one-liner in our codebase looks something like "Is \(n\) equal to \(1-\frac{d}{\tau}\)?" If the answer is yes, then \[ \alpha(\Gamma_G) \leq \frac{|G|}{n} \] which instantly gives us \(\rho(G) = 1\). As you may expect, this does not work for many groups, but the Hoffman bound holds for weighted graphs! We can apply weightings to edges of \(\Gamma_G\) based on conjugacy classes to try to 'force' this bound to be tight. Such a weighting can be found through integer linear programming, and it turns out that this method is extremely reliable in showing that a group has intersection density equal to one. It still feels like magic, to be honest.

The No Homomorphism Lemma for vertex transitive graphs states that if \(X, Y\) are vertex transitive graphs and there exists a homomorphism \(X \to Y\), then \[ \frac{|V(X)|}{\alpha(X)} \leq \frac{|V(Y)|}{\alpha(Y)}. \] In terms of derangement graphs, we get the following:

If \(H\) is a proper transitive subgroup of \(G\), there is an embedding \(\Gamma_H \hookrightarrow \Gamma_G\), so by the No Homomorphism Lemma \[ \alpha(\Gamma_G) \leq \frac{|G|}{|H|}\alpha(\Gamma_H) \] and so, \[ \rho(G) = \frac{\alpha(\Gamma_G)}{\frac{|G|}{n}} \leq \frac{|G|}{|H|}\alpha(\Gamma_H)\frac{n}{|G|} = \rho(H). \]

The GAP package TransGrp enumerates the minimally transitive groups within a given degree. That is, all transitive groups with no transitive proper subgroups. If a group is not minimally transitive, then it must contain a minimally transitive subgroup, which gives an immediate upper bound on intersection density! After computing \(\rho(G)\) for each of the minimally transitive groups within a given degree, we had (relatively) quick and easy bounds for the rest of the groups in that degree.

My favourite (sorry, Karen!) method we used to populate the dataset exploits structure in \(\Gamma_G\) to optimize an exhaustive coclique search. It relies on two nice facts about Cayley graphs. Let \(D = \langle\text{Der}(G)\rangle\) and \(ND = \langle\text{NonDer}(G)\rangle\).

• \(\Gamma_G\) is disconnected \(\iff\) \(D \lneq G\)

In the case that \(D\) is a proper subgroup of \(G\), then we have \[ \alpha(\Gamma_G) = [G : D] \cdot \alpha(\Gamma_D) \] As \(\Gamma_G\) is a disjoint union of (cosets of) \(\Gamma_D\). Searching \(\Gamma_D\) instead amounts to reducing the number of vertices by at least half!

• \(\Gamma_G\) is a join \(\iff\) \(ND \lneq G\)

In the case that \(ND\) is a proper subgroup of \(G\), we have \[ \alpha(\Gamma_G) = \alpha(\Gamma_{ND}) \] since all cosets of \(\Gamma_{ND}\) are connected by the join operation. Thus it suffices to search only the individual component \(\Gamma_{ND}\).

We keep asking "Do the derangements generate the group?" and "Do the non-derangements generate the group?" recurring on the smaller components \(\Gamma_D\) and \(\Gamma_{ND}\) respectively if the answer is ever "no". Once the answer is yes to both of these questions, we cannot reduce any further, and begin our exhaustive coclique search.

A speed-up procedure that provides no speed-up is no procedure at all. Thus, the natural question to ask here is: "How much smaller is the group we end up searching, compared to the group we began with?"

About 13% of the groups in our dataset reduce down to a single vertex under this method.

This means that no search is actually required; we can map the largest coclique back up from a single vertex using the join and disjoint union operations. It turns out that in this case, \(\Gamma_G\) is actually a Cograph. Obviously this gives rise to some interesting questions:

• Can we characterize the groups \(G\) for which \(\Gamma_G\) is a cograph?
• What structure in \(G\) inhibits \(\Gamma_G\) from 'reducing all the way down'?