ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 21 (2021) #P1.07 / 89–103
https://doi.org/10.26493/1855-3974.2554.856
(Also available at http://amc-journal.eu)
On complete multipartite derangement graphs*
Andriaherimanana Sarobidy Razafimahatratra
Department of Mathematics and Statistics, University of Regina
Regina, Saskatchewan S4S 0A2, Canada
Received 12 February 2021, accepted 31 March 2021, published online 19 August 2021
Abstract
Given a finite transitive permutation group G ≤ Sym(Ω), with |Ω| ≥ 2, the derange-
ment graph ΓG of G is the Cayley graph Cay(G,Der(G)), where Der(G) is the set of
all derangements of G. Meagher et al. [On triangles in derangement graphs, J. Combin.
Theory Ser. A, 180:105390, 2021] recently proved that Sym(2) acting on {1, 2} is the only
transitive group whose derangement graph is bipartite and any transitive group of degree
at least three has a triangle in its derangement graph. They also showed that there exist
transitive groups whose derangement graphs are complete multipartite.
This paper gives two new families of transitive groups with complete multipartite de-
rangement graphs. In addition, we prove that if p is an odd prime and G is a transitive
group of degree 2p, then the independence number of ΓG is at most twice the size of a
point-stabilizer of G.
Keywords: Derangement graph, cocliques, Erdős-Ko-Rado theorem, Cayley graphs.
Math. Subj. Class. (2020): 05C35, 05C69, 20B05
1 Introduction
This paper is concerned with Erdős-Ko-Rado (EKR) type theorems for finite transitive
groups. The classical EKR Theorem is stated as follows.
Theorem 1.1 (Erdős-Ko-Rado [9]). Suppose that n, k ∈ N such that 2k ≤ n. If F is a
family of k-subsets of [n] := {1, 2, . . . , n} such that A ∩ B ̸= ∅ for all A,B ∈ F , then
|F| ≤
(
n−1
k−1
)
. Moreover, if 2k < n, then equality holds if and only if F consists of all the
k-subsets which contain a fixed element of [n].
*The author would like to thank Roghayeh Maleki, Karen Meagher and Shaun Fallat for proofreading and
helping improve the presentation of this paper. The author is also grateful to the two anonymous referees for their
valuable comments and suggestions.
E-mail address: sarobidy@phystech.edu (Andriaherimanana Sarobidy Razafimahatratra)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
90 Ars Math. Contemp. 21 (2021) #P1.07 / 89–103
The EKR theorem has been well studied and generalized for numerous combinatorial
objects in the past 50 years [6, 7, 10, 11, 13, 19, 20, 22, 25]. Of interest to us is the
generalization of Theorem 1.1 for the symmetric group by Deza and Frankl in [10].
Given a finite transitive permutation group G ≤ Sym(Ω), we say that the permutations
σ, π ∈ G are intersecting if ωσ = ωπ , for some ω ∈ Ω. A subset or family F of G is
intersecting if any two permutations of F are intersecting.
Theorem 1.2 (Deza-Frankl, [10]). Let Ω be a set of size n ≥ 2. If F ⊂ Sym(Ω) is an
intersecting family, then |F| ≤ (n− 1)!.
The characterization of the maximum intersecting families of Sym(Ω) was solved al-
most three decades later by Cameron and Ku [6], and independently by Larose and Mal-
venuto [15].
Theorem 1.3 ([6, 15]). Let Ω be a set of size n ≥ 2. If F ⊂ Sym(Ω) is an intersecting
family of maximum size, that is |F| = (n− 1)!, then F is a coset of a stabilizer of a point
of Sym(Ω). In particular, there exist i, j ∈ Ω such that
F = {σ ∈ Sym(Ω) | iσ = j} .
The natural question that arises is whether analogues of Theorem 1.2 and Theorem 1.3
hold for different subgroups of Sym(Ω), i.e., permutation groups of degree n. All groups
considered in this paper are finite. We are interested in the following extremal problem.
Problem 1.4. Let G ≤ Sym(Ω) be transitive.
(1) What is the largest size of an intersecting family of G?
(2) If F is an intersecting family of G of maximum size, then describe the structure of
F .
Not surprisingly, the answer to this problem depends on the structure of the subgroup
of Sym(Ω). For instance, if σ1 = (1 2)(3 4), σ2 = (3 4)(5 6) and τ = (1 3 5)(2 4 6) are
permutations of Ω = {1, 2, 3, 4, 5, 6}, then ⟨σ1, σ2, τ⟩ has its point-stabilizers of size 2 but
F = {id, (1 2)(3 4), (3 4)(5 6), (1 2)(5 6)}
is a larger intersecting family. More examples of transitive permutation groups having
larger intersecting families than point-stabilizers are given in [3, 16, 18]. Due to this, we
consider the following definitions. We say that the group G has the EKR property if any
intersecting family of G has size at most |G||Ω| and G has the strict-EKR property if it has the
EKR property and an intersecting family of size |G||Ω| is a coset of a stabilizer of a point.
A typical approach in solving EKR-type problems is reducing it into a problem on a
graph theoretical invariant. The derangement graph ΓG of G ≤ Sym(Ω) is the graph
whose vertex set is G and two permutations σ, π are adjacent if and only if they are not
intersecting; that is, ωσ ̸= ωπ , for every ω ∈ Ω. In other words, ΓG is the Cayley graph
Cay(G,Der(G)), where Der(G) is the set of all derangements of G. Then, a family F ⊂ G
is intersecting if and only if F is an independent set or a coclique of the derangement graph
ΓG. Therefore, Problem 1.4 is equivalent to finding the size of the maximum cocliques
α(ΓG) and the structures of the cocliques of size α(ΓG).
A. S. Razafimahatratra: On complete multipartite derangement graphs 91
Our long term objective is to classify the transitive permutation groups that have the
EKR property and strict-EKR property. A big step toward this classification is the result
of Meagher, Spiga and Tiep [20], which says that every finite 2-transitive group has the
EKR property. More examples of primitive groups having the EKR property are given in
[1, 2, 5, 8, 17, 19, 22].
We are motivated to find more transitive groups that do not have the EKR property.
The group ⟨σ1, σ2, τ⟩ given above is special in the sense that its derangement graph is a
complete tri-partite graph. A recent result by Meagher, Spiga and the author [18] brought
to light the existence of many transitive groups that do not have the EKR property. The
most important of these are the transitive groups whose derangement graphs are complete
multipartite graphs. If G ≤ Sym(Ω) is transitive and ΓG is a complete multipartite graph,
then it is easy to see that the part H of ΓG, which contains the identity element id, consists
of the elements with at least one fixed point. Moreover, every element of G \ H is a
derangement. Therefore, H is a maximum coclique of ΓG and H is the union of all the
point-stabilizers of G. Thus, G does not have the EKR property unless H = {id}. An
important result on the structure of derangement graphs of transitive groups is given in the
next theorem.
Theorem 1.5 ([18]). Let G ≤ Sym(Ω) be transitive. Then, ΓG is bipartite if and only if
|Ω| ≤ 2. Further, if |Ω| ≥ 3, then ΓG contains a triangle.
Our motivation for this work is to find more transitive groups having complete multi-
partite derangement graphs. In this paper, we give two infinite families of transitive groups
whose derangement graphs are complete multipartite. Our main results are stated as fol-
lows.
Theorem 1.6. Let p be a prime and let q = pk, for some k ≥ 1. Then, there exists a
transitive group Gq , of degree q(q+1), such that ΓGq is a complete (q+1)-partite graph.
The following was conjectured in [18] on the existence of complete multipartite de-
rangement graphs.
Conjecture 1.7. If n is even but not a power of 2, then there is a transitive group G of
degree n such that ΓG is a complete multipartite graph with n/2 parts.
A transitive group of degree n = 2ℓ, where ℓ is odd, with a complete ℓ-partite de-
rangement graph was given in [18, Lemma 5.3]. We generalize this construction to find
another family of transitive groups with complete multipartite derangement graphs. This
result further reinforces Conjecture 1.7.
Theorem 1.8. For any odd ℓ, there exists a transitive permutation group of degree 4ℓ whose
derangement graph is a complete 2ℓ-partite graph.
The intersection density ρ(G) of a permutation group G was introduced in [16, 18] as
the ratio between the size of the largest intersecting families of G and the size of the largest
point-stabilizer of G. That is, if G ≤ Sym(Ω), then
ρ(G) :=
max{|F| : F ⊂ G is intersecting}
maxω∈Ω |Gω|
. (1.1)
For any n ∈ N, we define In := {ρ(G) | G is transitive of degree n} and I(n) := max In.
The following was conjectured in [18].
92 Ars Math. Contemp. 21 (2021) #P1.07 / 89–103
Conjecture 1.9 ([18]). (1) If n = pq where p and q are distinct odd primes, then I(n) =
1.
(2) If n = 2p where p is prime, then I(n) = 2.
In this paper, we also prove that Conjecture 1.9(2) holds.
Theorem 1.10. If p is an odd prime, then I(2p) = 2.
This paper is organized as follows. In Section 2, we give some background results on
complete multipartite derangement graphs and some properties of the intersection density
of transitive groups. In Section 3, Section 4, and Section 5, we give the proof of Theo-
rem 1.6, Theorem 1.8, and Theorem 1.10, respectively.
2 Background
Throughout this section, we let G ≤ Sym(Ω) be a transitive group and |Ω| = n.
2.1 Bound on maximum cocliques
We recall that the problem of finding the size of the maximum intersecting families of G is
equivalent to finding the size of the maximum cocliques of ΓG. We give a classical upper
bound on the size of the largest cocliques in vertex-transitive graphs (i.e., graphs whose
automorphism groups act transitively on their vertex sets). As the derangement graph of an
arbitrary finite permutation group is a Cayley graph, the right-regular representation of G
acts regularly on V (ΓG). In other words, ΓG is vertex transitive.
Lemma 2.1 ([13]). If X = (V,E) is a vertex-transitive graph, then α(X) ≤ |V (X)|ω(X) .
Moreover, equality holds if and only if a maximum coclique of X intersects each maximum
clique at exactly one vertex.
Lemma 2.1 can be used to prove the EKR property of groups. For instance, one can
prove that Sym(n), for n ≥ 3, has the EKR property [6, 10, 12] by showing first that
ω(ΓSym(n)) = n (a clique of ΓSym(n) is induced by a Latin square of size n) and applying
Lemma 2.1. A subset S ⊂ G with |S| = n that forms a clique in ΓG is called a sharply
1-transitive set. It is well-known that a transitive group need not have a sharply 1-transitive
set. Therefore, Lemma 2.1 does not hold with equality for the derangement graphs of many
transitive groups.
2.2 Intersection density
By (1.1), the intersection density of the transitive group G is the rational number
ρ(G) :=
max |{F ⊆ G | F is intersecting}|
|Gω|
,
where ω ∈ Ω.
The major result in [18] (see also Theorem 1.5) asserts that the intersection density of
the transitive group G cannot be equal to n2 . This is equivalent to saying that the derange-
ment graph of transitive groups cannot be bipartite if n ≥ 3 (see [18]). It is also proved in
[18] that for any transitive group K of degree n, ρ(K) is in the interval
[
1, n3
]
. We note
A. S. Razafimahatratra: On complete multipartite derangement graphs 93
that ρ(K) = 1 if and only if K has the EKR property. Moreover, the upper bound n3 is
sharp since there are transitive groups whose derangement graphs are complete tri-partite
graphs [18, Theorem 5.1]. It is conjectured that the only transitive groups that attain the
upper bound are those with complete tri-partite derangements graphs.
The study of the intersection density (see [16, 18]) of a transitive group was mainly
motivated by studying how far from having the EKR property a transitive group can be.
The intersection density, therefore, is a measure of the EKR property for transitive groups.
We make the following conjecture based on computer search using Sagemath [23].
Conjecture 2.2. For any n ≥ 3, almost all elements of the set In are integers. That is,
|{ρ(G) | G is transitive of degree n} ∩ N|
|In|
−−−−→
n→∞
1.
Note that the intersection density of a transitive group can be non-integer. For example,
the transitive groups of degree n and number k in the TransitiveGroup function of
Sagemath, with (n, k) ∈ {(12, 122), (12, 93)}, have non-integer intersection densities.
TransitiveGroup(12,122) and TransitiveGroup(12,93) have intersection density
equal to 32 and
17
16 , respectively.
Proposition 2.3. If the derangement ΓG has a clique of size k, then ρ(G) ≤ nk .
Proof. The proof follows by applying Lemma 2.1.
2.3 Complete multipartite derangement graphs
The transitive groups with complete multipartite derangement graphs are the most natural
examples of groups that do not have the EKR property. In this subsection, we give some
properties of transitive groups whose derangement graphs are complete multipartite.
The following lemma is a straightforward observation on the intersecting subgroups of
G.
Lemma 2.4 ([16, 18]). Let G ≤ Sym(Ω) and let H ≤ G. Then, H is intersecting if and
only if H does not have any derangement.
The next lemma illustrates that transitive groups with complete multipartite derange-
ment graphs have a very distinct algebraic structure.
Lemma 2.5 ([18]). If G ≤ Sym(Ω) is transitive such that ΓG is a complete multipartite
graph, then G is imprimitive.
A transitive group whose derangement graph is a complete multipartite graph is uniquely
determined by a specific subgroup of G. We define F(G) to be the subgroup of G generated
by all the permutations of G with at least one fixed point. That is,
F(G) :=
〈 ⋃
ω∈Ω
Gω
〉
.
Proposition 2.6. The subgroup F(G) is a normal subgroup of G.
Proof. The proof follows from the fact that F(G) is generated by all point-stabilizers.
94 Ars Math. Contemp. 21 (2021) #P1.07 / 89–103
Note that Lemma 2.5 follows from the normality of F(G) as its orbits form a non-trivial
system of imprimitivity of G acting on Ω.
A characterization of transitive groups with complete multipartite derangement graphs
is given in the next lemma.
Lemma 2.7 ([18]). Let G ≤ Sym(Ω) be transitive. The graph ΓG is complete multipartite
if and only if F(G) is intersecting. Moreover, if ΓG is a complete multipartite graph, then
the number of parts of ΓG is [G : F(G)].
Suppose that ΓG is a complete multipartite graph. When the subgroup F(G) is the
trivial group {id}, then ΓG is the complete multipartite graph that has |G| parts of size 1.
In other words, ΓG is the complete graph K|G|. When F(G) = G, then F(G) cannot be
intersecting since by Lemma 2.4, this would contradict the celebrated theorem of Jordan
[14, 21] on the existence of derangements in finite transitive groups. Hence, we say that
ΓG is a non-trivial complete multipartite graph if 1 < |F(G)| < |G|. In this paper, we
are only interested in transitive groups with non-trivial complete multiplartite derangement
graphs.
Next, we study the structure of F(G). If F(G) is intersecting, then by Lemma 2.4,
F(G) is derangement-free. Thus,
F(G) =
⋃
ω∈Ω
Gω.
Recall that if K ≤ Sym(Ω) and ω ∈ Ω, then the orbit of K containing ω is denoted by
ωK . Moreover, if S ⊂ Ω, then the setwise stabilizer of S in K is denoted by K{S}.
The following lemma is a standard result in the theory of permutation groups.
Lemma 2.8. Let G ≤ Sym(Ω) and ω ∈ Ω. If H is a non-trivial subgroup of G containing
Gω , then G{ωH} = H .
Corollary 2.9. Let G ≤ Sym(Ω) be transitive and let K be the subgroup of G fixing the
system of imprimitivity
{
ωF(G) | ω ∈ Ω
}
. Then K = F(G).
Proof. Since F(G) is generated by the point-stabilizers, by the previous lemma, we have
K =
⋂
ω∈Ω
G{ωF(G)} =
⋂
ω∈Ω
F(G) = F(G).
Remark 2.10. A representation of the derangement graph of the transitive group G as a
complete mutlipartite graph is unique. This is due to the fact that the part of ΓG, which
contains the identity element, must be equal to F (G).
3 Proof of Theorem 1.6
In this section, we describe the action of AGL(2, q) on the lines and give some basic results.
Then, we prove Theorem 1.6.
A. S. Razafimahatratra: On complete multipartite derangement graphs 95
3.1 An action of AGL(2, q) on the lines
Let q = pk be a prime power, where k ≥ 1. For b ∈ F2q and A ∈ GL(2, q), we let
(b, A) : F2q → F2q be the affine transformation such that (b, A)(v) := Av + b. The affine
group AGL(2, q) is the permutation group{
(b, A) | A ∈ GL(2, q), b ∈ F2q
}
,
with the multiplication (a,A)(b, B) := (a+Ab,AB).
Hence, AGL(2, q) acts naturally on the vectors of F2q . This action induces an action of
AGL(2, q) on the set Ω of all lines of F2q (i.e., the collection of all sets of the form Lu,v :=
{u+ tv | t ∈ Fq}, where u, v ∈ F2q and v ̸= 0). Recall that PG(1,Fq) := PG(1, q) is the
set of all 1-dimensional subspaces of the Fq-vector space F2q . The elements of PG(1, q)
are exactly the lines containing 0 ∈ F2q . By a simple counting argument, each vector of
F2q \ {0} determines a line, and each line passing through 0 has q − 1 points (excluding 0).
So there are q
2−1
q−1 = q + 1 subspaces in PG(1, q). For any line ℓ ∈ PG(1, q), we define
Ωℓ :=
{
ℓ+ b | b ∈ F2q
}
. The set Ωℓ consists of F2q-shifts of the 1-dimensional subspace ℓ,
thus its elements are affine lines of F2q that are parallel to ℓ. Therefore, Ω :=
⋃
ℓ∈PG(1,q) Ωℓ
is exactly the set of lines of F2q . Note that we can also view Ω as the lines of the incidence
structure
(
F2q, L,∼
)
, where L = {Lu,v | u, v ∈ F2q, v ̸= 0} and v ∼ ℓ, for v ∈ F2q and
ℓ ∈ L, if and only if v ∈ ℓ. This incidence structure is the affine plane AG(2, q).
As GL(2, q) acts transitively on PG(1, q), it is easy to see that AGL(2, q) acts transi-
tively on Ω. Since the elements of GL(2, q) ≤ AGL(2, q) leave PG(1, q) invariant, for any
ℓ ∈ PG(1, q), the set Ωℓ is either invariant by the action of an element of AGL(2, q) or is
mapped to some other Ωℓ′ , where ℓ′ ∈ PG(1, q) \ {ℓ}. That is, Ωℓ is a block for the action
of AGL(2, q) on Ω. Therefore, AGL(2, q) acts imprimitively on Ω.
As the elements of AGL(2, q) are affine transformations, the pair of parallel lines
(l, l′) ∈ Ωℓ×Ωℓ can be mapped by AGL(2, q) to any other pair of parallel lines. However,
if (l, l′) ∈ Ωℓ × Ωℓ′ , for distinct ℓ, ℓ′ ∈ PG(1, q), then no element of AGL(2, q) can map
(ℓ, ℓ′) to a pair of parallel lines. In addition, one can prove that any pair of non-parallel
lines can be mapped to any other pair of non-parallel lines. In other words, AGL(2, q)
acting on Ω2 has exactly 3 orbits. We formulate this result as the following lemma.
Lemma 3.1. The group AGL(2, q) acting on Ω is a rank 3 imprimitive group.
3.2 Action of Singer subgroups of GL(2, q) as subgroups of AGL(2, q)
We recall that for n ≥ 1, GL(n, q) admits elements of order qn − 1. These elements are
called Singer cycles, and a subgroup of order qn − 1 generated by a Singer cycle is called
a Singer subgroup. We recall the following observation about Singer cycles.
Proposition 3.2. If A is a Singer cycle of GL(2, q), then the subgroup ⟨A⟩ acts regularly
on F2q \ {0}.
For any matrix C ∈ GL(2, q), we define
Gq(C) :=
{
(b, B) | B ∈ ⟨C⟩, b ∈ F2q
}
.
Now, let A be an arbitrary Singer cycle of GL(2, q). By Proposition 3.2, it is easy to
see that the action of
Hq := {(0, B) ∈ AGL(2, q) | B ∈ ⟨A⟩}
96 Ars Math. Contemp. 21 (2021) #P1.07 / 89–103
on PG(1, q) is transitive. The latter implies that the action of the subgroup Gq(A) on Ω is
transitive. To see this, let ℓ = ℓ0 + b and ℓ′ = ℓ′0 + b
′ be two lines in Ω such that ℓ0 and ℓ′0
are 1-dimensional subspaces and b, b′ ∈ F2q . By transitivity of Hq on PG(1, q), there exists
(0, B) ∈ Hq such that (0, B)(ℓ0) = ℓ′0. Hence,
(b′ −Bb,B)(ℓ) = (b′ −Bb,B)(ℓ0 + b) = Bℓ0 +Bb+ b′ −Bb = ℓ′0 + b′ = ℓ′.
Thus, Gq(A) is transitive. It is straightforward to verify that for any ℓ ∈ PG(1, q), Ωℓ is a
block of Gq(A). Therefore, we have the following.
Proposition 3.3. The group Gq(A) acts imprimitively on Ω and Ωℓ is a block of Gq(A),
for any ℓ ∈ PG(1, q).
3.3 Kernel of the action of Gq(A)
In this subsection, we study the kernel of the action of Gq(A) on the system of imprimitivity
{Ωℓ | ℓ ∈ PG(1, q)}.
To avoid any confusion, we use the notation StabGq(A)(l) in the remainder of Sec-
tion 3 to denote the point-stabilizer of ℓ ∈ Ω in Gq(A), instead of the standard notation
used in the theory of permutation groups. Similarly, for any S ⊂ Ω, we use the notation
Stab(Gq(A), S) for the setwise stabilizer of S in Gq(A).
By Lemma 3.1, the action of AGL(2, q) on Ω has a unique system of imprimitivity,
namely the set {Ωℓ | ℓ ∈ PG(1, q)}. Define
Mq :=
⋂
ℓ∈PG(1,q)
Stab(Gq(A),Ωℓ).
We prove the following lemma.
Lemma 3.4. The affine transformation (b, B) ∈ Mq if and only if there exists k ∈ F∗q such
that B = kI , where I is the 2× 2 identity matrix.
Proof. It is easy to see that if B = kI , for some k ∈ F∗q , then (0, B) fixes every element of
PG(1, q). Therefore, (b, B) leaves Ωℓ invariant for any ℓ ∈ PG(1, q).
If (b, B) ∈ Mq , then (0, B) fixes every element of PG(1, q). In particular, there exists
k1, k2 ∈ F∗q such that
(0, B)
[
1
0
]
= B
[
1
0
]
= k1
[
1
0
]
, and (0, B)
[
0
1
]
= B
[
0
1
]
= k2
[
0
1
]
.
Therefore, the matrix B = diag(k1, k2). The 1-dimensional subspace generated by the
vector u =
[
1
1
]
forces k1 = k2, since Bu = ku for some k ∈ F∗q . Hence B = kI .
We present an immediate corollary of this.
Corollary 3.5. The subgroup Mq of Gq(A) is intersecting.
Proof. It suffices to prove that any element of Mq has a fixed point. Let (b, kI2) ∈ Mq . If
k = 1, then it is obvious that (b, I) fixes every line in the block Ωℓ, where ℓ ∈ PG(1, q)
such that b ∈ ℓ.
A. S. Razafimahatratra: On complete multipartite derangement graphs 97
If k ̸= 1, then we prove that there exist β ∈ F2q such that for any ℓ ∈ PG(1, q), (b, kI)
fixes the line ℓ+ β. If (b, kI) fixes this line, then we must have
(b, kI)(ℓ+ β) = kℓ+ kβ + b
= ℓ+ kβ + b = ℓ+ β.
In other words, we should find β such that (1 − k)β − b ∈ ℓ, for any ℓ ∈ PG(1, q). For
β = (1− k)−1b, we have (1− k)β − b = 0 ∈ ℓ. Moreover, the solution β = (1− k)−1b
does not depend on ℓ since every element of PG(1, q) contains 0.
We conclude that when k = 1, then (b, kI) fixes every line of the block Ωℓ, with b ∈ ℓ
and if k ̸= 1, then (b, kI) fixes every line of the form ℓ + (1 − k)−1b ∈ Ω, for any
ℓ ∈ PG(1, q).
We prove the following lemma about the relation between the kernel of the action
of Gq(A) on {Ωℓ | ℓ ∈ PG(1, q)} and the subgroup F(Gq(A)) generated by the non-
derangements of Gq(A).
Lemma 3.6. The subgroup F(Gq(A)) is equal to Mq .
Proof. Let (b, kI) ∈ Mq . In the proof of Corollary 3.5, we showed that a transformation
of (b, kI) either fixes every element of Ωℓ, for some ℓ ∈ PG(1, q), or it fixes exactly one
line in each Ωℓ. Therefore, Mq ≤ F(Gq(A)).
Next, we will prove that the point-stabilizer StabGq(A)(ℓ) of ℓ in Gq(A) is a subgroup
of Mq , for any ℓ ∈ Ω. First, let ℓ ∈ PG(1, q) be the line that contains the point
[
1
0
]
∈ F2q .
Observe that for b ∈ F2q , ℓ+ b = ℓ if and only if b ∈ ℓ. Therefore, the affine transformation
(b, kI) ∈ StabGq(A)(ℓ), for any b ∈ ℓ and k ∈ F∗q . There are q(q−1) affine transformations
of this form in StabGq(A)(ℓ). Arguing by the size of the stabilizer of ℓ in Gq(A), we have
|StabGq(A)(ℓ)| =
q2(q2 − 1)
q(q + 1)
= q(q − 1).
We conclude that the point-stabilizer of ℓ in Gq(A) is
StabGq(A)(ℓ) =
{
(b, B) ∈ Gq | B = kI, b ∈ ℓ, k ∈ F∗q
}
≤ Mq.
Since Mq ◁ Gq(A) and Gq(A) is transitive, we have StabGq(A)(ℓ) ≤ Mq for any ℓ ∈ Ω.
Therefore, F(Gq(A)) ≤ Mq . This completes the proof.
3.4 Proof of Theorem 1.6
We prove that the derangement graph ΓGq(A) of Gq(A) is a complete (q+1)-partite graph.
By Corollary 3.5, Mq is intersecting, and by Lemma 3.6, we have Mq = F(Gq(A)).
Therefore, ΓGq(A) is a complete k-partite graph, where k = [Gq(A) : Mq] =
q2(q2−1)
q2(q−1) =
q + 1.
Note that Lemma 3.6 is crucial to our proof. Indeed, the subgroup generated by the
permutations with fixed points in AGL(2, q) acting on Ω, i.e., F(AGL(2, q)), is the whole
of AGL(2, q); whereas the stabilizer of its unique system of imprimitivity is the proper
subgroup Mq .
98 Ars Math. Contemp. 21 (2021) #P1.07 / 89–103
4 Proof of Theorem 1.8
We will construct a transitive permutation group G of degree n = 4ℓ acting on [n], where
ℓ is an odd natural number. The derangement ΓG of this group G will be a complete
multipartite graph with n2 parts. The group G that we will construct is isomorphic to
(C2 × C2 × . . .× C2︸ ︷︷ ︸
ℓ−1
)⋊Dℓ,
where Dℓ is the dihedral group of order 2ℓ.
4.1 Kernel of the action
We would like to construct G so that it will have a system of imprimitivity
B = {{i, i+ 1} | for i ∈ [n] ∩ (2Z+ 1)} .
For any i, j ∈ (4Z+ 1) ∩ [n], define σi := (i i + 1)(i + 2 i + 3) and πj := σjσ4ℓ−3.
Let S = {πj | j ∈ (4Z+ 1) ∩ [n]}. Notice that |S| = ℓ, however, π4ℓ−3 = id ∈ S. We
consider the permutation group H = ⟨S⟩. It is easy to see that
H ∼= C2 × C2 × . . .× C2︸ ︷︷ ︸
ℓ−1
.
Moreover, for any fixed k ∈ [n]∩(4Z+1), any subset of the form {σiσk | i ∈ [n] ∩ (4Z+ 1)}
generates H .
A permutation of H either fixes, pointwise, an element of B or interchanges the pair of
elements in a set of B. Therefore, H leaves B invariant. Any g ∈ H can be written in the
form
g =
∏
j∈[n]∩(4Z+1)
π
kj
j , (4.1)
for some kj ∈ {0, 1}. Since π4ℓ−3 = id, there are at most ℓ − 1 (which is even) permu-
tations of the form πj in the expression of g in (4.1). If the number of non-identity terms
in (4.1) is even, then g fixes the points 4ℓ − 3, 4ℓ − 2, 4ℓ − 1, and 4ℓ. If the number of
non-identity terms in (4.1) is odd, then there exists j ∈ [n]∩(4Z+1), j ̸= 4ℓ−3, such that
kj = 0 (because ℓ− 1 is even). Therefore, g fixes the elements j, j + 1, j + 2, and j + 4.
We conclude that
H is an intersecting subgroup of degree n = 4ℓ. (4.2)
The group G will be defined so that H = F(G).
4.2 Action of a dihedral group on H
First, we give a permutation c, which is a product of four disjoint ℓ-cycles. Then, we
construct a transposition τ so that τcτ−1 = c−1. In other words, ⟨c, τ⟩ = Dℓ. This
subgroup will act on H so that ⟨H, c, τ⟩ is transitive.
For any i ∈ Z, define Ai := (i i+4 . . . i+4k . . . i+4(ℓ−1)) to be the permutation
of order ℓ, whose entries in the cycle notation are those of an arithmetic progression of step
4, and with initial value i. Let
c := A1A2A3A4.
A. S. Razafimahatratra: On complete multipartite derangement graphs 99
We note that A1, A2, A3, and A4 are pairwise disjoint ℓ-cycles. Consider the permutation
τ := (1 3)(2 4)
∏
i∈{1 2 ... ℓ−1}
(1 + 4i 3 + 4(ℓ− i)) (2 + 4i 4 + 4(ℓ− i)) .
The transpositions in the expression of τ are also pairwise disjoint. Moreover, τ is a de-
rangement of Sym(n). The following conditions are satisfied by τ
τA1τ
−1 = A−13 ,
τA2τ
−1 = A−14 ,
τA3τ
−1 = A−11 ,
τA4τ
−1 = A−12 .
(4.3)
From (4.3), we deduce that τcτ−1 = c−1. We conclude that ⟨τ, c⟩ ∼= Dℓ.
Next, we see how the subgroup ⟨c, τ⟩ acts on H . For i ∈ [n]∩(4Z+1) with i ̸= 4ℓ−3,
we have
νi := cπic
−1 = cσiσ4ℓ−3c
−1 = σi+4σ1.
Since {νi | i ∈ [n] ∩ (4Z + 1)} also generates H , we conclude that cHc−1 = H . In
addition, for any i ∈ [n] ∩ (4Z+ 1), we have
µi := τπiτ
−1 = τσiσ4ℓ−3τ
−1 = στ(i+2)σ5.
Since {µi | i ∈ [n] ∩ (4Z+ 1)} also generates H , we have τHτ−1 = H .
We conclude that G := H⟨τ, c⟩ is a permutation group of degree 4ℓ. In addition, it is
easy to see that H∩⟨τ, c⟩ = {id}, so we have G = H⋊⟨τ, c⟩. Furthermore, G is transitive
because
(1) the orbits of H⟨c⟩ are {1+4i | i ∈ {0, 1, 2, . . . , ℓ−1}}∪{2+4i | i ∈ {0, 1, 2, . . . , ℓ−
1}} and {3 + 4i | i ∈ {0, 1, 2, . . . , ℓ− 1}} ∪ {4 + 4i | i ∈ {0, 1, 2, . . . , ℓ− 1}}, and
(2) the orbits of ⟨τ⟩ are the sets of the form {1+4i, 3+4(ℓ− i)}, {2+4i, 4+4(ℓ− i)}
where i ∈ {0, 1, . . . , ℓ− 1} , {2, 4}, and {1, 3}.
4.3 Derangement graph of G
The derangement graph of G is a complete multipartite graph with 2ℓ parts. To prove this,
we need to show that H is intersecting and F(G) = H . We only need to prove the latter
since H is an intersecting subgroup (see (4.2)).
On one hand, as the elements of S all have fixed points, it is easy to see that ⟨S⟩ =
H ≤ F(G). On the other hand, the subgroup K = ⟨π5, π9, . . . , π4i+1, . . . , π4ℓ−7⟩ ≤ H
fixes 1; that is, K ≤ G1. Since |K| = 2ℓ−2 and |G1| = |G|4ℓ = 2
ℓ−2, we conclude that
G1 = K ≤ H . As G is transitive, the point-stabilizers of G are conjugate. Moreover, since
H ◁ G (because G = H ⋊ ⟨τ, c⟩) and G1 ≤ H , we can conclude that Gi ≤ H , for any
i ∈ [n]. Therefore, F(G) ≤ H .
In conclusion, we know that F(G) = H is intersecting. This is equivalent to ΓG being
a complete multipartite graph, with [G : H] = 2ℓ parts.
100 Ars Math. Contemp. 21 (2021) #P1.07 / 89–103
5 Proof of Theorem 1.10
We will prove that every transitive group of degree 2p, for any odd prime p, has intersec-
tion density at most 2 (Theorem 1.10) by showing that there is a clique of size p in the
derangement graph of G. In this case, we have ρ(G) ≤ |Ω|p = 2. Therefore, 1 ≤ ρ(G) ≤ 2
for any transitive group G of degree 2p. It is proved in [18, Lemma 5.3] that for any odd ℓ,
there is a transitive group of degree 2ℓ, whose intersection density is 2. Therefore, we will
have I(2p) = 2, for any odd prime p.
As p | |G|, by Cauchy’s theorem, there exists σ ∈ G whose order is p. Therefore, σ
is either a p-cycle or the product of two disjoint p-cycles. If the latter holds, then σ is a
derangement of G and ⟨σ⟩ is then a clique of size p in ΓG. So, we may suppose that σ is a
p-cycle.
5.1 Imprimitive case
Since G ≤ Sym(Ω) is imprimitive of degree 2p, a non-trivial block of imprimitivity of G
has size 2 or p. Assume that
σ = (x1 x2 x3 . . . xp).
As p is an odd prime and σ ∈ G, it is easy to see that G cannot have a system of imprimi-
tivity consisting of sets of size 2. We suppose that G has a set of imprimitivity Q consisting
of two subsets of size p of Ω. It is easy to see that σ cannot interchange the two blocks
of Q since the support of σ only has p elements. Thus, σ is in the setwise stabilizer of Q.
Suppose that Q = {B,B′}, where B = {x1, x2, . . . , xp} and B′ = {y1, y2, . . . , yp}. As
Gy1 and Gx1 are conjugate, there exists an element σ
′ ∈ Gx1 , which is a p-cycle. As σ′ is
a p-cycle, it must fix B pointwise and act as a p-cycle on B′.
We conclude that the permutation σσ′ ∈ G is a product of two disjoint p-cycles. The
subgroup ⟨σσ′⟩ is a clique of size p of ΓG.
5.2 Primitive case
Suppose that G ≤ Sym(Ω) is primitive of degree 2p. We derive the result of Theorem 1.10
from the following lemma.
Lemma 5.1 ([24]). Suppose that p is an odd prime. A primitive group of degree 2p is either
2-transitive or every non-identity element of a Sylow p-subgroup of G is a product of two
disjoint p-cycles.
By Lemma 5.1, we conclude that G is 2-transitive or G contains a derangement of order
p. Hence, either G has the EKR property [20] (in which case ρ(G) = 1) or ρ(G) ≤ 2.
This completes the proof of Theorem 1.10.
6 Further work
We finish this paper by posing some open questions. In Section 5, we proved that for any
odd prime p, a transitive group G of degree 2p has intersection density 1 ≤ ρ(G) ≤ 2. It
follows from the classification of finite simple groups that the only simply primitive groups
(i.e., primitive groups that are not 2-transitive) of degree 2p are Alt(5) and Sym(5), both
of degree 10. Using Sagemath [23], the largest intersecting family of Alt(5) is of size
A. S. Razafimahatratra: On complete multipartite derangement graphs 101
12, whereas its stabilizer of a point has size 6. The largest intersecting family of Sym(5)
is 12, which equals the size of its point-stabilizers. We conclude that the group Alt(5) of
degree 10 has the largest intersection density among all primitive groups of degree 2p, for
every odd prime p.
For the imprimitive case, there are infinitely many examples of transitive groups with
intersection density equal to 2. In [18, Lemma 5.3], the authors gave a family of transitive
groups of degree 2ℓ, for any odd ℓ, whose derangement graphs are ℓ-partite and whose in-
tersection densities are equal to 2. Based on a non-exhaustive search on the small transitive
groups of degree 2p (where p is an odd prime) available on Sagemath, we are inclined to
believe that the intersection density of a transitive group of degree 2p, where p is an odd
prime, is an integer. We ask the following question.
Question 6.1. Does there exist an odd prime p and a transitive group G of degree 2p such
that ρ(G) is not an integer?
In Theorem 1.8, we proved that there exists a family of transitive groups of degree
4ℓ, for any odd ℓ, with complete 2ℓ-partite derangement graphs. This further confirms
the validity of [18, Conjecture 6.6 (1)] (see also Conjecture 1.7) about the existence of
transitive groups of any degree n which is even but not a power of 2, with a complete
n
2 -partite derangement graph.
Problem 6.2. For any odd ℓ and an integer i ≥ 3, find a transitive group of degree 2iℓ
whose derangement graph is a complete 2i−1ℓ-partite graph.
In Section 3, we gave an example of a transitive group of degree q(q + 1), where q is
a prime power, whose intersection density is equal q. A non-exhaustive search on small
transitive groups of degree q(q + 1), which are available on Sagemath, shows that the
largest intersection density for these groups is q. We ask the following question.
Question 6.3. Does there exist a transitive group G of degree q(q+ 1), where q is a prime
power, such that ρ(G) > q?
Our motivation to work on the EKR property for the transitive group in Section 3 comes
from studying the EKR property for AGL(2, q) acting on the lines of AG(2, q) (see Sec-
tion 3), where q is a prime power. Observe that if H and G are transitive permutation
groups acting on Ω and H ≤ G, then ΓH is an induced subgraph of ΓG. Using the No-
Homomorphism Lemma [4], one can prove that α(ΓG) ≤ α(ΓH) |G||H| . We deduce from this
inequality that if H has the EKR property, then so does G. Moreover, ρ(G) ≤ ρ(H).
Recall that the subgroup Gq(A) defined in Section 3 is a subgroup of AGL(2, q) acting
on the lines of AG(2, q). Using the result from the previous paragraph, we know that
ρ(AGL(2, q)) ≤ ρ(Gq(A)) =
q2(q − 1)
q(q − 1)
= q,
where q is a prime power and A is a Singer cycle of GL(2, q). However, we believe that
this bound is not sharp. Indeed, from the observation of the behavior of the intersection
density of AGL(2, q) (q ∈ {3, 4, 5, 7, 8}) acting on the lines of AG(2, q), we make the
following conjecture.
Conjecture 6.4. For any ε > 0, there exists a prime power q0, such that for any prime
power q ≥ q0, 0 ≤ ρ(AGL(2, q)) − 1 ≤ ε. In particular, ρ(AGL(2, q)) ∈ Q \ N, for any
prime power q.
102 Ars Math. Contemp. 21 (2021) #P1.07 / 89–103
ORCID iDs
Andriaherimanana Sarobidy Razafimahatratra https://orcid.org/0000-0002-3542-9160
References
[1] B. Ahmadi and K. Meagher, A new proof for the Erdős-Ko-Rado theorem for the alternating
group, Discrete Math. 324 (2014), 28–40, doi:10.1016/j.disc.2014.01.013.
[2] B. Ahmadi and K. Meagher, The Erdős-Ko-Rado property for some 2-transitive groups, Ann.
Comb. 19 (2015), 621–640, doi:10.1007/s00026-015-0285-6.
[3] B. Ahmadi and K. Meagher, The Erdős-Ko-Rado property for some permutation groups, Aus-
tralas. J. Combin. 61 (2015), 23–41, https://ajc.maths.uq.edu.au/?page=get_
volumes&volume=61.
[4] M. O. Albertson and K. L. Collins, Homomorphisms of 3-chromatic graphs, Discrete Math. 54
(1985), 127–132, doi:10.1016/0012-365x(85)90073-1.
[5] A. Behajaina, R. Maleki, A. T. Rasoamanana and A. S. Razafimahatratra, 3-setwise intersecting
families of the symmetric group, Discrete Math. 344 (2021), 112467, 15, doi:10.1016/j.disc.
2021.112467.
[6] P. J. Cameron and C. Y. Ku, Intersecting families of permutations, European J. Combin. 24
(2003), 881–890, doi:10.1016/s0195-6698(03)00078-7.
[7] M. Deza and P. Frankl, Erdős-Ko-Rado theorem—22 years later, SIAM J. Algebraic Discrete
Methods 4 (1983), 419–431, doi:10.1137/0604042.
[8] D. Ellis, E. Friedgut and H. Pilpel, Intersecting families of permutations, J. Amer. Math. Soc.
24 (2011), 649–682, doi:10.1090/s0894-0347-2011-00690-5.
[9] P. Erdős, C. Ko and R. Rado, Intersection theorems for systems of finite sets, Quart. J. Math.
Oxford Ser. (2) 12 (1961), 313–320, doi:10.1093/qmath/12.1.313.
[10] P. Frankl and M. Deza, On the maximum number of permutations with given maximal or mini-
mal distance, J. Combinatorial Theory Ser. A 22 (1977), 352–360, doi:10.1016/0097-3165(77)
90009-7.
[11] P. Frankl and R. M. Wilson, The Erdős-Ko-Rado theorem for vector spaces, J. Combin. Theory
Ser. A 43 (1986), 228–236, doi:10.1016/0097-3165(86)90063-4.
[12] C. Godsil and K. Meagher, A new proof of the Erdős-Ko-Rado theorem for intersecting families
of permutations, European J. Combin. 30 (2009), 404–414, doi:10.1016/j.ejc.2008.05.006.
[13] C. Godsil and K. Meagher, Erdős-Ko-Rado theorems: algebraic approaches, volume 149 of
Cambridge Studies in Advanced Mathematics, Cambridge University Press, Cambridge, 2016,
doi:10.1017/cbo9781316414958.
[14] C. Jordan, Recherches sur les substitutions, J. Math. Pures Appl. 17 (1872), 351–367, https:
//archive.org/details/s2journaldemat17liou/page/n9/mode/2up.
[15] B. Larose and C. Malvenuto, Stable sets of maximal size in Kneser-type graphs, European J.
Combin. 25 (2004), 657–673, doi:10.1016/j.ejc.2003.10.006.
[16] C. H. Li, S. J. Song and V. Pantangi, Erdős–Ko–Rado problems for permutation groups, 2020,
arXiv:2006.10339 [math.CO].
[17] K. Meagher and A. S. Razafimahatratra, 2-intersecting permutations, 2020,
arXiv:2005.00139 [math.CO].
[18] K. Meagher, A. S. Razafimahatratra and P. Spiga, On triangles in derangement graphs, J. Com-
bin. Theory Ser. A 180 (2021), 105390, 26, doi:10.1016/j.jcta.2020.105390.
A. S. Razafimahatratra: On complete multipartite derangement graphs 103
[19] K. Meagher and P. Spiga, An Erdős-Ko-Rado theorem for the derangement graph of PGL(2, q)
acting on the projective line, J. Combin. Theory Ser. A 118 (2011), 532–544, doi:10.1016/j.jcta.
2010.11.003.
[20] K. Meagher, P. Spiga and P. H. Tiep, An Erdős-Ko-Rado theorem for finite 2-transitive groups,
European J. Combin. 55 (2016), 100–118, doi:10.1016/j.ejc.2016.02.005.
[21] J.-P. Serre, On a theorem of Jordan, Bull. Amer. Math. Soc. (N.S.) 40 (2003), 429–440, doi:
10.1090/s0273-0979-03-00992-3.
[22] P. Spiga, The Erdős-Ko-Rado theorem for the derangement graph of the projective general
linear group acting on the projective space, J. Combin. Theory Ser. A 166 (2019), 59–90, doi:
10.1016/j.jcta.2019.02.015.
[23] The Sage Developers, SageMath, the Sage Mathematics Software System (Version 8.9.0), 2020,
https://www.sagemath.org.
[24] H. Wielandt, Finite Permutation Groups, Academic Press, 2014, doi:10.1016/
c2013-0-11702-3.
[25] R. M. Wilson, The exact bound in the Erdős-Ko-Rado theorem, Combinatorica 4 (1984), 247–
257, doi:10.1007/bf02579226.