\documentclass[ALCO, Unicode,published]{cedram}
\usepackage{amscd}
\usepackage{latexsym}
%\usepackage{txfonts}
\usepackage{hyperref}
\newcommand{\bb}{\mathbb}
\newcommand{\mrm}{\mathrm}
\newcommand{\mf}{\mathfrak}
\newcommand{\ov}{\overline}
\newcommand{\Sym}{\mathrm{Sym}}
\newcommand{\Der}{\mathfrak{Der}}
\newcommand{\I}{\mathcal{S}}
\newcommand{\In}{\mathfrak{I}}
\newcommand{\Ome}{\Omega}
\newcommand{\ch}{\mathbf{v}}
\newcommand{\Irr}{{\rm Irr}}
\title{On the EKR-module property}
\author[\initial{C-H} Li]{\firstname{Cai-Heng} \lastname{Li}}
\address{SUSTech International Center for Mathematics\\
Department of Mathematics\\
Southern University of Science and Technology\\
Shenzhen, Guangdong 518055\\
P. R. China}
\email{lich@sustech.edu.cn}
\author[\initial{V.R.T} Pantangi]{\firstname{Venkata Raghu Tej} \lastname{Pantangi}}
\address{Department of Mathematics and Computer Science\\
University of Lethbridge\\
Lethbridge, Alberta T1K 3M4\\
Canada}
\email{pvrt1990@gmail.com}
\curraddr{Department of Mathematics and Statistics\\
University of Regina\\
Regina, Saskatchewan S4S 0A2\\
Canada
}
\thanks{This work was partially supported by NSFC grant 11931005 to the first author. The second author is supported by the PIMS postdoctoral fellowship.}
\keywords{Erd\H{o}s--Ko--Rado theorems, permutation groups, EKR-module property, derangement graphs}
\subjclass{05D99, 05E18, 05E30}
\datepublished{2024-04-29}
\begin{document}
\newtheorem{problem}[cdrthm]{Problem}
\begin{abstract}
In recent years, the generalization of the Erd\H{o}s--Ko--Rado (EKR) theorem to permutation groups has been of much interest. A transitive group is said to satisfy the \emph{EKR-module property} if the characteristic vector of every maximum intersecting set is a linear combination of the characteristic vectors of cosets of stabilizers of points. This generalization of the well-known permutation group version of the Erd\H{o}s--Ko--Rado (EKR) theorem was introduced by K. Meagher in \cite{PSUEKR}. In this article, we present several infinite families of permutation groups satisfying the EKR-module property, which shows that permutation groups satisfying this property are quite diverse.
\end{abstract}
\maketitle
\section{Introduction}
The Erd\H{o}s--Ko--Rado (EKR) theorem \cite{EKR1961} 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 \binom{n-1}{k-1}$.
Moreover in the case $n>2k$, if $|\mathfrak{S}|=\binom{n-1}{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 $\binom{n-1}{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 forms of intersection.
One such generalization, given by Frankl and Wilson \cite{FW1986}, 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 \cite{GMbook} 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 \cite{DF1977}, who investigated families of pairwise \emph{intersecting} permutations.
Two permutations $\sigma, \tau \in S_{n}$ are said to {\it intersect} if the permutation $\sigma\tau^{-1}$ fixes a point.
A set of permutations is called an {\it 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 \cite{DF1977}, it was shown that if $\I$ is a family of pairwise intersecting permutations, then $|\I| \leq (n-1)!$. In the same paper, it was conjectured that if the equality $|\I|=(n-1)!$ is met, then $\I$ has to be a coset of a point stabilizer. This conjecture was proved by Cameron and Ku (see \cite{CK2003}). An independent proof was given by Larose and Malvenuto (see \cite{LM2004}). Later, Godsil and Meagher (see \cite{GM2009}) 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 \emph{intersecting} subset of $G$ with respect to this action is a subset $\I\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 \emph{canonical} intersecting sets.
An intersecting set of maximum possible size is called a \emph{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.
\begin{defi}
A transitive group $G$ on $\Omega$ is said to satisfy the {\it EKR} property if every intersecting set has size at most $|G|/|\Omega|$, and further said to satisfy the {\it strict-EKR} property if every maximum intersecting set is canonical.
\end{defi}
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 \cite{AM2014,AM2015,LPSX2018, MSi2019, MS2011, MST2016}).
In particular, it was shown that all $2$-transitive group actions satisfy the EKR property, see \cite[Theorem 1.1]{MSi2019}, but not every 2-transitive group satisfies the strict-EKR property; for instance, with respect to the $2$-transitive action of $\mrm{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 \cite{MSi2019} 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
\[\ch_{S}=\sum\limits_{s \in S} s \in \bb{C}G,\]
the characteristic vector of $S$ in the group algebra $\bb{C}G$.
For $\alpha, \beta \in \Omega$ and $g\in G$ with $g\cdot \alpha=\beta$, we write
\[\ch_{\alpha,\beta}=\sum_{\substack{ t \in G\\ t\cdot\alpha= \beta}} t=\sum\limits_{x\in G_\alpha}{gx}=g\sum\limits_{x\in G_\alpha}x=\ch_{gG_\alpha},\]
the characteristic vector of the canonical intersecting set $gG_\alpha$, which we call a {\it canonical vector} for convenience.
The next definition was first introduced in \cite{PSUEKR}.
\begin{defi}
A finite transitive group $G$ on a set $\Omega$ is said to satisfy the {\it EKR-module property} if the characteristic vector of each maximum intersecting set of $G$ on $\Ome$ is a linear combination of canonical vectors, that is, the vectors in $\{\ch_{\alpha,\beta}\mid \alpha,\beta \in \Ome\}$.
\end{defi}
The name is from the so called ``module method'' described in \cite{ahmadi2015erdHos}.
We remark that
\begin{enumerate}[(a)]
\item a group action satisfying the strict-EKR property also satisfies the EKR-module property, but the converse statement is not true;
\item and there exist group actions that satisfy the EKR-module property but not the EKR property, see \cite[Theorem 5.2]{meagher2021triangles}, and the following Example~\ref{ex:A_4};
\end{enumerate}
\begin{exam}\label{ex:A_4}
Consider the action of $A_{4}$ on the set $\Omega$ of cosets of a subgroup $H \cong \bb{Z}_{2}$. We observe that the Sylow 2-subgroup $N$ of $A_{4}$ is an intersecting set. As $4=|N|>|A_{4}/|\Omega|=2$, this action does not satisfy the EKR property.
Consider an intersecting set $\I$. Then given $t\in \I$, the set $\I t^{-1}$ is an intersecting set containing the identity. By the definition of an intersecting set, we have $\I t^{-1} \subset \bigcup\limits_{g \in A_{4}}gHg^{-1}=N$. This shows that any maximum intersecting set must be coset of $N$. Any coset of $N$ is a union of two disjoint cosets of $H$, and thus this action satisfies the EKR-module property.
\end{exam}
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 $\Ome$. A subset $R\subset G$ is said to be a \emph{regular subset}, if for any $(\alpha,\ \beta) \in \Ome^2$, there is a unique $r \in R$ such that $r\cdot \alpha =\beta$. Corollary 2.2 of \cite{AM2015} states that permutation groups which contain a regular subset, satisfy the EKR property.
For a group $G$ and a subgroup $H\leqslant G$, let
\[[G:H]=\{xH\mid x\in G\},\]
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.
\begin{exam}\label{cex}
Consider $G=S_{5}$ (isomorphic to $\mrm{PGL}(2,5)$) and a subgroup $H\leq G$ isomorphic to the dihedral group of size 12. We consider the action of $G$ on $\Omega=[G :H]$. We first show that this action satisfies the EKR property, by demonstrating the existence of a regular subset. We consider the cyclic subgroup $C:=\left\langle(1,2,3,4,5)\right\rangle$ and the $4$-cycle $t :=(2,3,5,4)$. We claim that $R := C \cup tC$ is a regular set. As $|R|=|\Omega|$, this claim will follow by showing that for $r,s \in R$ with $r\neq s$, we have $rgH \neq sgH$, for all $g \in G$. This is equivalent to showing that $g^{-1}r^{-1}sg \notin H$, for all $g \in G$. It is easy to verify that for any two distinct $r,s\in R$ , $r^{-1}s$ is either a $4$-cycle or a $5$-cycle, and thus $g^{-1}r^{-1}sg \notin H$. We can now conclude that $R$ is a regular subset. Therefore, by \cite[Corollary 2.2]{AM2015}, $G$ satisfies the EKR property. Thus the size of any intersecting set is bounded above by $|H|=12$.
Now we consider subgroup $K \cong A_{4}$ of $G$. It is easy to check that $KK^{-1}=K \subset \cup gHg^{-1}$ and thus $K$ is a maximum intersecting set. In this case, canonical intersecting sets are cosets of a conjugate of $H$. Every canonical intersecting set contains exactly $3$ even permutations. Also every permutation in $K$ is even. Now consider the sign character $\lambda$. For every canonical intersecting set $\I$, we have $\lambda(\ch_{S})=0$. On the other hand, we have $\lambda(\ch_{K})\neq 0$. From this, we see that $\ch_{K}$ cannot be a linear combination of the characteristic vectors of the canonical intersecting sets. Therefore this action does not satisfy the EKR-module property.
\end{exam}
We will now describe the main results of our paper.
\subsection{Main results}
Our first result is a characterization of the EKR-module property of a group action, in terms of the characters of the group in question. Given a group $G$, a complex character $\chi$ of $G$, and a subset $A \subseteq G$, by $\chi(\ch_{A})$, we denote the sum $\sum\limits_{a\in A}\chi(a)$. We now describe our first result, a characterization of the EKR-module property in terms of character sums.
\begin{theorem}\label{idekrm}
Let $G$ be a finite group, $Hs$ be the other eigenvalues.
Our proof uses some results on graphs in association schemes. For a quick introduction to the preliminaries on graphs in association schemes, we refer the reader to Chapter 3 of \cite{GMbook}.
We first recall the following well-known result linking strongly regular graphs with association schemes.
By $J$ and $I$, we denote the all-one matrix and the identity matrix respectively.
\begin{lemma}[{\cite[Lemma 5.1.1]{GMbook}}] Let $X$ be a graph with $A$ as its adjacency matrix. Then $X$ is strongly regular if and only if $\mathcal{A}_{X}:=\{I,\ A,\ \ov{A}:=J-I-A\}$ is an association scheme.
\end{lemma}
By $\bb{C}[\mathcal{A}_{X}]$, we denote the linear span of matrices in $\mathcal{A}_{X}$. This is referred to as the Bose-Mesner algebra. By a well-known result (\cite[Theorem 3.4.4]{GMbook}), the projections onto eigenspaces of $A$ is an orthogonal basis of idempotents of $\bb{C}[\mathcal{A}_{X}]$. The matrix $J$ is the projection onto the $k$-eigenspace. We denote $E_{r}$ and $E_{s}$ to be the projections onto the $r$-eigenspace and the $s$-eigenspace respectively. We have $A=kJ+rE_{r}+sE_{s}$, $I=\frac{J}{n}+E_{r}+E_{s}$, and so $\{\frac{J}{n},\ E_{r},\ E_{s}\}$ is an orthogonal basis of idempotents of $\bb{C}[\mathcal{A}_{X}]$. We now mention a bound by Delsarte (see equation $(3.25)$ of \cite{delsarte1973algebraic}) on cliques in strongly regular graphs. We state the formulation of this result as given in \cite[Corollary 3.7.2]{GMbook}.
\begin{lemma}\label{godsilub}
Let $X$ be $k$-regular strongly regular graph with $s$ as the least eigenvalue of its adjacency matrix. If $C$ is a clique in $X$, then $|C| \leqslant 1-\frac{k}{s}$.
Moreover, if $C$ is a clique that meets the bound with equality, then the characteristic vector $\ch_{C}$ is orthogonal to the $s$-eigenspace.
\end{lemma}
Given a subset $B$ of the vertex set of $X$, by $\ch_{B}$, we denote the characteristic vector of $B$, and by $\mathbf{1}$, the all-one vector. Consider the $\bb{C}$-linear span $V_{max}$ of characteristic vectors of maximum cliques in $X$. By the above lemma, we have $|C| \leq 1-\frac{k}{s}$, for any clique $C$. Assume that there is a clique $C$ of size $1-\frac{k}{s}$, then by the above Lemma, $V_{max}$ is orthogonal to the $s$-eigenspace. We will now show that $V_{max}$ is in the image of $\frac{J}{n}+E_{r}$.
\begin{lemma}\label{evec}
Let $X$ be $k$-regular strongly regular graph on $n$ vertices with $\{k,\ r,\ s\}$ with $r>s$ as set of distinct eigenvalues of its adjacency matrix. If $X$ has a clique of size $1-\frac{k}{s}$, then $\ch_{C}-\frac{|C|}{n}\mathbf{1}$ is an $r$-eigenvector.
\end{lemma}
\begin{proof}
From Lemma~\ref{godsilub}, we have $E_{s}\ch_{S}=0$. As $\mathbf{1}$ is a $k$-eigenvector, it is also orthogonal to the $s$-eigenspace. Since $J \ch_{C} = |C| \mathbf{1}$, the vector $\ch_{C}-\frac{|C|}{n}\mathbf{1}$ is orthogonal to both the $k$-eigenspace and the $s$-eigenspace, and so must lie in the $r$-eigenspace.
\end{proof}
We are now ready to prove Theorem~\ref{EKRP}.
\vskip0.1in
\begin{proof}[Proof of Theorem~\ref{EKRP}]
Let $X$ be a Peisert-type graph of type $(m,q)$ whose connection set is $S=\bigcup\limits_{i=0}^{m-1} c_{i}\bb{F}^{\times}_{q}$ (with $c_{0}=1$).
By Lemmas~\ref{par}, \ref{godsilub} and \ref{evec}, we obtain the next result.
\begin{lemma}
If $C$ is a maximum clique in $X$, then $|C|=q$ and $\ch_{C}-\frac{1}{q}\mathbf{1}$ is a $(q-m)$-eigenvector.
\end{lemma}
Thus, given $x \in \bb{F}_{q^{2}}$ and $0\leq i \leqslant m-1$, the canonical clique $c_{i}\bb{F}_{q}+x$ is a maximum clique and $\ch_{c_{i},x}:=\ch_{c_{i}\bb{F}_{q}+x}-\frac{1}{q}\mathbf{1}$ is a $(q-m)$-eigenvector. By Lemma~\ref{par}, the dimension of the $(q-m$)-eigenspace is $m(q-1)$. Using the above Lemma, we can now deduce that Theorem~\ref{EKRP} follows from showing that $\{\ch_{c_{i},x}\ : \ x \in \bb{F}_{q^{2}}\ \&\ 0\leqslant i \leqslant m-1\}$ spans an $m(q-1)$ dimensional vector space.
Given an additive character $\chi$ of $\bb{F}_{q^{2}}$, we set $\ch_{\chi}:=\sum\limits_{z\in \bb{F}_{q^{2}}}\chi(z)z$.
In the proof of Lemma~\ref{par}, we see that the $(q-m)$-eigenspace $V_{q-m}$, is spanned by
$$\{\ch_{\chi}: \ \text{ $\chi$ is non-trivial and $c_{i}\bb{F}_{q} \subseteq \ Ker(\chi)$ for some $0\leqslant i \leqslant m-1$}\}.$$
Let $E_{i}= \left\langle\{v_{\chi}\ :\ \bb{F}_{q^{2}}\supsetneq Ker(\chi) \supset c_{i}\bb{F}_{q}\} \right\rangle$.
Then we have
$$V_{q-m}=\bigoplus E_{i}.$$
By $\left[\ ,\ \right]$, we denote the natural orthogonal form on $\bb{C}[\bb{F}_{q^{2}}]$.
With respect to this form, we have $E^{\perp}_{i}= \bigoplus\limits_{j\neq i}E_{j}$.
If $\chi$ is a non-trivial character, then
$$\left[ \ch_{\chi}, \ch_{c_{i},x} \right] = \chi(x)\sum\limits_{z\in c_{i}\bb{F}_{q}}\chi(z).$$
Therefore, $\ch_{c_{i},x} \in E_{i}$ for all $x\in \bb{F}_{q^{2}}$.
We will now show that vectors of the form $\ch_{c_{i},x}$ span $E_{i}$.
Considering $x\in \bb{F}^{\times}_{q^{2}}$ and $f_{i,x}:= \ch_{c_{i},\ 0}- \ch_{c_{i},\ x}= \ch_{c_{i}\bb{F}_{q}}-\ch_{c_{i}\bb{F}_{q}+x}$.
As the set $\{\ch_{c_{i}F_{q}+x}\ : \ x\in \bb{F}_{q^{2}}\}$ is a set of $q$ orthogonal vectors, the set $\{f_{i,x}: \ x\neq 0\}$ spans a $q-1$ dimensional vector space.
Therefore $\{\ch_{c_{i},x}: \ x \in \bb{F}_{q^{2}}\}$ spans $E_{i}$.
Thus $\{\ch_{c_{i},x}: \ x \in \bb{F}_{q^{2}}\ \&\ 0\leqslant i \leqslant m-1\}$ spans $V_{q-m}=\bigoplus E_{i}$.
This concludes the proof of Theorem~\ref{EKRP}. \qedhere
\end{proof}
\section{Conclusion and further work}\label{final}
We end this paper with some directions for future research. Theorem $4.5$ of \cite{ahmadi2015erdHos}, provides a sufficient condition for a $2$-transitive group to satisfy the strict-EKR property. They refer to this as the \emph{module method}. EKR-module property of $2$-transitive groups is a key result that makes this method work. It is now natural to ask the following question.
\begin{problem}
Find a condition under which EKR-module property implies the strict-EKR property. More specifically, generalize Ahmadi and Meagher's module method to group actions satisfying the EKR-module property.
\end{problem}
After finding a strong characterization of intersecting sets in $2$-transitive groups, the authors of \cite{MSi2019}, noted that investigating intersecting sets in rank $3$ group actions is a natural progression.
\begin{problem}
(1) Which rank $3$ group actions satisfy the EKR property?
(2) Which rank $3$ group actions satisfy the EKR-module property?
(3) Which rank $3$ group actions satisfy the strict-EKR property?
\end{problem}
Theorem~\ref{Rank3} reduces (1) and (2) of the above problem to the following two classes: (a) primitive rank $3$ actions of almost simple groups and (b) imprimitive rank $3$ actions. We end by noting that, a classification of primitive rank $3$ actions of almost simple groups is well known (see \cite{eiichi1972maximal, kantor1982rank, liebeck1986finite}). In \cite{Alice}, a classification of imprimitive rank $3$ group actions was achieved.
\bibliographystyle{mersenne-plain}
\bibliography{ALCO_Pantangi_778}
\end{document}