Project: Intersection Density for Transitive Permutation Groups
Date:
Overview
🔗This post discusses my database of intersection densities for small transitive permutation groups. I spent two summers (2024/2025) working on this project as an NSERC USRA student, under the supervision of Dr. Karen Meagher. I recently gave a talk on this subject at the 2026 Prairie Discrete Mathematics Workshop, and this blog post aims to answer the same 'what worked and what didnt?' question that my talk focused on.
Intersection Density
🔗Let \([n] = \{1,2,\ldots,n\}\). Given two permutations \(\sigma, \pi \in \text{Sym}([n])\), we say that \(\sigma\) and \(\pi\) are intersecting if there exists \(i,j \in [n]\) such that \[ \sigma(i) = \pi(i) = j \] Given a set of permutations, we say that the set is intersecting if any two elements from the set are intersecting as above.
Let \(G \leq \text{Sym}([n])\) be a transitive permutation group. For an intersecting set \(\mathcal{F} \subseteq G\) (not necessarily a subgroup, but it can be!), the intersection density of \(\mathcal{F}\) is defined as \[ \rho(\mathcal{F}) := \frac{|\mathcal{F}|}{|G_i|} \] Where \(G_i\) is the stabilizer of the point \(i\) in the group \(G\). Using this, the intersection density of the group \(G\) is defined as \[ \rho(G) := \max \left\{\frac{|\mathcal{F}|}{|G_i} \mid \mathcal{F} \text{ is intersecting}\right\} \]
This was first defined in 2020 by Li, Song and Pantangi.
Database
🔗Since 2020, intersection density has become a productive area of research. A key missing component was a centralized dataset of known densities for small (enough) groups. Our dataset directly addressed this lack. There were a few important considerations we needed to make beforehand:
What other group properties should we catalog?
🔗The first (obvious) piece of data to hold onto is both upper and lower bounds. Our methods (in the end) almost entirely relied on creating tight upper and lower bounds on possible values of intersection density for a group. If we couldn't get our bounds to converge on a value, the table shows the best bounds we could achieve.
At the time of writing, the group properties listed alongside intersection densities mainly relate to the derangement graph (i.e. eigenvalues, connectivity, etc.) as this was our primary computational 'tool'. That is to say, we have only really kept track of what we found interesting so far. Otherwise, we have held onto more general group properties such as whether the group is abelian, nilpotent, etc. as well as the structure descriptions of the group and its stabilizer. These descriptions are generated by GAP and can be comptationally challenging. If your favourite group is missing a structure description, this is why. If there is a group property that you would like to see listed , please get in touch with me to discuss the possibility.