INTERSECTION DENSITY OF TRANSITIVE GROUPS
WITH CYCLIC POINT STABILIZERS

Ademir Hujdurovića,b,∗,111The work of Ademir Hujdurović is supported in part
by the Slovenian Research Agency (research program P1-0404 and research
projects J1-7051, N1-0062, J1-9110, J1-1690, J1-1694, J1-1695, N1-0140,
N1-0159, J1-2451, N1-0208)., István Kovács a,b,222The work of István Kovács is
supported in part by the Slovenian Research Agency (research program P1-0285
and research projects N1-0062, J1-9108, J1-1695, N1-0140, J1-2451, N1-0208,
J3-3001)., Klavdija Kutnara,b,333The work of Klavdija Kutnar is supported in
part by the Slovenian Research Agency (research program P1-0285 and research
projects N1-0062, J1-9110, J1-9186, J1-1695, J1-1715, N1-0140, J1-2451,
J1-2481, N1-0209, J3-3001). and Dragan Marušiča,b,c,444 The work of Dragan
Marušič is supported in part by the Slovenian Research Agency (I0-0035,
research program P1-0285 and research projects N1-0062, J1-9108, J1-1695,
N1-0140, J1-2451, J3-3001). *Corresponding author e-mail:
<EMAIL_ADDRESS>
aUniversity of Primorska, UP IAM, Muzejski trg 2, 6000 Koper, Slovenia
bUniversity of Primorska, UP FAMNIT, Glagoljaška 8, 6000 Koper, Slovenia
cIMFM, Jadranska 19, 1000 Ljubljana, Slovenia

###### Abstract

For a permutation group $G$ acting on a set $V$, a subset $\mathcal{F}$ of $G$
is said to be an intersecting set if for every pair of elements
$g,h\in\mathcal{F}$ there exists $v\in V$ such that $g(v)=h(v)$. The
intersection density $\rho(G)$ of a transitive permutation group $G$ is the
maximum value of the quotient $|\mathcal{F}|/|G_{v}|$ where $G_{v}$ is a
stabilizer of a point $v\in V$ and $\mathcal{F}$ runs over all intersecting
sets in $G$. If $G_{v}$ is a largest intersecting set in $G$ then $G$ is said
to have the Erdős-Ko-Rado (EKR)-property. This paper is devoted to the study
of transitive permutation groups, with point stabilizers of prime order with a
special emphasis given to orders 2 and 3, which do not have the EKR-property.
Among other, constructions of infinite family of transitive permutation groups
having point stabilizer of order $3$ with intersection density $4/3$ and of
infinite families of transitive permutation groups having point stabilizer of
order $3$ with arbitrarily large intersection density are given.

> Keywords: intersection density, transitive permutation group, derangement
> graph.

> Math. Subj. Class.: 05C25, 20B25.

##  1 Introductory remarks

The Erdős-Ko-Rado theorem [3], one of the central results in extremal
combinatorics, which gives a bound on the size of a family of intersecting
$k$-subsets of a set and classifies the families satisfying the bound, has
been extended in various ways. This paper is concerned with an extension of
this theorem to the ambient of transitive permutation groups.

For a finite set $V$ let $\hbox{{\rm Sym}}(V)$ denote the corresponding
symmetric group, and if $|V|=n$, the notation $S_{n}$ will be adopted. Given a
permutation group $G\leq\hbox{{\rm Sym}}(V)$, a subset $\mathcal{F}$ of $G$ is
called _intersecting_ if, for any two $g,h\in\mathcal{F}$, there exists $v\in
V$ such that $g(v)=h(v)$. The intersection density $\rho({\cal F})$ of the
intersecting set ${\cal F}$ is defined to be the quotient

$\rho({\cal F})=\frac{|{\cal F}|}{\max\\{|G_{v}|\colon v\in V\\}},$

where $G_{v}$ is the point stabilizer of $v\in V$, and the intersection
density $\rho(G)$ (see [8]) of a group $G$, is the maximum value of
$\rho({\cal F})$ where ${\cal F}$ runs over all intersecting sets in $G$.
Clearly, every coset $gG_{v}$, $v\in V$ and $g\in G$, is an intersecting set,
referred to as a canonical intersecting set. Consequently, $\rho(G)\geq 1$. We
say that $G$ has the _Erdős-Ko-Rado property_ (in short EKR-property), if the
size of a maximum intersecting set is equal to the order of the largest point
stabilizer, and is said to have the _strict Erdős-Ko-Rado property_ (in short
strict-EKR-property) if every maximum intersecting set of $G$ is a coset of a
point stabilizer. It is clear that strict-EKR-property implies EKR-property,
but the converse does not hold. In particular, for a transitive group $G$ it
follows that $\rho(G)=1$ if and only if the maximum cardinality of an
intersecting set is $|G|/|V|$. Note that if $\mathcal{F}$ is an intersecting
set of $G$ and $f\in\mathcal{F}$ then $f^{-1}\mathcal{F}$ is an intersecting
of $G$ (see [4, Proposition 2.3]). Therefore without loss of generality one
can consider those intersecting sets containing the identity. We will refer to
such sets as basic intersecting sets.

The investigation of the EKR-property of transitive permutation groups and
related concepts is an active topic of research (see [4, 5, 6, 8, 13, 14, 16,
15, 18, 19]). This paper initiates a program aimed at obtaining deeper
understanding of transitive permutation groups, not having the EKR-property,
with small point stabilizers. As a starting point we consider groups with
cyclic stabilizers of prime order, in particular those isomorphic to
$\mathbb{Z}_{2}$ and $\mathbb{Z}_{3}$. We remark that in this context the
question on whether their orbitals are connected and self-paired or not is
essential, see Section 2.

The paper is organized as follows. In Section 2 we gather basic definitions
and fix the notation. Section 3 deals with groups having point stabilizers of
order $2$ while Section 4 deals with solvable groups having point stabilizers
of odd prime order. In Section 5 some special results on intersecting sets in
groups with point stabilizer of order $3$ are proved. In Section 6 a
construction of an infinite family of groups with point stabilizer of order
$3$ and intersection density $4/3$ is given. Finally, in Section 7 infinite
families of groups with point stabilizer of order $3$ and arbitrarily large
intersection density are constructed.

##  2 Preliminaries

###  2.1 Permutation groups and orbital digraphs

Let $G\leq\hbox{{\rm Sym}}(V)$. The orbitals of $G$ are the orbits of $V\times
V$ under the canonical action of $G$ on $V\times V$. The set
$\Delta^{*}:=\\{(u,v)\colon(v,u)\in\Delta\\}$ is also an orbital, and in the
case when $\Delta=\Delta^{*}$, $\Delta$ is called self-paired. Supppose that
$G$ is transitive. Then the set $\\{(v,v)\colon v\in V\\}$ is an orbital, and
any orbital distinct from this is called non-trivial. For a non-trivial
orbital $\Delta$, let $\Gamma_{\Delta}$ be the digraph with vertex set $V$ and
arc set $\Delta$, that is, the so-called orbital digraph
$\Gamma_{\Delta}=\Gamma(G,\Delta)$ of $G$ relative to $\Delta$. We say that
$\Delta$ is connected if so is the associated digraph $\Gamma_{\Delta}$, that
is, for any two vertices $u$ and $v$, there is a sequence of vertices
$u=w_{1},w_{2},\ldots,w_{k}=v$ such that for every $1\leq i\leq k-1$,
$(w_{i},w_{i+1})\in\Delta$ or $(w_{i+1},w_{i})\in\Delta$. Using a standard
terminology, for a prime $p$ a $p$-element is an element of order a power of
$p$.

###### Proposition 2.1

Let $G\leq\hbox{{\rm Sym}}(V)$ be a transitive permutation group and let
$\Delta$ be a non-trivial orbital containing the pair $(u,v)$. Then

  1. (i)

$\Delta$ is self-paired if and only if there exists a $2$-element $g\in G$
such that $g(u)=v$ and $g^{2}\in G_{u}$,

  2. (ii)

$\Delta$ is connected if and only if $G=\langle G_{u},g\rangle$ for every
$g\in G$ with $g(u)=v$.

Let $H$ be a point stabilizer and $\Delta$ an orbital of a transitive
permutation group $G$. Then it is well-known that the orbital digraph
$\Gamma_{\Delta}=\Gamma(G,\Delta)$ corresponds to the so-called double coset
graph $\textrm{Cos}(G,H,HgH)$, where $g\in G$ such that $(u,u^{g})\in\Delta$
and $H=G_{u}$. In general, for a subset $S\subseteq G$, the double coset graph
is defined to have vertex set $G/H$ (the set of left cosets of $H$ in $G$) and
arc set consisting of pairs $(xH,yH)$, $x,y\in G$ and $x^{-1}y\in HSH$.

We end this subsection with a result about quotient graphs of arc-transitive
graphs which will be needed in Section 4. For terms not defined here we refer
the reader to [11] (see also [9]).

###### Proposition 2.2

[11, Lemma 2.5] Let $\Gamma$ be a connected $G$-arc-transitive graph of
valency $p$ for an odd prime $p$, and let $N\lhd\hbox{{\rm Aut}}\,(\Gamma)$ be
a semiregular subgroup with at least $3$ orbits. Then $\Gamma_{N}$ is a
connected $\bar{G}$-arc-transitive graph of valency $p$, where $\bar{G}$ is
the image of $G$ under its action on $V(\Gamma_{N})$.

###  2.2 Derangement graphs

Let $G\leq\hbox{{\rm Sym}}(V)$. The fixed-point-free elements of $G$ are also
called derangements. Following [16], the derangement graph of $G$ is defined
to be the Cayley graph $\Gamma_{G}=\hbox{{\rm Cay}}(G,\mathcal{D})$ with
vertex set $G$ and edge set consisting of all pairs $(g,h)\in G\times G$ such
that $g^{-1}h\in\mathcal{D}$, where $\mathcal{D}$ is the set of all
derangements of $G$. Clearly, $\mathcal{D}$ is closed under conjugation by
elements of $G$, which shows that $\mathrm{Inn}(G)\leq\hbox{{\rm
Aut}}\,(\Gamma_{G})$, where $\mathrm{Inn}(G)$ denotes the group of all inner
automorphisms of $G$. The lemma below gives an additional kind of
automorphisms of a derangement graph.

###### Lemma 2.3

For every $G\leq\hbox{{\rm Sym}}(V)$, the inverse map $\iota:G\to G$ defined
by $\iota(g)=g^{-1}$ $(g\in G)$ is an automorphism of the derangement graph
$\Gamma_{G}$.

Proof.  Suppose that $x$ and $y$ are two non-adjacent vertices of
$\Gamma_{G}$. Then there exists points $v,u\in V$ such that $x(v)=u=y(v)$.
Clearly, $x^{-1}(u)=v=y^{-1}(u)$, implying that $x^{-1}$ and $y^{-1}$ are also
non-adjacent in $\Gamma_{G}$.

In the terminology of derangement graphs, an intersecting set of a transitive
permutation group $G$ is an independent set of $\Gamma_{G}$, or equivalently,
a clique of its complement $\overline{\Gamma_{G}}$. Therefore,
$\rho(G)=\omega(\overline{\Gamma_{G}})/|G_{v}|,$ where the clique number
$\omega(\overline{\Gamma_{G}})$ is the size of a maximum clique of
$\overline{\Gamma_{G}}$. In the special case with stabilizers of order $2$ or
$3$, the complement of the derangement graph is arc-transitive.

###### Lemma 2.4

Let $G$ be a transitive group with point stabilizers of order $2$ or $3$. Then
the complement $\overline{\Gamma_{G}}$ is arc-transitive.

Proof.  Observe that $\overline{\Gamma_{G}}=\hbox{{\rm Cay}}(G,\mathcal{S})$
where $\cal{S}$ is the set of all non-identity elements of $G$ that fix a
point. As $G$ is transitive, its point stabilizers are conjugate. Thus
$\mathcal{S}=C\cup C^{-1}$, where $C$ is the conjugacy class of some $g\in G$
fixing a point. Using the fact that $\mathrm{Inn}(G)\leq\hbox{{\rm
Aut}}\,(\overline{\Gamma_{G}})$ and that $\iota\in\hbox{{\rm
Aut}}\,(\overline{\Gamma_{G}})$, we obtain that the stabilizer of the identity
element $1=1_{G}$ of $G$ in $\hbox{{\rm Aut}}\,(\overline{\Gamma_{G}})$ acts
transitively on $\cal{S}$. Hence $\overline{\Gamma_{G}}$ is arc-transitive.

For a prime power $q$ with $q\equiv 1\pmod{4}$, the Paley graph $P_{q}$ is
defined to be the Cayley graph of $\mathbb{F}_{q}^{+}$, the additive group of
the finite field $\mathbb{F}_{q}$ with $q$ elements, whose connection set
consists of all non-zero squares in $\mathbb{F}_{q}$.

###### Proposition 2.5

[2, Theorem 1] Let $q=p^{2n}$ where $p$ is a prime such that $q\equiv
1\pmod{4}$. Then $\omega(P_{q})=\sqrt{q}$.

###  2.3 Intersection density

In this subsection we list four results from [4].

###### Proposition 2.6

([4, Proposition 2.6]) Let $G$ be a transitive permutation group containing a
semiregular subgroup $H$ with $k$ orbits. Then $\rho(G)\leq k$. In particular,
if $H$ is regular then $\rho(G)=1$.

###### Proposition 2.7

[4, Proposition 3.1] Let $G$ be a transitive permutation group admitting a
semiregular subgroup $H$ whose orbits form a $G$-invariant partition
$\mathcal{B}$, and let $\bar{G}$ be the image of $G$ under its action on
$\mathcal{B}$. Then $\rho(G)\leq\rho(\bar{G})$.

###### Proposition 2.8

[4, Theorem 1.4] For a transitive permutation group $G$ of prime power degree
the intersection density $\rho(G)$ is equal to $1$.

We end this subsection with a lemma that can be extracted from the proof of
[4, Theorem 1.5]

###### Lemma 2.9

[4] Let $p$ be a prime and let $G$ be a transitive permutation group of degree
$2p$. If $G$ admits $G$-invariant partition $\mathcal{B}$ consisting of two
blocks then $\rho(G)=1$.

###  2.4 Properties of $\hbox{\rm PSL}(2,q)$

We will need two well-known results about the group $\hbox{\rm PSL}(2,q)$. The
first one can be easily derived from the structure of subgroups of $\hbox{\rm
PSL}(2,q)$ (see, for example, [20]), so we omit the proof. For the second one
we refer the reader to [12].

###### Proposition 2.10

Let $q=3^{n}$ and $n>1$. Then $\hbox{\rm PSL}(2,q)$ has one conjugacy class of
subgroups of order $3$ if $n$ is odd, and two otherwise.

###### Proposition 2.11

[12] Unless $q=9$ the group $\hbox{\rm PSL}(2,q)$ is generated by an element
of order $2$ and an element of order $3$.

Finally, it is known that if $F$ is an algebraic closed field of
characteristic $p$ and $A\in\hbox{\rm SL}(2,F)$ such that $A$ is not in the
center $Z=Z(\hbox{\rm SL}(2,F))$, then $A^{3}\in Z$ if and only if $\hbox{{\rm
Tr}}(A)$ is either $1$ or $-1$ (see [20, (6.19) in Chapter 3]). This implies
the following statement.

###### Proposition 2.12

Let $A\in\hbox{\rm SL}(2,q)$ be a matrix such that $A\neq\pm I$. Then
$A^{3}=\pm I$ if and only if its trace $\hbox{{\rm Tr}}(A)$ is either $1$ or
$-1$.

###### Proposition 2.13

Let $q=p^{k}$ for a prime $p$, $p\neq 3$. Further let $G=\mathrm{PSL}(2,q)$ be
considered in its transitive action on the cosets of a subgroup isomorphic to
$\mathbb{Z}_{3}$. Then a non-canonical basic intersecting set in $G$ contains
no point stabilizer as a proper subset.

Proof.  Let us assume that there is an intersecting set $\mathcal{F}$ in $G$
containing $I$, $B$, $B^{2}$ and $C$, where $B$ and $C$ are two elements of
order $3$ in $G$ such that $C\not\in\\{B,B^{2}\\}$.

Consider the above two elements $B$ and $C$ in $G$ as ‘matrices’, that is
elements in $\mathrm{SL}(2,q)$. Then the minimal polynomial $m_{B}(x)$ of $B$
is either $x^{2}+x+1$ or $x^{2}-x+1$, depending on whether $B^{3}=I$ or
$B^{3}=-I$ in $\mathrm{SL}(2,q)$. If $m_{B}(x)=x^{2}+x+1$ consider the product
$C(I+B+B^{2})$. We have

$\mathbf{0}=C\cdot\mathbf{0}=C(I+B+B^{2})=CI+CB+CB^{2}.$

Consequently, the sum of traces $Tr(CI)$, $Tr(CB)$ and $Tr(CB^{2})$ equals
zero. However, by our assumption each of $C$, $CB$ and $CB^{2}$ is an element
of order $3$, and therefore its trace (as an ‘element’ of $\mathrm{SL}(2,q)$)
is either $1$ or $-1$. Therefore, since $p\neq 3$, the sum of these three
traces cannot be equal to zero. The argument in case when $m_{B}(x)=x^{2}-x+1$
is analogous. We just have to consider the expression $C(I-B+B^{2})$,
completing the proof of Proposition 2.13.

##  3 Groups with point stabilizers of order $2$

###### Lemma 3.1

Let $G$ be a transitive group with point stabilizers of order $2$, and let
$\mathcal{F}$ be a basic intersecting set. Then $\langle\mathcal{F}\rangle$ is
an elementary abelian $2$-group.

Proof.  Let $x,y\in\mathcal{F}$ be distinct and non-identity. Since $x$ and
$y$ are intersecting with the identity, it follows that each fixes a point,
hence has order $2$. Moreover, since $x$ and $y$ are intersecting, it follows
that $x^{-1}y=xy$ is also of order $2$, which implies that $x$ and $y$
commute.

In the next proposition we provide some sufficient condition for the EKR
property of a transitive group with point stabilizers of order $2$.

###### Proposition 3.2

A transitive group $G$ with point stabilizers of order $2$ has the EKR
property if

  1. (i)

$G$ has a cyclic Sylow $2$-subgroup, or

  2. (ii)

$G$ is a nilpotent group.

Proof.  Part (i) is a direct consequence of Lemma 3.1.

To show part (ii) we proceed by induction on the number of prime divisors of
$|G|$. If $G$ is a $2$-group, then the statement follows from Proposition 2.8.
Assume that $|G|$ is divisible by an odd prime $p$, and let $P$ be a Sylow
$p$-subgroup of $G$. Then $P\lhd G$ because $G$ is nilpotent. As $P$ is also
semiregular, Proposition 2.7 can be applied with $\mathcal{B}$ being the set
of $P$-orbits. It follows that $\rho(G)\leq\rho(\bar{G})$, where $\bar{G}$ is
the image of $G$ under its action on $\mathcal{B}$. Moreover, $\bar{G}$ is
transitive with point stabilizers of order $2$, it is also nilpotent with the
smaller number of prime divisors than $|G|$. Hence the induction hypothesis
yields $\rho(\bar{G})=1$, and (ii) follows.

It can be deduced from Lemma 3.1 that a maximal intersecting set of transitive
group with point stabilizer of order $2$ cannot have size $3$. Namely, if
$\mathcal{F}=\\{1,x,y\\}$ is an intersection set, then it is easy to see that
so is $\\{1,x,y,xy\\}$. Nonetheless, the example below shows that maximum
intersecting sets in transitive groups with stabilizers of order $2$ can have
any size $d\geq 2$ and $d\neq 3$.

###### Example 3.3

Let $G=E\rtimes Q$ be the semidirect product of the group $E=\langle
e_{1},\ldots,e_{n}\rangle\cong\mathbb{Z}_{2}^{n}$ with the group $Q=\langle
a,b\rangle$, where the action of $a$ and $b$ by conjugation on $E$ is defined
by

$e_{i}^{a}=\begin{cases}e_{i+1}&\text{if}~{}1\leq i\leq n-1\\\ e_{1}&\text{if
}~{}i=n.\end{cases},\quad e_{i}^{b}=\begin{cases}e_{i}e_{n}&\text{if}~{}1\leq
i\leq n-1\\\ e_{n}&\text{if}~{}i=n.\end{cases}$

Consider the permutation group induced by the action of $G$ on the cosets of
$\langle e_{1}\rangle$.

It is easy to check that the conjugacy class of $G$ containing $e_{1}$ is
equal to the set $C:=\\{e_{i},e_{i}e_{j}:1\leq i,j\leq n\\}$. This shows that
the set $\\{1,e_{1},\ldots,e_{n}\\}$ is an intersecting set. We prove that, if
$\mathcal{F}$ is an arbitrary intersecting set, then $|\mathcal{F}|\leq n+1$.
We may assume without loss of generality that $1\in\mathcal{F}$, hence
$\mathcal{F}\setminus\\{1\\}\subset C$. Write

$\mathcal{F}_{1}=\mathcal{F}\cap\\{e_{i}:1\leq i\leq
n\\}~{}\text{and}~{}\mathcal{F}_{2}=\mathcal{F}\cap\\{e_{i}e_{j}:1\leq i,j\leq
n\\}.$

Note that, from the set theoretic point of view the sets $\\{i,j\\}$,
$e_{i}e_{j}\in\mathcal{F}$, form a classical intersecting family of
$\\{1,\ldots,n\\}$, hence $|\mathcal{F}_{2}|\leq n-1$. On the other hand, it
is easy to see that $|\mathcal{F}_{1}|\leq 1$ if $|\mathcal{F}_{2}|\geq 2$.
All these yield that $|\mathcal{F}|\leq n+1$.

We remark that the group $G$ above admits no connected orbitals. If that was
not the case then $G=\langle e_{1},g\rangle$ would hold for some element $g\in
G$ due to Proposition 2.1(ii). But then $G=\langle E,g\rangle=E\rtimes\langle
g\rangle$, so $Q$ is a cyclic group, contradicting the fact that $ab\neq ba$.

We conclude this subsection with a connection to character theory. In fact,
the EKR property of a given transitive group $G$ with stabilizers of order $2$
can be read off the character table of $G$.

###### Proposition 3.4

Let $G$ be a transitive group with point stabiliers of order $2$. Then $G$ has
the EKR property if and only if

$\sum_{\chi}\frac{\chi(g)^{3}}{\chi(1)}=0.$

where $\chi$ runs though the set of all irreducible characters of $G$, and $g$
is any non-identity element of $G$ fixing a point.

Proof.  Let $C_{1},\ldots,C_{r}$ be the conjugacy classes of $G$ and let
$a_{ijk}$ be the class algebra constants of $G$, that is, for $1\leq i,j,k\leq
r$,

$\underline{C}_{i}\,\underline{C}_{j}=\sum_{k=1}^{r}a_{ijk}\underline{C}_{k}$

holds in the group algebra $\mathbb{C}G$ (see [10, Chapter 30]). For a subset
$X\subseteq G$, $\underline{X}$ stands for the element $\sum_{g\in G}a_{g}g$
with $a_{g}=1$ if $g\in X$, and $a_{g}=0$ otherwise. Then we have

$a_{ijk}=\frac{|G|}{|C_{G}(g_{i})||C_{G}(g_{j})|}\sum_{\chi}\frac{\chi(g_{i})\chi(g_{j})\overline{\chi(g_{k})}}{\chi(1)},$
(1)

where $g_{i}\in C_{i},g_{j}\in C_{j}$ and $g_{k}\in C_{k}$, and $\chi$ runs
through the set of all irreducible characters of $G$ (see [10, Theorem 30.4]).
Now, take $g_{1}$ to be $g$. It is clear that having the EKR property is the
same as requiring $a_{111}=0$, so the proposition follows directly from (1).

##  4 Solvable groups with point stabilizers of odd prime order

We start by observing that solvable transitive permutation groups with point
stabilizers of prime order and admitting a connected self-paired orbital have
the EKR property. This is a consequence of the following more general result
formulated in a graph-theoretic language.

###### Proposition 4.1

Let $p$ be a prime, $\Gamma$ be a connected $p$-valent arc-transitive graph,
and let $G\leq\hbox{{\rm Aut}}\,(\Gamma)$ be a solvable group acting
transitively on arcs of $\Gamma$. Then $G$ has the EKR property.

Proof.  Assume first that $p=2$. Then $\Gamma$ is a cycle, and so $G$ contains
a regular subgroup, and thus Proposition 2.6 implies that $G$ has the EKR
property.

Assume from now on that $p$ is an odd prime. Assume on the contrary that
$\rho(G)>1$ with $\Gamma$ being the smallest counterexample. In other words,
if $\tilde{\Gamma}$ is a connected $p$-valent $\tilde{G}$-arc-transitive graph
for some solvable group $\tilde{G}$ and $|V(\tilde{\Gamma})|<|V(\Gamma)|$,
then $\rho(\tilde{G})=1$.

Let $N$ be a minimal normal subgroup of $G$. Then $N\cong\mathbb{Z}_{r}^{l}$
for some prime $r$ and $l\geq 1$. If $N$ is transitive, then it is regular,
but this contradicts the fact that $\rho(G)>1$ in view of Proposition 2.7.

If $N$ has more than $2$ orbits, by Proposition 2.2, $\Gamma_{N}$ is a
connected $p$-valent $\bar{G}$-arc-transitive graph with $\bar{G}\cong G/N$,
where $\bar{G}$ is the image of $G$ under its action on the orbits of $N$. The
group $\bar{G}$ is solvable, hence by the minimality of $\Gamma$,
$\rho(\bar{G})=1$. On the other hand, by Proposition 2.7,
$1<\rho(G)\leq\rho(\bar{G})$, a contradiction.

It remains to consider the case when $N$ has two orbits. If $N$ is
semiregular, then the image of the action of $G$ on the two $N$-orbits is
$S_{2}$, hence by Proposition 2.7, $1<\rho(G)\leq\rho(S_{2})=1$, again a
contradiction. If $N$ is not semiregular, then it is easy to show that $r=p$,
$N\cong\mathbb{Z}_{p}^{2}$ and $\Gamma=K_{p,p}$. Clearly the bipartition sets
of $\Gamma$ form a block system for $G$. It follows then from Lemma 2.9 that
$\rho(G)=1$, a contradition, completing the proof of Proposition 4.1.

In the example below we show that the above proposition does not extend to
solvable transitive permutation groups with the point stabilizer of order $p$
but without connected self-paired orbitals. These groups act on edge-
transitive graphs, first studied by Praeger and Xu [17].

###### Example 4.2

Let $G=\mathrm{AGL}(1,q)$, where $q=p^{e}$, $p$ an odd prime and $e>1$. Then
$G$ consists of the linear transformations $x\mapsto ax+b$, where
$a\in\mathbb{F}_{q}^{*}$ and $b\in\mathbb{F}_{q}$. Fix non-zero elements
$a,b\in\mathbb{F}_{q}$ such that $a$ is a primitive element, and let
$\sigma:x\mapsto x+b$ and $\tau:x\mapsto ax$. Note that
$\langle\sigma,\tau\rangle=G$. Then let $\Gamma$ be the double coset graph
$\mathrm{Cos}(G,H,H\\{\tau,\tau^{-1}\\}H)$, where $H=\langle\sigma\rangle$. It
follows from basic properties of double coset graphs (see, for example, [7,
Lemma 2.1]) that $\Gamma$ is a connected $G$-edge-transitive graph. It is easy
to see that $H\tau H\neq H\tau^{-1}H$ (the corresponding orbitals are non-
self-paired), hence, by [7, Lemma 2.4], $\Gamma$ has valency $2|H|/|H\cap
H^{\tau}|=2p$. The conjugacy class of $G$ containing $\sigma$ consists of all
transformations $x\mapsto x+u$, $u\neq 0$. Consequently, these transformations
together with the identity form an intersecting set, and so $\rho(G)>1$. Note
also that a self-paired orbital of the action of $G$ on
$H=\langle\sigma\rangle$ is necessarily disconnected.

##  5 Intersecting sets in groups with point stabilizers of order $3$

In view of Proposition 4.1, in order to construct transitive permutation
groups having point stabilizers of prime order $p$ admitting a connected self-
paired orbital and without EKR-property, nonsolvable groups need to be brought
into consideration. Hereafter, we restrict ourselves to $p=3$. The lemma below
gives a lower bound on the cardinality of a maximal intersecting set
containing a point stabilizer in a transitive group with point stabilizer of
order $3$.

###### Lemma 5.1

Let $G$ be a transitive permutation group. Let $H,K\leq G$ such that $H\cup K$
is an intersecting set. Then $HK$ is also an intersecting set.

Proof.  Since $H\cup K$ is an intersecting set, it follows that $hk$ and $kh$
fixes a point for each $h\in H$ and $k\in K$. Hence $1$ is adjacent with every
element of $HK$ in $\overline{\Gamma_{G}}$. Let $hk$, $h_{1}k_{1}$ be
arbitrary in $HK$. By $\sim$ we denote the adjacency relation in
$\overline{\Gamma_{G}}$. Then we have

$\displaystyle hk\sim h_{1}k_{1}$ $\displaystyle\Leftrightarrow k\sim
h^{-1}h_{1}k_{1}\textrm{ (Using left multiplicaiton by }h^{-1}\textrm{which is
an automorphism})$ $\displaystyle\Leftrightarrow k^{-1}\sim
k_{1}^{-1}h_{1}^{-1}h\textrm{ (Using the inversion automorphism})$
$\displaystyle\Leftrightarrow 1\sim kk_{1}^{-1}h_{1}^{-1}h\textrm{ (Using left
multiplicaiton by }k)$ $\displaystyle\Leftrightarrow 1\sim
k^{\prime}h^{\prime}.$

Observe that $k^{\prime}h^{\prime}$ is adjacent with $1$ in
$\overline{\Gamma_{G}}$ for every $h^{\prime}\in H$ and every $k^{\prime}\in
K$ since $H\cup K$ is an intersecting set in $G$. This shows that $HK$ is a
clique in $\overline{\Gamma_{G}}$.

###### Proposition 5.2

Let $G$ be a transitive group acting on a set $V$, with point stabilizer
$H=\langle x\rangle\cong\mathbb{Z}_{3}$ of order $3$, and admitting a maximal
intersecting set $\mathcal{F}$ containing $H$ as a proper subset. Then

  1. (i)

$|\mathcal{F}|\geq 9$.

  2. (ii)

For every $y\in\mathcal{F}\setminus H$, the group $\langle x,y\rangle$ is
isomorphic either to $\mathbb{Z}_{3}^{2}$ or to the unique non-abelian group
of order $27$ with exponent $3$.

Proof.  By assumption there exists $y\in\mathcal{F}\setminus H$. It follows
that $\\{1,x,x^{2},y\\}$ is a clique in $\overline{\Gamma_{G}}$. Since, by
Lemma 2.3, the mapping $\iota:g\mapsto g^{-1}$ ($g\in G$) is an automorphism
of $\overline{\Gamma_{G}}$, it follows that $\\{1,x,x^{2},y,y^{2}=y^{-1}\\}$
is an intersecting set of $G$, and so (i) follows by Lemma 5.1.

As for part (ii), let $P=\langle x,y\rangle$. If $z=[x,y]=1$, then clearly
$P\cong\mathbb{Z}_{3}^{2}$. Hence assume that $z\neq 1$. We show that
$[x,z]=[y,z]=1$. It follows from $(x^{2}y)^{3}=1$ that
$y^{2}xy^{2}=x^{2}yx^{2}$ and from $(xy)^{3}=1$ that $x^{2}y^{2}x^{2}=yxy$ and
$(yx)^{2}=x^{2}y^{2}$. Using these we compute

$z^{x}=x[x,y]x^{2}=y^{2}xyx^{2}=(y^{2}xy^{2})y^{2}x^{2}=x^{2}y(x^{2}y^{2}x^{2})=x^{2}y^{2}xy=z,$
$z^{y}=y[x,y]y^{2}=yx^{2}y^{2}x=yx(xy^{2}x)=yxyx^{2}y=(yx)^{2}xy=x^{2}y^{2}xy=z.$

Since $xz=y^{2}xy$ is a conjugate of $x$ it has order $3$, and since
$[x,z]=1$, we conclude that so does $z$. It follows that $\langle
z\rangle\cong\mathbb{Z}_{3}$, $P/\langle z\rangle\cong\mathbb{Z}_{3}^{2}$, and
therefore, $P$ is isomorphic to the unique non-abelian group of order $27$
with exponent $3$.

###### Corollary 5.3

Let $G$ be a transitive group acting on a set $V$, with point stabilizer of
order $3$, and admitting a maximal basic intersecting set $\mathcal{F}$ of $G$
such that $|\mathcal{F}|=4$. Then no point stabilizer $G_{v}$, $v\in V$, is
contained in $\mathcal{F}$. In other words, $\mathcal{F}=\\{1,x,y,z\\}$ with
$x$, $y$ and $z$ belonging to different point stabilizers.

###### Example 5.4

There exists a connected cubic symmetric graph of order $720$ with
automorphism group $A$ of order $2160$. Using MAGMA [1], one can obtain that
the group $A$ is isomorphic to $(3\cdot A_{6})\rtimes\mathbb{Z}_{2}$, where
$3\cdot A_{6}$ denotes the triple cover of $A_{6}$. Let $P$ be a Sylow
$3$-subgroup of $A$. Then $P\cong\langle a,b,c\mid
a^{3}=b^{3}=c^{3}=1,[a,b]=c,[a,c]=1,[b,c]=1\rangle$ is the unique non-abelian
group of order $27$ with exponent $3$. Again, we established with MAGMA that
maximum intersecting sets of $A$ are of size $9$ and furthermore every maximum
intersecting set of $A$ containing identity is contained in $P$ or one of its
$10$ conjugates in $A$. All non-central elements of order $3$ from $P$ are
conjugate in $A$, and the subgraph of the derangement graph of $A$ induced by
these $24$ non-central elements of $P$ is a disjoint union of 8 triangles of
the form $\\{x,xc,xc^{2}\\}$, with $x$ a non-central element of $P$. Then the
maximum intersecting sets containing $1$ that lie inside $P$ are just the
transversals of $\langle c\rangle=Z(P)$ in $P$. Observe that there are $3^{8}$
such transversals. Consequently, all possibilities between $0$ and $4$ full
vertex-stabilizers, contained in such a maximum intersecting set of $A$, can
occur.

##  6 Groups with point stabilizer of order $3$ and intersection density $4/3$

In this section we give an infinite family of transitive permutation groups
with intersection density $4/3$. These groups arise from the groups $\hbox{\rm
PSL}(2,q)$ acting on cosets of a subgroup of order $3$. In view of Proposition
2.13, the corresponding non-canonical basic intersecting sets are of the form
$\\{1,x,y,z\\}$ where $x$, $y$ and $z$ are from different point stabilizers.

###### Theorem 6.1

Let $p$ be a prime, let $q=p^{e}\equiv 1\pmod{3}$, and let $G$ be a transitive
permutation group arising from $\hbox{\rm PSL}(2,q)$ acting on cosets of a
subgroup of order $3$. Then

$\displaystyle\rho(G)$ $\displaystyle=$
$\displaystyle\begin{cases}4/3&\text{if }p\neq 5,\\\ 2&\text{if
}p=5.\end{cases}$ (2)

Proof.  Observe that all cyclic subgroups of order $3$ are conjugate in
$\hbox{\rm PSL}(2,q)$, while the elements of order $3$ form two conjugacy
classes, with two elements $x$ and $x^{-1}$ of order $3$ belonging to
different conjugacy classes. In $\hbox{\rm PGL}(2,q)$, however, these two
conjugacy classes merge into a single class. Consequently, every element of
order $3$ in $\hbox{\rm PSL}(2,q)$ belongs to a point stabilizer (with regards
to the action considered in this theorem).

Let $\Gamma$ be the subgraph of the complement of the derangement graph
$\Gamma_{G}$ of $G$ induced by the set of neighbours of the identity element
of $G$. In other words, the vertices of $\Gamma$ are the elements of order
$3$, with $h,g$ adjacent if and only if $h^{-1}g$ is of order $3$. Since a
clique in $\Gamma$ together with the identity element gives rise to an
intersecting set for $G$, the statement (2) will be proved if we show that

$\omega(\Gamma)=\begin{cases}3&\text{if }p\neq 5,\\\ 5&\text{if
}p=5,\end{cases}$ (3)

where $\omega(\Gamma)$ denotes the clique number of $\Gamma$.

As before we will think of elements of $\hbox{\rm PGL}(2,q)$ as ‘matrices’,
that is, as elements of $\hbox{\rm GL}(2,q)$. Note that, $A,B\in\hbox{\rm
SL}(2,q)$ represent the same element in $\hbox{\rm PSL}(2,q)$ if and only if
$B=-A$.

In view of the observation made in the first paragraph, the action of
$\hbox{\rm PGL}(2,q)$ on $V(\Gamma)$ by conjugation is transitive, and the
corresponding image is therefore a transitive subgroup of $\hbox{{\rm
Aut}}\,(\Gamma)$. In particular, every vertex of $\Gamma$ is contained in a
maximum clique. Let us fix the vertex

$A_{0}=\left[\begin{array}[]{cc}r&0\\\ 0&r^{2}\end{array}\right],$

where $r^{3}=1$ and $r\neq 1$. The existence of such an $r$ is guaranteed by
the condition $q\equiv 1\pmod{3}$. Let $\mathcal{K}$ be a maximum clique
containing $A_{0}$. The vertex stabilizer of $A_{0}$ in $\hbox{\rm PGL}(2,q)$
coincides with the centralizer $\Lambda=\\{L_{a}:a\in\mathbb{F}_{q}^{*}\\}$ of
$A_{0}$ in $\hbox{\rm PGL}(2,q)$, isomorphic to $\mathbb{Z}_{q-1}$, where

$L_{a}:=\left[\begin{array}[]{cc}a&0\\\ 0&1\end{array}\right],\
a\in\mathbb{F}_{q}^{*}.$

We now show that the neighborhood $\Gamma(A_{0})$ splits into the following
$\Lambda$-orbits: $\\{A_{0}^{-1}\\},~{}O_{1},~{}O_{1}^{\prime}$ and $O_{2}$ if
$p\neq 2$, and $\\{A_{0}^{-1}\\},~{}O_{1}$ and $O_{1}^{\prime}$ if $p=2$,
where

$\displaystyle O_{1}$ $\displaystyle=$
$\displaystyle\big{\\{}A_{x}=\left[\begin{array}[]{cc}-r^{2}&x\\\
0&-r\end{array}\right]:x\in\mathbb{F}_{q}^{*}\big{\\}},$ $\displaystyle
O_{1}^{\prime}$ $\displaystyle=$
$\displaystyle\big{\\{}A_{x}^{T}:x\in\mathbb{F}_{q}^{*}\big{\\}},$
$\displaystyle O_{2}$ $\displaystyle=$
$\displaystyle\Big{\\{}B_{x}=\left[\begin{array}[]{cc}\frac{r}{r-1}&-2x\\\
\frac{1}{3x}&\frac{-1}{r-1}\end{array}\right]:x\in\mathbb{F}_{q}^{*}\Big{\\}}.$

It is clear that $A_{0}$ and $A_{0}^{-1}$ are adjacent in $\Gamma$. In view of
Proposition 2.12, we may choose $A\in\Gamma(A_{0})\setminus\\{A_{0}^{-1}\\}$
with $\hbox{{\rm Tr}}(A)=1$. Then $A=\left[\begin{array}[]{cc}a&b\\\
c&d\end{array}\right]$ for some $a,b,c,d\in\mathbb{F}_{q}$ with $ad-bc=1$ and
$a+d=1$. Also, $\hbox{{\rm Tr}}(A_{0}^{-1}A)=r^{2}a+rd=\pm 1$.

Suppose first that $p\neq 2$. Using the fact that $a+d=1$, we have
$(r^{2}-r)a=\pm 1-r$. If $(r^{2}-r)a=1-r$, then we have $a=-r^{2}$, $d=-r$,
and $bc=ad-1=0$. If $c=0$, then $A\in O_{1}$, and if $b=0$, then $A\in
O_{1}^{\prime}$. Suppose now that $(r^{2}-r)a=-1-r=r^{2}$. Then we have that
$a=r/(r-1)$, $d=-1/(r-1)$, and $bc=ad-1=-r/(r-1)^{2}-1=-r/(-3r)-1=-2/3$. It
follows that $A\in O_{2}$. We have therefore shown that
$\Gamma(A_{0})=\\{A_{0}^{-1}\\}\cup O_{1}\cup O_{1}^{\prime}\cup O_{2}$.

Suppose now that $p=2$. Then $r^{2}a+rd=1$, and since $d=1-a$ it follows that
$a=(r+r^{2})a=r+1=r^{2}$, $d=r$ and $bc=0$. We obtain that
$\Gamma(A_{0})=\\{A_{0}^{-1}\\}\cup O_{1}\cup O_{1}^{\prime}$.

Straightforward computations show that, for every $x\in\mathbb{F}_{q}^{*}$,

$A_{x}=L_{x}A_{1}L_{x}^{-1},~{}A_{x}^{T}=L_{x}^{-1}A_{1}^{T}L_{x},~{}\text{and}~{}B_{x}=L_{x}B_{1}L_{x}^{-1}.$

Thus each of $O_{1}$, $O_{1}^{\prime}$ and $O_{2}$ is a $\Lambda$-orbit, as
claimed. It can be directly checked that for every $x\in\mathbb{F}_{q}^{*}$

$A_{x}^{-1}=\begin{bmatrix}-r&-x\\\
0&-r^{2}\end{bmatrix}~{}\text{and}~{}B_{x}^{-1}=\begin{bmatrix}\frac{r+2}{3}&2x\\\
-\frac{1}{3x}&\frac{2r+1}{3r}\end{bmatrix}.$

Using these, the traces $\hbox{{\rm Tr}}(XY)$ for
$X\in\\{A_{x}^{-1},(A_{x}^{T})^{-1},B_{x}^{-1}\\}$ and
$Y\in\\{A_{y},A_{y}^{T},B_{y}\\}$ can be computed directly. The results are
collected in Table 1. In particular, $A_{1}$ and $A_{1}^{T}$ are adjacent, and
so $|\mathcal{K}|\geq 3$. Combining this with Proposition 2.13 we have that
$A_{0}^{-1}\notin\mathcal{K}$.

| $A_{y}$ | $A_{y}^{T}$ | $B_{y}$
---|---|---|---
$A_{x}^{-1}$ | $2$ | $2-xy$ | $-\frac{x}{3y}$
$(A_{x}^{T})^{-1}$ | $2-xy$ | $2$ | $2xy$
$B_{x}^{-1}$ | $-\frac{y}{3x}$ | $2xy$ | $\frac{2}{3}\Big{(}1+\frac{x}{y}+\frac{y}{x}\Big{)}$
Table 1: The traces $Tr(XY)$,
$X\in\\{A_{x}^{-1},(A_{x}^{T})^{-1},B_{x}^{-1}\\}$ and
$Y\in\\{A_{y},A_{y}^{T},B_{y}\\}$.

Assume for the moment that $\mathcal{K}\setminus\\{A_{0}\\}$ is not contained
in $O_{2}$. It is easy to show that the mapping $\tau:X\mapsto X^{T}$, $X\in
V(\Gamma)$, is an automorphism of $\Gamma$. This automorphism fixes $A_{0}$
and $A_{0}^{-1}$, swaps $O_{1}$ with $O_{1}^{\prime}$, and maps $O_{2}$ onto
itself. Thus $\langle\Lambda,\tau\rangle$ is transitive on $O_{1}\cup
O_{1}^{\prime}$, and so we may, without loss of generality, assume that
$A_{1}\in\mathcal{K}$. Now, if $A\in\mathcal{K}\setminus\\{A_{0},A_{1}\\}$
then $\hbox{{\rm Tr}}(A_{1}^{-1}A)=\pm 1$. Using Table 1, we find
$A\in\\{A_{1}^{T},A_{3}^{T},B_{1/3},B_{-1/3}\\}$ if $p\neq 2$, and
$A=A_{1}^{T}$ if $p=2$. This shows that
$\mathcal{K}=\\{A_{0},A_{1},A_{1}^{T}\\}$ if $p=2$. Let $p\neq 2$. If $p\neq
5$, then using Table 1 again, we obtain that no two vertices in the set
$\\{A_{1}^{T},A_{3}^{T},B_{1/3},B_{-1/3}\\}$ are adjacent, and hence
$|\mathcal{K}|=3$. If $p=5$, then a direct computation yields
$\mathcal{K}=\\{A_{0},A_{1},A_{1}^{T},B_{1/3},B_{-1/3}\\}$, and so
$|\mathcal{K}|=5$.

Observe that the above arguments show that $\omega(\Gamma)=3$ for $p=2$, as
claimed in (3). It remains to consider the case $p\neq 2$ and
$\mathcal{K}\setminus\\{A_{0}\\}\subseteq O_{2}$. As $O_{2}$ is a
$\Lambda$-orbit, we may assume that $B_{1}\in\mathcal{K}$. Also, assume that
$B_{z}\in\mathcal{K}$ for $z\neq 1$. Then $(\hbox{{\rm
Tr}}(B_{1}^{-1}B_{z})-1)(\hbox{{\rm Tr}}(B_{1}^{-1}B_{z})+1)=0$ holds. Using
Table 1, we find that $z$ is a root of the polynomial

$\displaystyle
f(x)=\Big{(}x^{2}-\frac{1}{2}x+1\Big{)}\Big{(}x+2\Big{)}\Big{(}x+\frac{1}{2}\Big{)}.$
(6)

If $p=5$ then $x^{2}-\frac{1}{2}x+1=(x+1)^{2}$, $x+\frac{1}{2}=x+3$, and so
$z\in\\{2,3,4\\}$. Consequently,
$\mathcal{K}=\\{A_{0},B_{1},B_{2},B_{3},B_{4}\\}$, $|\mathcal{K}|=5$, and
$\omega(\Gamma)=5$, as claimed in (3). Suppose now that $p\neq 5$ and that
there exists a root $w$ of $f(x)$, $w\notin\\{1,z\\}$, such that
$B_{w}\in\mathcal{K}$. Then, by Table 1, we have

$\frac{2}{3}\Big{(}1+\frac{z}{w}+\frac{w}{z}\Big{)}=\pm 1.$ (7)

We complete the proof of Theorem 6.1 by showing that (7) together with the
fact that $z$ and $w$ are roots of the polynomial $f(x)$ given in (6) leads to
a contradiction. We go through all possibilities for $z$ and $w$.

If $z=-2$ and $w=-1/2$ then (7) yields $15=0$ or $27=0$ in $\mathbb{F}_{q}$, a
contradiction.

If $z=-2$ and $w^{2}-1/2w+1=0$ then (7) implies $2-4/w-w=\pm 3$, and so $w=-2$
or $w=2/3$. Hence, $6=0$ or $10=0$, a contradiction.

If $z=-1/2$ and $w^{2}-1/2w+1=0$ then (7) implies $2-1/w-4w=\pm 3$, and so
$w=1$ or $w=-1$. Hence $3=0$ or $5=0$, a contradiction.

Finally, if $z,w$ are both roots of $x^{2}-1/2x+1$ then $zw=1$ and $z+w=1/2$,
and so $1+z^{2}+w^{2}=-3/4$. Dividing both sides with $zw=1$, we have
$1+z/w+w/z=-3/4$. Combining this with (7), we conclude that $-3/4=\pm 3/2$, a
contradiction, completing the proof of Theorem 6.1.

##  7 Groups with point stabilizer of order $3$ and large intersection density

In the example below, using an action of the symmetric group $S_{n}$, $n\geq
4$, we show that maximum intersecting sets in transitive groups with point
stabilizers of order $3$ can be arbitrarily large.

###### Example 7.1

Let $n\geq 4$. First observe that for two $3$-cycles $x=(i\,j\,k),y\in S_{n}$
we have that $x^{-1}y$ is also a $3$-cycle if and only if $y=(i\,k\,j)$ or
$y\in\\{\,(i\,j\,l),~{}(j\,k\,l),~{}(k\,i\,l)\colon 1\leq l\leq
n-1,l\notin\\{i,j,k\\}\,\\}.$

Let $G$ be the permutation group induced by the action of $S_{n}$ on cosets of
$\langle(1\,2\,3)\rangle$. We show that a maximum intersecting set of $G$ has
size $n-1$. Let $\Gamma$ be the complement of the derangement graph of $G$.
Observe that the set of neighbours of $id$ in $\Gamma$ is the set of all
$3$-cycles from $S_{n}$. Let $\Gamma_{1}$ be the subgraph of $\Gamma$ induced
by the set of common neighbours of $id$ and $(1\,2\,3)$. In view of the first
paragraph it follows that
$V(\Gamma_{1})=\\{(1\,3\,2\\}\cup\\{(1\,2\,i),(2\,3\,i),(3\,1\,i):i\in\\{4,5,\ldots,n\\}\\}$.
Furthermore, it follows that the set $\\{(1\,2\,i):i\in\\{4,5,\ldots,n\\}\\}$
induces a clique in $\Gamma_{1}$. Analogously, the sets
$\\{(2\,3\,i):i\in\\{4,5,\ldots,n\\}\\}$ and
$\\{(3\,1\,i):i\in\\{4,5,\ldots,n\\}\\}$ also induce cliques. Moreover, there
are no other edges in $\Gamma_{1}$, that is, $\Gamma_{1}$ is a disjoint union
of an isolated vertex (corresponding to $(1\,3\,2)$) and three cliques of size
$n-3$. Consequently, $\omega(\Gamma_{1})=n-3$. A clique in $\Gamma$ is
therefore obtained from $id$, $(1\,2\,3)$ and any of these three maximum
cliques in $\Gamma_{1}$. In view of arc-transitivity of $\Gamma$, it follows
that $\omega(\Gamma)=2+n-3=n-1$. Hence, $\rho(G)=\omega(\Gamma)/3=(n-1)/3$.

The simplicity of this construction is a consequence of the fact that the
existence of a connected self-paired orbital was not required (see the first
paragraph of Section 4). With this additional restriction the problem of
finding such groups becomes somewhat more complicated. In the theorem below we
give such a construction using the group $\hbox{\rm PSL}(2,3^{n})$ for $n\geq
3$. The group $\hbox{\rm PSL}(2,9)$ is not considered here because none of its
orbitals in the action on cosets of a subgroup of order $3$ is self-paired and
connected. This is a direct consequence of the fact that, by Proposition 2.11,
$\hbox{\rm PSL}(2,9)$ cannot be generated by an involution and an element of
order $3$. However, by Proposition 2.11, for $n\geq 3$ the group $\hbox{\rm
PSL}(2,3^{n})$ is generated by an involution and an element of order $3$, and
thus the theorem below indeed gives transitive permutation groups with point
stabilizer of order $3$ having connected self-paired orbital.

###### Theorem 7.2

Let $G$ be a transitive permutation group arising from $\hbox{\rm
PSL}(2,3^{n})$, $n\geq 3$, acting on cosets of a subgroup of order $3$. Then

$\displaystyle\rho(G)$ $\displaystyle=$
$\displaystyle\begin{cases}3^{n-1}&\text{if $n$ is odd},\\\ 3^{n/2-1}&\text{if
$n$ is even}.\end{cases}$ (8)

Proof.  Consider the subgroup $K$ of $\hbox{\rm PSL}(2,3^{n})$ consisting of
matrices

$M_{x}=\left[\begin{array}[]{cc}1&x\\\ 0&1\end{array}\right],\
x\in\mathbb{F}_{3^{n}},$

(where a matrix is a ‘matrix’ as in the proof of Theorem 6.1).

Observe that $K\cong\mathbb{Z}_{3}^{n}$ is a Sylow $3$-subgroup of $\hbox{\rm
PSL}(2,3^{n})$. Observe also that $K$ consists precisely of those elements of
$\hbox{\rm PSL}(2,3^{n})$ fixing the subspace $\langle[1,0]^{T}\rangle$. There
are $3^{n}+1$ conjugates of $K$, each conjugate corresponding to a Sylow
$3$-subgroup of the stabilizer of some projective point. In what follows, we
shall consider the action of $\hbox{\rm PSL}(2,3^{n})$ on the projective line,
whose points are the one dimensional subspaces $\langle[a,b]^{T}\rangle$,
$a,b\in\mathbb{F}_{q}$.

Suppose first that $n$ is odd. Then, by Proposition 2.10 any two subgroups of
order $3$ in $\hbox{\rm PSL}(2,3^{n})$ are conjugate. Let $\Gamma$ be the
subgraph of the complement of the derangement graph of $G$ induced by the
neighbours of the identity matrix $I\in G$. The vertex set $V(\Gamma)$ can be
partitioned into $3^{n}+1$ cliques, each of size $3^{n}-1$, corresponding to
$K\setminus\\{I\\}$ and its conjugates.

Consider a neighbour of $M_{x}$ outside of $K$. (Note that, since Sylow
3-subgroups of $\hbox{\rm PSL}(2,3^{n})$ and $\hbox{\rm PGL}(2,3^{n})$ are of
the same order, all elements of order $3$ are contained in $\hbox{\rm
PSL}(2,3^{n})$.) We can assume that this neighbour is of the form
$A=\left[\begin{array}[]{cc}a&b\\\ c&1-a\end{array}\right]$. Using the
assumption that $M_{x}^{2}A$ is an elements of order $3$, it follows that its
trace must be equal to $\pm 1$. If $2cx+1=1$, it follows that $c=0$, but this
would imply that $A$ is in $K$, a contradiction. Hence $2cx+1=-1$, and we
obtain that $c=-1/x$. This implies that all neighbours of $M_{x}$ outside of
$K$ have the entry in the first column and second row equal to $-1/x$.
Consequently, no two different elements of $K$ have a common neighbour outside
of $K$. This shows that given an edge of $K$, the maximum clique that contains
this edge is the one induced by $K$. Hence, the maximum clique of $\Gamma$ can
be the one induced by $K$, or it can consist of at most one element from each
of the conjugates of $K$. Since there are $3^{n}+1$ such conjugates, it
follows that $\omega(\Gamma)\leq 3^{n}+1$. Adding the identity, which is not
in $\Gamma$, it follows that $\rho(G)\leq(3^{n}+2)/3$.

Let $q=3^{n}$, and let $K=K_{0},K_{1},\ldots,K_{q}$ be the conjugates of
$K_{0}$, where we may assume that $K_{1}$ consists of lower triangular
matrices with 1 on diagonal fixing the projective point corresponding to
$\langle[0,1]^{T}\rangle$. Suppose that there exists a maximal clique
$\mathcal{K}$ of $\Gamma$ not contained in $K_{i}$ for any $i$ and such that
$|\mathcal{K}|\geq 3^{n}$. By the argument from the first paragraph, we know
that $|\mathcal{K}\cap K_{i}|\leq 1$, for each $i$, and so we may assume that
$\mathcal{K}\cap K_{i}=\emptyset$ for at most one $i\in\\{0,1,\ldots,q\\}$.
Since $\hbox{\rm PSL}(2,q)$ acts $2$-transitively on projective points, we may
assume, without loss of generality, that $\mathcal{K}\cap K_{0}\neq\emptyset$
and that $\mathcal{K}\cap K_{1}\neq\emptyset$.

Let $A_{0}=M_{x}$. By calculation we see that the only neighbour of $A_{0}$ in
$K_{1}$ is $A_{1}=\left[\begin{array}[]{cc}1&0\\\ 1/x&1\end{array}\right]$.
Let $A=\left[\begin{array}[]{cc}a&b\\\ c&1-a\end{array}\right]$ be a common
neighbour of $A_{0}$ and $A_{1}$. Observe that $\hbox{{\rm
Tr}}(A_{0}^{2}A)=2cx+1$ and $\hbox{{\rm Tr}}(A_{1}^{2}A)=\frac{2b}{x}+1$.
Using the assumption that $A_{0}^{2}A$ and $A_{1}^{2}A$ are elements of order
$3$, it follows that their traces must be equal to $\pm 1$, implying that
$c=-1/x$ and $b=-x$. Hence

$A=\begin{bmatrix}a&-x\\\ \frac{-1}{x}&1-a\end{bmatrix}.$

Since $det(A)=a-a^{2}-1$, and since $A$ is in $\hbox{\rm PSL}(2,q)$, it
follows that $a-a^{2}-1=\pm 1$. There are at most $4$ elements $a$ in
$\mathbb{F}_{q}$ that satisfy this equation. It follows that for a fixed
$x\in\mathbb{F}_{q}^{*}$ there are at most four possibilities for the matrix
$A$, and therefore $A_{0}$ and $A_{1}$ can have at most 4 common neighbours,
that is the clique containing the edge $\\{A_{0},A_{1}\\}$ can have size at
most $6$. Since $3^{n}-1>6$, it follows that $\omega(\Gamma)=3^{n}-1$. This
shows that $\rho(G)=3^{n}/3=3^{n-1}$.

Suppose now that $n$ is even. The elements $M_{x}$ of $K$ split into two
conjugacy classes, depending on whether $x$ is a square in
$\mathbb{F}_{3^{n}}^{*}$ or a non-square. It is easy to see that the subgraph
of $\overline{\Gamma_{G}}$ induced by $K$ is isomorphic to the Paley graph or
its complement. Combining Proposition 2.5 with the fact that the Paley graph
and its complement are isomorphic we obtain that a maximum clique of the
latter graph $\overline{\Gamma_{G}}[K]$ is of size $3^{n/2}$. Using the same
argument as for $n$ odd we obtain that a clique in $\overline{\Gamma_{G}}$
that is not contained inside $K_{i}$, $i\in\\{0,1,\ldots,q\\}$ can have size
at most $6$. Since $n\geq 4$, it follows that $3^{n/2}\geq 9$, and so the
clique number of $\overline{\Gamma_{G}}$ is $3^{n/2}$, implying that
$\rho(G)=3^{n/2-1}$.

As a final remark regarding possible future work, we would like to pose the
following problem which generalizes the results of this paper for cyclic
groups of orders $2$ and $3$.

###### Problem 7.3

Given a group $H$ determine all possible intersection densities of transitive
permutation groups having point stabilizers isomorphic to $H$.

## References

  * [1] W. Bosma, J. Cannon, and C. Playoust, The Magma Algebra System I: The User Language, J. Symbolic Comput. 24 (1997) 235–265.
  * [2] I. Broere, D. Döman, J. N. Ridley, The clique numbers and chromatic numbers of certain Paley graphs, Quaestiones Math. 11 (1988), no. 1, 91–93.
  * [3] P. Erdős, C. Ko and R. Rado, Intersection theorems for systems of finite sets, Quart. J. Math. Oxford Ser. 12 (1961), 313–320.
  * [4] A. Hujdurović, K. Kutnar, D. Marušič and Š. Miklavič, Intersection density of transitive groups of certain degrees, to appear in Algebraic Combin., arXiv preprint arXiv:2104.04699, 2021.
  * [5] A. Hujdurović, K. Kutnar, D. Marušič and Š. Miklavič, On maximum intersecting sets in direct and wreath product of groups, arXiv:2108.03943 [math.CO].
  * [6] A. Hujdurović, K. Kutnar, B. Kuzma, D. Marušič, Š. Miklavič, and M. Orel, On intersection density of transitive groups of degree a product of two odd primes, Finite Fields and Their Appl. 78 (2022), 101975
  * [7] C. H. Li, Z. P. Lu and D. Marušič, On primitive permutation groups with small suborbits and their orbital graphs, J. Algebra 279 (2004), 749–770
  * [8] C. H. Li, S. J. Song, and V. R. T. Pantangi, Erdős-Ko-Rado problems for permutation groups, 2021, https://arxiv.org/abs/arXiv:2006.10339.
  * [9] P. Lorimer, Vertex-transitive graphs: symmetric graphs of prime valency, J. Graph Theory 8 (1984), 55–68.
  * [10] G. James and M. Liebeck, Representations and characters of groups - second edition, Cambridge University Press, 2001.
  * [11] C. H. Li and J. Pan, Finite 2-arc-transitive abelian Cayley graphs, European J. Combin. 29 (2008), 148–158.
  * [12] A. M. Machbet, Generators of the linear fractional groups, Proc. Sympos. Pure Math. 12 (1967), 14–32.
  * [13] K. Meagher, An Erdős-Ko-Rado theorem for the group PSU(3,q), Des. Codes Cryptogr. 87 (2019), no. 4, 717–744.
  * [14] K. Meagher, A. S. Razafimahatratra, The Erdős-Ko-Rado theorem for 2-pointwise and 2-setwise intersecting permutations, Electron. J. Combin. 28 (2021), no. 4, Paper No. 4.10.
  * [15] K. Meagher, P. Sin, All 2-transitive groups have the EKR-module property, J. Combin. Theory Ser. A 177 (2021), Paper No. 105322.
  * [16] K. Meagher, A. S. Razafimahatratra and P. Spiga, On triangles in derangement graphs, J. Combin. Theory, Ser. A 180 (2021), 105390.
  * [17] C. E. Praeger and M.-Y. Xu, A characterisation of a class of symmetric graphs of twice prime valency, European J. Combin. 10 (1989), 91–102.
  * [18] A. S. Razafimahatratra, On multipartite derangement graphs, Ars Math. Contemp. 21 (2021), $\\#P1.07$.
  * [19] P. Spiga, The Erdős-Ko-Rado theorem for the derangement graph of the projective general linear group acting on the projective spac, J. Combin. Theory Ser. A 166 (2019), 59–90.
  * [20] M. Suzuki, Group Theory I, Springer-Verlag, 1982.