# Intersection density of transitive groups

Given a set of permutations \(\mathcal{F}\) of a set Ω, we say that F is *intersecting* if any two permutations of F agree on an element of \(\Omega\). That is,

It is easy to see that the subgroup \(G_\omega = \{ g\in G : \omega^g = \omega \}\) and any of its cosets are always intersecting. These are the so-called *canonical intersecting sets* of \(G\). A transitive permutation group G≤Sym(Ω) is said to have the EKR property if any family of intersecting permutations of G has size no more than a stabilizer of a point. The long term objective of this project is to classify groups that have the EKR property. This is of course a very ambitious plan and seems to be out of reach with the tools at our disposal.

Let us now introduce a parameter that *measures* how far from a point stabilizer an intersecting is. Define the **intersection density** to be the rational number

Clearly \(\rho(G)\geq 1\). In a paper with Karen Meagher and Pablo Spiga, we showed that in fact

\[1 \leq \rho(G) \leq \frac{|\Omega|}{3}.\]The upper bound is sharp since the group \(\operatorname{Alt}(4)\) acting on cosets of \(C_2\) has intersection density \(2\) (due to the fact that the largest intersecting sets are cosets of the Klein group \(C_2\times C_2\)) and \(\frac{6}{3} = 2\). In fact, there are only four transitive groups with intersection density attaining the upper bound.

One typical method often used to prove an EKR type problem is to turn it into a graph theoretic problem. Define the **derangement graph** \(\Gamma_G\) of a transitive group \(G\leq \operatorname{Sym}(\Omega)\) to be the graph whose vertex set is \(G\) and two group elements \(g\) and \(h\) are adjacent if and only if \(hg^{-1}\) is a *derangement*, i.e., a fixed-point-free permutation of \(G\). It follows that

Using this fact, we deduce that

\[\rho(G) = \frac{\alpha(\Gamma_G)}{|G_\omega|}.\]On thing to note here is that all the transitive groups attaining the upper bound \(\frac{|\Omega|}{3}\) have very special derangement graphs. In particular, their derangement graphs are complete tripartite. So far, we have not been able to find more groups attaining this upper bound. A problem that I would like to be solved is the following.

**Problem.**

Construct a family of transitive groups attaining whose intersecting density is \(\frac{|\Omega|}{3}\) . Is the intersection density \(\frac{|\Omega|}{3}\) always an integer for such groups?

In fact, I counjecture that the following statement is true.

**Conjecture.**

Given a transitive group \(G\leq \operatorname{Sym}(\Omega)\), we have that \(\rho(G) = \frac{|\Omega|}{3}\) if and only if \(\Gamma_G\) is a complete tripartite graph.

Here are some reading materials on this topic:

- Karen Meagher, Pablo Spiga, and Pham Huu Tiep. An Erdős-Ko–Rado theorem for finite 2-transitive groups. European Journal of Combinatorics, 55:100–118, 2016.
- Chris Godsil and Karen Meagher. A new proof of the Erdős-Ko-Rado theorem for intersecting families of permutations. European Journal of Combinatorics, 30(2):404–414, 2009.
- Chris Godsil and Karen Meagher. Erdős-Ko-Rado theorems: algebraic approaches
- Hujdurović, A., Kutnar, K., Kuzma, B., Marušič, D., Miklavič, Š., and Orel, M. On intersection density of transitive groups of degree a product of two odd primes. Finite Fields and Their Applications 78 (2022): 101975.