On the EKR-module Property

The Erdős-Ko-Rado (EKR) theorem [12] is a classical result in extremal set theory. This celebrated result considers collections of pairwise intersecting $k$-subsets of an $n$-set. The result states that if $n\geq 2k$, for any collection $\mathfrak{S}$ of pairwise intersecting $k$-subsets, the cardinality $|\mathfrak{S}|\leq{n-1\choose k-1}$. Moreover in the case $n>2k$, if $|\mathfrak{S}|={n-1\choose k-1}$, then $\mathfrak{S}$ is a collection of $k$-subsets containing a common point. (When $n=2k$, the collection of $k$-subsets that avoid a fixed point, is also a collection of ${n-1\choose k-1}$ pairwise intersecting subsets.) From a graph-theoretic point of view, this is the characterization of maximum independent sets in Kneser graphs.

There are many interesting generalizations of this result to other classes of objects with respect to certain form of intersection. One such generalization given by Frankl and Wilson [14] considers collections of pairwise non-trivially intersecting $k$-subspaces of a finite $n$-dimensional vector space, which corresponds to independent sets in $q$-Kneser graphs. The book [17] is an excellent survey, including many generalizations of the EKR theorem.

In this article, we are concerned with EKR-type results for permutation groups. The first result of this kind was obtained by Deza and Frankl [13], who investigated families of pairwise intersecting permutations. Two permutations $\sigma,\tau\in S_{n}$ are said to intersect if the permutation $\sigma\tau^{-1}$ fixes a point. A set of permutations is called an intersecting set if $\sigma\tau^{-1}$ fixes a point for any two members $\sigma$ and $\tau$ of the set. Clearly the stabilizer in $S_{n}$ of a point or its coset is a canonically occurring family of pairwise intersecting permutations, of size $(n-1)!$. In [13], it was shown that if $\mathcal{S}$ is a family of pairwise intersecting permutations, then $|\mathcal{S}|\leq(n-1)!$. In the same paper, it was conjectured that if the equality $|\mathcal{S}|=(n-1)!$ is met, then $\mathcal{S}$ has to be a coset of a point stabilizer. This conjecture was proved by Cameron and Ku (see [8]). An independent proof was given by Larose and Malvenuto (see [20]). Later, Godsil and Meagher (see [15]) gave a different proof. A natural next step is to ask similar questions about general transitive permutation groups.

Let $G$ be a finite group acting transitively on a set $\Omega$. An intersecting subset of $G$ with respect to this action is a subset $\mathcal{S}\subset G$ in which any two elements intersect. Obviously, a point stabilizer $G_{\alpha}$, its left cosets $gG_{\alpha}$, and right cosets $G_{\alpha}g$ are intersecting sets, which we call canonical intersecting sets. An intersecting set of maximum possible size is called a maximum intersecting set. Noting that the size of a canonical intersecting set is $|G_{\alpha}|=|G|/|\Omega|$, we see that the size of a maximum intersecting set is at least $|G|/|\Omega|$. It is now natural to ask the following:

(A) Is the size of every intersecting set in $G$ bounded above by the size of a point stabilizer?

(B) Is every maximum intersecting set canonical?

As mentioned above, the results of Deza-Frankl, Cameron-Ku, and Larose-Malvenuto show that the answer to both these questions in positive for the natural action of a symmetric group. However, not all permutation groups satisfy similar properties, although there are many interesting examples that do. We now formally define the conditions mentioned in the above questions.

When the action is apparent, these properties will be attributed to the group. We have already seen that the natural action of $S_{n}$ satisfies both the EKR and the strict-EKR property. EKR properties of many specific permutation groups have been investigated (see [1, 3, 22, 25, 26, 27]). In particular, it was shown that all $2$-transitive group actions satisfy the EKR property, see [25, Theorem 1.1], but not every 2-transitive group satisfies the strict-EKR property; for instance, with respect to the $2$-transitive action of $\mathrm{PGL}(n,q)$ (with $n\geq 3$) on the 1-spaces, the stabilizer of a hyperplane is also a maximum intersecting set. However, it is shown in [25] that $2$-transitive groups satisfy another interesting property called the EKR-module property, defined below.

For a transitive group $G$ on $\Omega$ and a subset $S\subset G$, let

the characteristic vector of $S$ in the group algebra $\mathbb{C}G$. For $\alpha,\beta\in\Omega$ and $g\in G$ with $g\cdot\alpha=\beta$, we write

the characteristic vector of the canonical intersecting set $gG_{\alpha}$, which we call a canonical vector for convenience. The next definition was first introduced in [23].

The name is from the so called “module method” described in [2]. We remark that

1. (a)

   a group action satisfying the strict-EKR property also satisfies the EKR-module property, but the converse statement is not true;

2. (b)

   and there exist group actions that satisfy the EKR-module property but not the EKR property, see [24, Theorem 5.2], and the following Example 1.3;

We will now construct an example of a group action that satisfies the EKR property, but not the EKR-module property. Prior to doing so, we mention a well-known result. Consider a transitive action of a group $G$ on a set $\Omega$. A subset $R\subset G$ is said to be a regular subset, if for any $(\alpha,\ \beta)\in\Omega^{2}$, there is a unique $r\in R$ such that $r\cdot\alpha=\beta$. Corollary 2.2 of [3] states that permutation groups which contain a regular subset, satisfy the EKR property.

For a group $G$ and a subgroup $H\leqslant G$, let

the set of left cosets of $H$ in $G$. Then $G$ acts transitively on $[G:H]$ by left multiplication. Moreover, each transitive action of a group is equivalent to such a coset action.

We will now describe the main results of our paper.

In this section, we gather some tools which are used to prove our main results, and then prove Theorem 1.5.

Let $K=G_{(\Omega)}$ be the kernel of $G$ on $\Omega$. Here $\Omega=[G:H]$ for some $H\leq G$. The following simple lemma shows that we may assume without loss of generality that $K$ is trivial.

As an immediate consequence, we get the following corollary.

For any $g\in G$, we denote by $H^{g}$ the subgroup $gHg^{-1}$. Given $\alpha=aH\in\Omega$, we have $G_{\alpha}=H^{a}$. Thus, with respect to this action, we see that the set $\{aH^{b}\ :\ a,b\in G\}$ is the set of canonical intersecting sets. By $\mathfrak{I}_{G}(\Omega)$, we denote the subspace of $\mathbb{C}G$ spanned by the set $\{\mathbf{v}_{aH^{b}}\ :\ a,b\in G\}$ of the characteristic vectors of the canonical intersecting sets. By the definition of the EKR-module property, the action of $G$ on $\Omega$ satisfies the EKR-module property if and only if $\mathbf{v}_{\mathcal{S}}\in\mathfrak{I}_{G}(\Omega)$ for every maximum intersecting set $\mathcal{S}$ in $G$.

We observe that for every $a,\ b,\ g,\ h\in G$, we have $g\mathbf{v}_{aH^{b}}h=\mathbf{v}_{gahH^{h^{-1}b}}$. Therefore, $\mathfrak{I}_{G}(\Omega)$ is a two-sided ideal of the group algebra $\mathbb{C}G$. The two-sided ideals of complex group algebras are characterized by the Artin-Wedderburn decomposition.

We will now recall some basic facts on group algebra, proofs of which can be found in any standard text on representation theory such as [19]. Let ${\rm Irr}(G)$ be the set of irreducible complex characters of $G$. For $\chi\in{\rm Irr}(G)$, we define $M_{\chi}:=\sum\limits_{i=1}^{\chi(1)}W_{i}$, where $\{W_{1},W_{2},\ldots W_{\chi(1)}\}$ are the right submodules of $\mathbb{C}G$ that afford the character $\chi$. By Maschke’s theorem, we have the decomposition

For each $\chi\in{\rm Irr}(G)$, we have $\mathrm{dim}_{\mathbb{C}}(M_{\chi})=\chi(1)^{2}$ and that $M_{\chi}$ is a minimal two-sided ideal containing the primitive central idempotent

By orthogonality relations among characters, we have

Using the fact that $\mathbb{C}G$ is a semi-simple algebra, we now get the following description of two-sided ideals of $\mathbb{C}G$

Our investigation of the EKR-module property of the action of $G$ on $\Omega$, will benefit from the description of $\mathfrak{I}_{G}(\Omega)$ as a direct sum of simple ideals of $\mathbb{C}G$. We recall that $\mathfrak{I}_{G}(\Omega)$, is the subspace of $\mathbb{C}G$ spanned by the set $\{\mathbf{v}_{aH^{b}}\ :\ a,b\in G\}$. We also showed that it is a two-sided ideal.

As an immediate application, we obtain a significantly shorter proof of Lemma 4.1 and Lemma 4.2 of [2]. The content of these two results is presented as the following corollary. We will use the following technical result in the proof of Theorem 1.7. We would like to mention that it was a key result that led to the “Module Method” described in [2].

We are now ready to prove Theorem 1.5.

Proof of Theorem 1.5: Given $\chi\in C=\{\chi\in{\rm Irr}(G)\ :\ \chi(\mathbf{v}_{H})=0\}$, by Lemma 2.4 and (1), we have $e_{\chi}x=0$, for all $x\in\mathfrak{I}_{G}(\Omega)$. By the definition of the EKR-module property, for any maximum intersecting set $\mathcal{S}$, we have $\mathbf{v}_{\mathcal{S}}\in\mathfrak{I}_{G}(\Omega)$. The equality $\chi(\mathbf{v}_{\mathcal{S}})=0$ follows from $e_{\chi}\mathbf{v}_{\mathcal{S}}=0$.

We now prove the other direction. Suppose that for any $\chi\in C$ and any maximum intersecting set $\mathcal{S}$, we have $\chi(\mathbf{v}_{\mathcal{S}})=0$. Fix a maximum intersecting set $\mathcal{S}$. If $\mathcal{S}$ is a maximum intersecting set, then so is $\mathcal{S}g^{-1}$, for all $g\in G$. Therefore, $\chi(\mathbf{v}_{\mathcal{S}g^{-1}})=0$, for all $\chi\in C$ and all $g\in G$. Thus $\frac{|G|}{\chi(1)}e_{\chi}\mathbf{v}_{\mathcal{S}}=\sum\limits_{g\in G}\chi(\mathbf{v}_{\mathcal{S}g^{-1}})g=0$, for all $\chi\in C$. Further, by the equality $\sum\limits_{\psi\in{\rm Irr}(G)}e_{\psi}=1$, we have

By Lemma 2.4, $\sum\limits_{\psi\notin C}e_{\psi}\in\mathfrak{I}_{G}(\Omega)$. Since $\mathfrak{I}_{G}(\Omega)$ is an ideal, we have $\mathbf{v}_{\mathcal{S}}\in\mathfrak{I}_{G}(\Omega)$. Thus the EKR-module property is satisfied. ∎

We note that if $\mathcal{S}$ is a maximum intersecting set, then for any $t\in\mathcal{S}$, the set $\mathcal{S}t^{-1}$ is a maximum intersecting set that contains the identity element. So every maximum intersecting set is a “translate” of an intersecting set containing the identity. The following corollary shows that, as far as the EKR-module property is concerned, we can restrict ourselves to maximum intersecting sets containing the identity.

Results from spectral graph theory have proved useful in characterizing maximum intersecting sets in some permutation groups (for instance, see [25], [26], [27]). Let $G$ be a group acting on $\Omega=[G:H]$, for some $H\leq G$. An element $g\in G$ is called a derangement if it does not fix any point in $\Omega$. Let $Der(G,\Omega)$ denote the set of derangements in $G$. It is easy to see that $Der(G,\Omega)=G\setminus\bigcup\limits_{g\in G}gHg^{-1}$. By $\Gamma_{G,\Omega}$, we denote the Cayley graph on $G$, with $Der(G,\Omega)$ as the “connection set”. We now observe that intersecting sets in $G$ are the same as independent sets/co-cliques in $\Gamma_{G,\Omega}$. This observation enables us to use some popular spectral bounds on sizes of independent sets in regular graphs. Before describing these, we recall some standard definitions.

For graph $X$ on $n$ vertices, a real symmetric matrix $M$ whose rows and columns are indexed by the vertex set of $X$, is said to be compatible with $X$, if $M_{u,v}=0$ whenever $u$ is not adjacent to $v$ in $X$. Clearly, the adjacency matrix of $X$ is compatible with $X$. Given a subset $S$ of the vertex set, by $\mathbf{v}_{S}$, we denote the characteristic vector of $S$. We now state the following famous result which is referred to as either the Delsarte-Hoffman bound or the ratio bound.

The application of the above lemma on clever choices of $\Gamma_{G,\Omega}$-compatible matrices, proved useful in characterization of maximum intersecting sets for many permutation groups (for instance see [26] and [27]). We will now describe these in detail.

Let $f$ be a $(G,\Omega)$-compatible class function . Consider the matrix $M^{f}$ indexed by $G\times G$, that satisfies $M^{f}_{g,h}=f(gh^{-1})$ for all $(g,h)\in G\times G$. Clearly $M^{f}$ is a $\Gamma_{G,\Omega}$-compatible matrix. We now describe the spectra of such matrices. The description of spectra of matrices of the form $M^{f}$ is a special case of well-know results by Babai ([5]) and Diaconis-Shahshahani ([10]). The following lemma, which is a special case of Lemma 5 of [10], describes the spectra of matrices of the form $M^{f}$.

We are now ready to give a sufficient condition for EKR-module property in terms of spectra of $\Gamma_{G,\Omega}$-compatible matrices. Let $f:G\to\mathbb{R}$ be a $(G,\Omega)$-compatible class function. Then the row sum of $M^{f}$ is $r_{f}:=\sum\limits_{g\in G}f(g)$. Let $\tau$ be the least eigenvalue of $M^{f}$. By Lemma 3.1, for any intersecting set $S$, we have

Let us assume that equality holds for some intersecting set $\mathcal{S}$. By Lemmas 3.1 and 3.3, if $\mathcal{S}$ is an maximum intersecting set, then $\mathbf{v}_{\mathcal{S}}$ is in the $2$-sided ideal

Now by application of Lemma 2.4, we obtain the following sufficient condition for EKR-module property.

At this point, we remark that the proofs of EKR ([27]) and EKR-module properties ([25]) of $2$-transitive groups, involved finding a class function that satisfies the conditions of Theorem 3.4.

In this section, we prove Theorem 1.6. By Corollary 2.2, we can restrict ourselves to permutation groups that contain a regular normal subgroup. Let $A$ be a finite group and $H\leqslant Aut(A)$. We consider the permutation action of $G:=A\rtimes H$ on $A$, defined by $(a,\sigma)\cdot b=a\sigma(b)$, for all $a,b\in A$ and $\sigma\in H$. It is well-known that any permutation group with a regular normal subgroup, is of the form $G\leqslant\mathrm{Sym}(A)$. By [1, Corollary 2.2], permutation groups which contain a regular subgroup, satisfy the EKR property. Thus the action of $G$ on $A$ satisfies the EKR property.

Before starting the proof, we prove an elementary result that we will use later. Every element of $G$ is of the form $(a,\sigma)$, where $a\in A$ and $\sigma\in H$. Note that $(a,\sigma)(b,\pi)=(a\sigma(b),\sigma\pi)$. We need the following well-known result for technical reasons.

We will now prove the theorem by using Corollary 2.6. Let $\mathcal{S}_{0}$ be any maximum intersecting set with $1_{G}\in\mathcal{S}_{0}$. As $\mathcal{S}_{0}$ is an intersecting set, for all $s\in\mathcal{S}_{0}$, the element $s=s1^{-1}_{G}$ fixes some point. Thus by Lemma 4.1, given $s\in\mathcal{S}_{0}$, there exists a unique element $\sigma_{s}\in H$ and an element $a_{s}\in A$, such that $a_{s}^{-1}sa_{s}=\sigma_{s}\in H$. We now claim that $\{\sigma_{s}\ :\ s\in\mathcal{S}_{0}\}=H$. Since $G$ satisfies the EKR property, we have $|\mathcal{S}_{0}|=|H|$. Therefore, $\{\sigma_{s}:\ s\in\mathcal{S}_{0}\}=H$ is equivalent to injectivity of the map $s\mapsto\sigma_{s}$.

Suppose that for some $s,r\in\mathcal{S}_{0}$, we have $\sigma_{s}=\sigma_{r}$. Then, we have

As $\mathcal{S}_{0}$ is an intersecting set, $sr^{-1}\in A$ fixes a point. Since $A$ acts regularly, we must have $sr^{-1}=1$. Thus $s\mapsto\sigma_{s}$ is injective, and $\{\sigma_{s}:\ s\in\mathcal{S}_{0}\}=H$. As $s\in\mathcal{S}_{0}$ is conjugate to $\sigma_{s}$, for any $\psi\in{\rm Irr}(G)$, we have $\psi(\mathbf{v}_{\mathcal{S}_{0}})=\sum\limits_{s\in\mathcal{S}_{0}}\psi(\sigma_{s})=\psi(\mathbf{v}_{H})$. Therefore, if $\chi\in\{\psi:\ \psi\in{\rm Irr}(G)\ \&\ \psi(\mathbf{v}_{H})=0\}$ and $\mathcal{S}_{0}$ is a maximum intersecting set containing $1_{G}$, we have $\chi(\mathbf{v}_{\mathcal{S}_{0}})=0$. Now, by Corollary 2.6, Theorem 1.6 is proved. ∎

In this section, we study the EKR-module property for primitive permutation groups of rank 3, and prove Theorem 1.7. Let $G$ be a primitive permutation group on $\Omega$ of rank 3. To prove Theorem 1.7, we may assume that $G$ is not an almost simple group. Then either

1. (a)

   $G$ is affine, so that $G$ has a regular normal subgroup, or

2. (b)

   $G$ is in product action, and $G\leqslant T\wr S_{2}$ on $\Omega^{2}$, where $T\leqslant\mathrm{Sym}(\Omega)$ is $2$-transitive.

If $G$ is affine, then $G$ indeed has the EKR-module property by Theorem 1.6. We thus assume further that $G$ is in product action in the rest of this section.

Let $T\leqslant\mathrm{Sym}(\Omega)$ be a $2$-transitive group, and let $H=T_{\omega}<T$, where $\omega\in\Omega$. Let $G=T\wr S_{2}$, and $M=H\wr S_{2}$. Then $G$ naturally acts on $\Omega^{2}$, with $M=G_{(\omega,\omega)}$. Obviously,

are the orbits of $M=G_{(\omega,\omega)}$ on $\Omega^{2}$. Thus $G$ is of rank $3$.

In view of Corollary 2.6, it is beneficial to obtain descriptions of the set ${\rm Irr}(G)$ of irreducible characters of $G$, and of the maximum intersecting sets in $G$ containing the identity. As one would expect, the $2$-transitive action $T$ on $\Omega$ plays a major role. Before going any further, we establish some notation. In $G=T\wr S_{2}=(T\times T)\rtimes S_{2}$, by $\pi$, we denote the unique $2$-cycle in $S_{2}$. Elements of $G\setminus(T\times T)$ are of the form $(s,r)\pi$, where $s,r\in T$. By $(s,r)\pi$, we denote the product of elements $(s,r)$ and $\pi$ of $G$.

We start by describing ${\rm Irr}(G)$. The subgroup $N:=T\times T$ of $G$ is a normal subgroup of index $2$. By Clifford theory ([19, 6.19]), restriction of any irreducible character $\nu\in{\rm Irr}(G)$ to $N$ is either an irreducible $G$-invariant character of $N$, or the sum of two $G$-conjugate irreducible characters of $N$. From well-known results on characters of direct products, we have