# On constructing expander families of G-graphs

Mohamad Badaoui, Alain Bretto, David Ellison, Bassam Mourad

► To cite this version:

Mohamad Badaoui, Alain Bretto, David Ellison, Bassam Mourad. On constructing expander families of G-graphs. Ars Mathematica Contemporanea, 2018, 15 (2), pp.425-440. 10.26493/1855-3974.1537.97c. hal-02125928

HAL Id: hal-02125928

https://hal.science/hal-02125928

Submitted on 31 May 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# On constructing expander families of G-graphs

Mohamad Badaoui, Alain Bretto, David Ellison, Bassam Mourad

► To cite this version:

Mohamad Badaoui, Alain Bretto, David Ellison, Bassam Mourad. On constructing expander families of G-graphs. Ars Mathematica Contemporanea, 2018, 15 (2), pp.425-440. 10.26493/1855-3974.1537.97c. hal-02125928

HAL Id: hal-02125928

https://hal.science/hal-02125928v1

Submitted on 31 May 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# On constructing expander families of
G-graphs*

Mohamad Badaoui

Normandie Univ-Caen, GREYC CNRS UMR-6072, Campus II, Bd Marechal Juin BP
5186, 14032 Caen cedex, France, and
Lebanese University, Laboratoire de Mathématique, EDST, Rafic Hariri University
Campus, Hadath P.O. Box 5, Beirut, Lebanon

Alain Bretto

Normandie Univ-Caen, GREYC CNRS UMR-6072, Campus II, Bd Marechal Juin BP
5186, 14032 Caen cedex, France

David Ellison

RMIT University, 124 Little La Trobe St, Melbourne VIC 3000, Australia

Bassam Mourad

Department of Mathematics, Faculty of Science, Lebanese University, Beirut, Lebanon

Received 1 December 2017, accepted 11 July 2018, published online 14 August 2018

## Abstract

Like Cayley graphs, *G*-graphs are graphs that are constructed from groups. A method for constructing expander families of *G*-graphs is presented and is used to construct new expander families of irregular graphs. This technique depends on a relation between some known expander families of Cayley graphs and certain expander families of *G*-graphs. Several other properties of expander families of *G*-graphs are presented.

**Keywords:** Cayley graph, diameter of a graph, abelian group, *G*-graph, expander family.

Math. Subj. Class.: 05C40, 05C42, 05C69

<footnote>*The authors sincerely thank the referee for many valuable suggestions and useful comments. The first and the fourth authors are supported by the Lebanese University research grants program.</footnote>

<footnote>E-mail addresses: mohamad.badaoui1@gmail.com (Mohamad Badaoui), alain.bretto@unicaen.fr (Alain Bretto), davidellison@polytechnique.edu (David Ellison), bmourad@ul.edu.lb (Bassam Mourad)</footnote>
# On constructing expander families of
G-graphs*

Mohamad Badaoui

Normandie Univ-Caen, GREYC CNRS UMR-6072, Campus II, Bd Marechal Juin BP
5186, 14032 Caen cedex, France, and
Lebanese University, Laboratoire de Mathématique, EDST, Rafic Hariri University
Campus, Hadath P.O. Box 5, Beirut, Lebanon

Alain Bretto

Normandie Univ-Caen, GREYC CNRS UMR-6072, Campus II, Bd Marechal Juin BP
5186, 14032 Caen cedex, France

David Ellison

RMIT University, 124 Little La Trobe St, Melbourne VIC 3000, Australia

Bassam Mourad

Department of Mathematics, Faculty of Science, Lebanese University, Beirut, Lebanon

Received 1 December 2017, accepted 11 July 2018, published online 14 August 2018

## Abstract

Like Cayley graphs, G-graphs are graphs that are constructed from groups. A method for constructing expander families of G-graphs is presented and is used to construct new expander families of irregular graphs. This technique depends on a relation between some known expander families of Cayley graphs and certain expander families of G-graphs. Several other properties of expander families of G-graphs are presented.

**Keywords:** Cayley graph, diameter of a graph, abelian group, G-graph, expander family.

Math. Subj. Class.: 05C40, 05C42, 05C69

<footnote>*The authors sincerely thank the referee for many valuable suggestions and useful comments. The first and the fourth authors are supported by the Lebanese University research grants program.</footnote>

<footnote>E-mail addresses: mohamad.badaoui1@gmail.com (Mohamad Badaoui), alain.bretto@unicaen.fr (Alain Bretto), davidellison@polytechnique.edu (David Ellison), bmourad@ul.edu.lb (Bassam Mourad)</footnote>
# 1 Introduction

Expander graphs are sparse graphs that have strong connectivity properties. Expander constructions have found extensive applications in computer science [13, 16], in constructing of algorithms, error correcting codes [12], random walks [23], and sorting networks [1]. If one chooses at random a family of $d$-regular graphs, it is almost certain to be an expander graph [10]. Nevertheless, constructing expander families is not an easy task. Most constructions use deep algebraic and combinatorial techniques; mainly through Cayley graphs and the Zig-Zag product (see for example [15, 19]).

Like Cayley graphs, $G$-graphs are defined from groups, but they correspond to an alternative construction. These graphs, introduced in [6], have highly regular properties. In particular, because the algorithm for constructing $G$-graphs is simple, it appears to be a useful tool to construct new symmetric and semi-symmetric graphs [7]. Several extensively studied problems in graph theory such as the hamiltonicity of Cayley graphs (see e.g. [3, 18] for the latest development on this problem) may as well be approached using these objects. For instance, $G$-graphs are used to characterize new classes of Hamiltonian Cayley graphs [4], and to improve some upper bounds in the cage graphs problem [6]. Recently in [9], the authors studied some robustness properties of $G$-graphs such as edge/vertex-connectivity and vertex/edge-transitivity. It turns out, that several families of $G$-graphs are optimally connected where an optimally connected graph can be thought of as a graph whose vertex-connectivity is equal to its minimum degree. Because of their nice properties, it is natural to consider the problem of constructing an expander family of $G$-graphs.

One of the chief tools for constructing a family of expander graphs is the concept of Cayley graphs. The main advantage for using such graphs is that at first it enables us when fixing the size of the generating set, to construct a large family of sparse graphs in an effective and concise way. Additionally, the underlying properties of a group $G$ and its generating set $S$ can give us an insightful gaze on the expansion properties of its corresponding Cayley graph $Cay(G, S)$. Generally speaking, it is hard to prove that a certain family of Cayley graphs is an expander family. Concerning this, a huge amount of research in the last few decades has been devoted to dealing with the following question: which sequence of groups corresponds to an expander family of Cayley graphs? Using some algebraic techniques that depend mainly on Kazhdan constant, many partial results were obtained. In fact, most of these results gave negative answers to this question for certain groups (see [14] and [17], see also Example 3.2 below). The purpose of this article is to present a technique for constructing such families. Our construction is based on a relation between some known expander families of Cayley graphs and certain expander families of $G$-graphs. More precisely, for a group $G$ and a subset $S$ of $G$ with $S^* = \bigcup_{s \in S} \langle s \rangle \setminus \{e\}$ (i.e. if $S = \{s_1, \dots, s_k\}$, then $S^* = \{s_1, \dots, s_1^{o(s_1)-1}, \dots, s_k, \dots, s_k^{o(s_k)-1}\}$, where $o(s_i)$ denotes the order of $s_i$), we prove the following main result (see below for terminology).

**Theorem 1.1.** If $\{Cay(G_n, S_n^*)\}$ is an expander family, then $\{\tilde{\Phi}(G_n, S_n)\}$ is also an expander family.

The rest of the paper is organized as follows. In Section 2, we give a review of some basic facts concerning groups, multigraphs, $G$-graphs and expander graphs that are needed for our purposes. In Section 3, we shall prove the preceding theorem. In addition, just like in the case of Cayley graphs, we prove that abelian groups can not yield an expander family of $G$-graphs. In Sections 4 and 5, we first identify a new method for generating
# 1 Introduction

Expander graphs are sparse graphs that have strong connectivity properties. Expander constructions have found extensive applications in computer science [13, 16], in constructing of algorithms, error correcting codes [12], random walks [23], and sorting networks [1]. If one chooses at random a family of $d$-regular graphs, it is almost certain to be an expander graph [10]. Nevertheless, constructing expander families is not an easy task. Most constructions use deep algebraic and combinatorial techniques; mainly through Cayley graphs and the Zig-Zag product (see for example [15, 19]).

Like Cayley graphs, $G$-graphs are defined from groups, but they correspond to an alternative construction. These graphs, introduced in [6], have highly regular properties. In particular, because the algorithm for constructing $G$-graphs is simple, it appears to be a useful tool to construct new symmetric and semi-symmetric graphs [7]. Several extensively studied problems in graph theory such as the hamiltonicity of Cayley graphs (see e.g. [3, 18] for the latest development on this problem) may as well be approached using these objects. For instance, $G$-graphs are used to characterize new classes of Hamiltonian Cayley graphs [4], and to improve some upper bounds in the cage graphs problem [6]. Recently in [9], the authors studied some robustness properties of $G$-graphs such as edge/vertex-connectivity and vertex/edge-transitivity. It turns out, that several families of $G$-graphs are optimally connected where an optimally connected graph can be thought of as a graph whose vertex-connectivity is equal to its minimum degree. Because of their nice properties, it is natural to consider the problem of constructing an expander family of $G$-graphs.

One of the chief tools for constructing a family of expander graphs is the concept of Cayley graphs. The main advantage for using such graphs is that at first it enables us when fixing the size of the generating set, to construct a large family of sparse graphs in an effective and concise way. Additionally, the underlying properties of a group $G$ and its generating set $S$ can give us an insightful gaze on the expansion properties of its corresponding Cayley graph $Cay(G, S)$. Generally speaking, it is hard to prove that a certain family of Cayley graphs is an expander family. Concerning this, a huge amount of research in the last few decades has been devoted to dealing with the following question: which sequence of groups corresponds to an expander family of Cayley graphs? Using some algebraic techniques that depend mainly on Kazhdan constant, many partial results were obtained. In fact, most of these results gave negative answers to this question for certain groups (see [14] and [17], see also Example 3.2 below). The purpose of this article is to present a technique for constructing such families. Our construction is based on a relation between some known expander families of Cayley graphs and certain expander families of $G$-graphs. More precisely, for a group $G$ and a subset $S$ of $G$ with $S^* = \bigcup_{s \in S} \langle s \rangle \setminus \{e\}$ (i.e. if $S = \{s_1, \dots, s_k\}$, then $S^* = \{s_1, \dots, s_1^{o(s_1)-1}, \dots, s_k, \dots, s_k^{o(s_k)-1}\}$, where $o(s_i)$ denotes the order of $s_i$), we prove the following main result (see below for terminology).

**Theorem 1.1.** If $\{Cay(G_n, S_n^*)\}$ is an expander family, then $\{\tilde{\Phi}(G_n, S_n)\}$ is also an expander family.

The rest of the paper is organized as follows. In Section 2, we give a review of some basic facts concerning groups, multigraphs, $G$-graphs and expander graphs that are needed for our purposes. In Section 3, we shall prove the preceding theorem. In addition, just like in the case of Cayley graphs, we prove that abelian groups can not yield an expander family of $G$-graphs. In Sections 4 and 5, we first identify a new method for generating
an infinite regular family of Cayley graphs from another one by switching specific edges. This leads to a new infinite expander family of Cayley graphs on the projective special linear group PSL(2, $Z/pZ$). Consequently, we construct several new infinite families of expander G-graphs on the special linear group SL(2, $Z/pZ$) and projective special linear group PSL(2, $Z/pZ$). These families are formed of irregular graphs, in particular semi-regular, which are of the very few ones.

# 2 Preliminaries

This section has been designed to give a general introduction to some of the basic facts needed from the theory of groups, multigraphs, expanders and G-graphs. This introduction is given here to provide a convenient repository for all readers. We discuss briefly the material we shall require from these theories and for more details on any of these subjects, see for example [2, 11, 14, 17, 20].

## 2.1 Groups

Throughout this paper, all groups are assumed to be finite. Let $(G, \cdot, e)$ be a group, where $e$ denotes the identity element of $G$ and “:” denotes the group operation (multiplicative notation). For every $g$ in $G$ we define the order of $g$, denoted by $o(g)$, as the smallest integer $l$ such that $g^l = e$. Let $S = \{s_1, \dots, s_k\}$ be a non-empty subset of $G$, and let $O_{\max}(S)$ and $O_{\min}(S)$ be respectively the maximum and the minimum $o(s_i)$ for all $i \in \{1, \dots, k\}$. A subset $S$ of $G$ is said to be *symmetric* if every element in $S$ has its inverse in $S$. We define $\langle S \rangle$ to be the smallest subgroup of $G$ which contains $S$. If $\langle S \rangle = G$, then set $S$ is said to be a *generating set* of $G$, or $G$ is *generated* by $S$. If $H$ is a subgroup of $G$ then the set $Hx$ is called right coset of $H$ in $G$, and we denote by $G/H$ to be the set of all right cosets of $H$ in $G$. A subset $T_H$ of $G$ is said to be a *right transversal* for $H$ if $T_H$ contains exactly one element from each right coset of $H$ in $G$. Let $A$ and $B$ be subsets of a set $U$, then we denote $B \setminus A = \{x \in B \text{ and } x \notin A\}$ and $\bar{A} = U \setminus A$. The special linear group SL(2, $Z/qZ$) is defined as follows:

$$ \mathrm{SL}(2, \mathbb{Z}/q\mathbb{Z}) = \left\{ \begin{pmatrix} a_1 & a_2 \\ a_3 & a_4 \end{pmatrix} ; a_1, a_2, a_3, a_4 \in \mathbb{Z}/q\mathbb{Z} \text{ and } a_1a_4 - a_2a_3 = 1 \right\}. $$

The projective special linear group $\mathrm{PSL}(2, \mathbb{Z}/q\mathbb{Z}) = \mathrm{SL}(2, \mathbb{Z}/q\mathbb{Z}) / \{\pm I_2\}$, where $I_2$ is the $2 \times 2$ identity matrix.

## 2.2 Multigraphs

All multigraphs considered in this paper are undirected and finite. Generally, we define an *undirected multigraph* $\Gamma$ as the triple $(V(\Gamma), E(\Gamma), \xi_{\Gamma})$, where $V(\Gamma)$ is the *set of vertices*, $E(\Gamma)$ is the *set of edges*, and $\xi_{\Gamma}$ is an incidence function that associates with each edge of $\Gamma$ an unordered pair of vertices of $\Gamma$. In addition, we denote by $\{u, v\}$ the multi-edge that links vertices $u$ and $v$. The multiplicity of the multi-edge $\{u, v\}$ is the cardinality of the set of edges that links $u$ and $v$. A multi-edge with identical end-points is called a *loop*. A multigraph is a *simple graph* if it has neither loops nor multi-edges with multiplicity greater than or equal to 2.

The *neighborhood* of vertex $u$ denoted by $N(u)$ is the set of all vertices that are adjacent to $u$. The *degree* of a vertex $v$ in a multigraph $\Gamma$, denoted by $d(v)$ is the number of edges
an infinite regular family of Cayley graphs from another one by switching specific edges. This leads to a new infinite expander family of Cayley graphs on the projective special linear group PSL(2, $Z/pZ$). Consequently, we construct several new infinite families of expander G-graphs on the special linear group SL(2, $Z/pZ$) and projective special linear group PSL(2, $Z/pZ$). These families are formed of irregular graphs, in particular semi-regular, which are of the very few ones.

# 2 Preliminaries

This section has been designed to give a general introduction to some of the basic facts needed from the theory of groups, multigraphs, expanders and G-graphs. This introduction is given here to provide a convenient repository for all readers. We discuss briefly the material we shall require from these theories and for more details on any of these subjects, see for example [2, 11, 14, 17, 20].

## 2.1 Groups

Throughout this paper, all groups are assumed to be finite. Let $(G, \cdot, e)$ be a group, where $e$ denotes the identity element of $G$ and “:” denotes the group operation (multiplicative notation). For every $g$ in $G$ we define the order of $g$, denoted by $o(g)$, as the smallest integer $l$ such that $g^l = e$. Let $S = \{s_1, \dots, s_k\}$ be a non-empty subset of $G$, and let $O_{\max}(S)$ and $O_{\min}(S)$ be respectively the maximum and the minimum $o(s_i)$ for all $i \in \{1, \dots, k\}$. A subset $S$ of $G$ is said to be *symmetric* if every element in $S$ has its inverse in $S$. We define $\langle S \rangle$ to be the smallest subgroup of $G$ which contains $S$. If $\langle S \rangle = G$, then set $S$ is said to be a *generating set* of $G$, or $G$ is *generated* by $S$. If $H$ is a subgroup of $G$ then the set $Hx$ is called right coset of $H$ in $G$, and we denote by $G/H$ to be the set of all right cosets of $H$ in $G$. A subset $T_H$ of $G$ is said to be a *right transversal* for $H$ if $T_H$ contains exactly one element from each right coset of $H$ in $G$. Let $A$ and $B$ be subsets of a set $U$, then we denote $B \setminus A = \{x \in B \text{ and } x \notin A\}$ and $\bar{A} = U \setminus A$. The special linear group SL(2, $Z/qZ$) is defined as follows:

$$ \mathrm{SL}(2, \mathbb{Z}/q\mathbb{Z}) = \left\{ \begin{pmatrix} a_1 & a_2 \\ a_3 & a_4 \end{pmatrix} ; a_1, a_2, a_3, a_4 \in \mathbb{Z}/q\mathbb{Z} \text{ and } a_1a_4 - a_2a_3 = 1 \right\}. $$

The projective special linear group $\mathrm{PSL}(2, \mathbb{Z}/q\mathbb{Z}) = \mathrm{SL}(2, \mathbb{Z}/q\mathbb{Z}) / \{\pm I_2\}$, where $I_2$ is the $2 \times 2$ identity matrix.

## 2.2 Multigraphs

All multigraphs considered in this paper are undirected and finite. Generally, we define an *undirected multigraph* $\Gamma$ as the triple $(V(\Gamma), E(\Gamma), \xi_{\Gamma})$, where $V(\Gamma)$ is the set of vertices, $E(\Gamma)$ is the set of edges, and $\xi_{\Gamma}$ is an incidence function that associates with each edge of $\Gamma$ an unordered pair of vertices of $\Gamma$. In addition, we denote by $\{u, v\}$ the multi-edge that links vertices $u$ and $v$. The multiplicity of the multi-edge $\{u, v\}$ is the cardinality of the set of edges that links $u$ and $v$. A multi-edge with identical end-points is called a *loop*. A multigraph is a *simple graph* if it has neither loops nor multi-edges with multiplicity greater than or equal to 2.

The *neighborhood* of vertex $u$ denoted by $N(u)$ is the set of all vertices that are adjacent to $u$. The *degree* of a vertex $v$ in a multigraph $\Gamma$, denoted by $d(v)$ is the number of edges
of $\Gamma$ incident to $v$ where each loop counts as two edges. The maximum and minimum degree of a multigraph $\Gamma$ are denoted by $\Delta(\Gamma)$ and $\delta(\Gamma)$ respectively. A multigraph $\Gamma$ is $d$-regular if $d(u) = d$ for all $u \in V(\Gamma)$. A family of $d$-regular multigraphs is formed of regular multigraphs where each has degree $d$, while a family of regular multigraphs is formed of regular multigraphs with possibly varying degrees. The distance $d(u, v)$ between two vertices $u$ and $v$ is the number of edges in a shortest path that connects $u$ and $v$. The diameter diam($\Gamma$) of a multigraph $\Gamma$ is defined by:

$$ \mathrm{diam}(\Gamma) = \max\{d(u, v); u, v \in V(\Gamma)\}. $$

Let $\Gamma_1 = (V_1, E_1, \xi_1)$ and $\Gamma_2 = (V_2, E_2, \xi_2)$ be two multigraphs, a homomorphism from $\Gamma_1$ to $\Gamma_2$ is a couple $(f, f^\#)$ where $f: V_1 \to V_2$ and $f^\# : E_1 \to E_2$ such that if $\xi_1(a) = \{u, v\}$ then $\xi_2(f^\#(a)) = \{f(u), f(v)\}$. A graph isomorphism is the couple $(f, f^\#)$ where $f$ and $f^\#$ are bijective. We say that $\Gamma_1$ is isomorphic to $\Gamma_2$ if there exists an isomorphism between $\Gamma_1$ and $\Gamma_2$. In such a case, we write $\Gamma \simeq \Gamma'$.

A multigraph $\Gamma = (V, E, \xi_\Gamma)$ is $k$-partite if there is a partition of $V$ into $k$ parts such that each part is a stable set. We will write $\Gamma = (\bigsqcup_{i \in I} V_i; E)$ where $I = \{1, \dots, k\}$. A multigraph is minimum $k$-partite ($k \ge 1$) if it is $k$-partite and not $(k-1)$-partite. It is easy to verify that for any multigraph $\Gamma$, there exists $k$ such that $\Gamma$ is minimum $k$-partite. If a multigraph $\Gamma$ is $k$-partite, then we will say that $(V_i)_{i \in \{1, 2, \dots, k\}}$ is a $k$-representation of $\Gamma$.

Cayley graphs offer a combinatorial depiction of groups and their generators. More precisely, the Cayley graph $\mathrm{Cay}(G, S)$ is the multigraph with vertex set $G$ and two elements $x$ and $y$ of $G$ are adjacent if and only if $y = s \cdot x$ for some $s \in S$. It is well-known that $\mathrm{Cay}(G, S)$ is connected if and only if $G = \langle S \rangle$ (see for example [14]).

## 2.3 G-graphs

**Definition 2.1.** Let $(G, \cdot, e)$ be a finite group. Let $S$ be a nonempty subset of $G$. For $s \in S$, consider the cycles $(s)x = (x, sx, \dots, s^{o(s)^{-1}}x)$ of permutation $g_s : x \mapsto sx$. Note that $\langle s \rangle x$ is the set $\{x, sx, \dots, s^{o(s)^{-1}}x\}$. We define the $G$-graph $\Phi(G, S)$ in the following way:

1. The vertex set of $\Phi(G, S)$ is $V = \bigsqcup_{s \in S} V_s$ where $V_s = \{(s)x, x \in T_{\langle s \rangle}\}$ where $T_{\langle s \rangle}$ is a right transversal for the subgroup $\langle s \rangle$.

2. For each $(s)x, (t)y \in V$, there exists edge between $(s)x$ and $(t)y$ labeled $g$ for each $g \in \langle s \rangle x \cap \langle t \rangle y$, such an edge will be denoted by $(\{(s)x, (t)y\}, g)$. If $\mathrm{card}(\langle s \rangle x \cap \langle t \rangle y) = p, p \ge 1$ then there exists $p$ labeled edges between $(s)x$ and $(t)y$, or $\{(s)x, (t)y\}$ is a multi-edge with multiplicity $p$.

Since the cosets of $\langle s \rangle$ form a partition of $G$, $(V_s)_{s \in S}$ is a $|S|$-representation of $\Phi(G, S)$. Every vertex $(s)x$ has $o(s)$ loops. We denote by $\tilde{\Phi}(G, S)$ the multigraph $\Phi(G, S)$ without loops. The multigraph $\tilde{\Phi}(G, S)$ is the simple graph underlying $\Phi(G, S)$, that is, the vertices $(s)x$ and $(t)y$ in $V(\tilde{\Phi}(G, S))$ are connected by a single edge if $\langle s \rangle x \cap \langle t \rangle y$ is non-empty. If $S = \{s_1, \dots, s_k\}$ then the level of any $s_i$, noted $V_{s_i}$ (or simply $V_i$), is the stable set of $\tilde{\Phi}(G, S)$ which comprises all the vertices of the form $(s_i)x$ where $x \in G$. Note that each level $V_s$ contains $\frac{|G|}{o(s)}$ vertices, therefore we have the following relation:

$$ |V(\tilde{\Phi}(G, S))| = |G| \sum_{s \in S} \frac{1}{o(s)}. $$
of $\Gamma$ incident to $v$ where each loop counts as two edges. The maximum and minimum degree of a multigraph $\Gamma$ are denoted by $\Delta(\Gamma)$ and $\delta(\Gamma)$ respectively. A multigraph $\Gamma$ is $d$-regular if $d(u) = d$ for all $u \in V(\Gamma)$. A family of $d$-regular multigraphs is formed of regular multigraphs where each has degree $d$, while a family of regular multigraphs is formed of regular multigraphs with possibly varying degrees. The distance $d(u, v)$ between two vertices $u$ and $v$ is the number of edges in a shortest path that connects $u$ and $v$. The diameter diam($\Gamma$) of a multigraph $\Gamma$ is defined by:

$$ \mathrm{diam}(\Gamma) = \max\{d(u, v); u, v \in V(\Gamma)\}. $$

Let $\Gamma_1 = (V_1, E_1, \xi_1)$ and $\Gamma_2 = (V_2, E_2, \xi_2)$ be two multigraphs, a homomorphism from $\Gamma_1$ to $\Gamma_2$ is a couple $(f, f^\#)$ where $f: V_1 \to V_2$ and $f^\#: E_1 \to E_2$ such that if $\xi_1(a) = \{u, v\}$ then $\xi_2(f^\#(a)) = \{f(u), f(v)\}$. A graph isomorphism is the couple $(f, f^\#)$ where $f$ and $f^\#$ are bijective. We say that $\Gamma_1$ is isomorphic to $\Gamma_2$ if there exists an isomorphism between $\Gamma_1$ and $\Gamma_2$. In such a case, we write $\Gamma \simeq \Gamma'$.

A multigraph $\Gamma = (V, E, \xi_\Gamma)$ is $k$-partite if there is a partition of $V$ into $k$ parts such that each part is a stable set. We will write $\Gamma = (\bigsqcup_{i \in I} V_i; E)$ where $I = \{1, \dots, k\}$. A multigraph is minimum $k$-partite ($k \ge 1$) if it is $k$-partite and not $(k-1)$-partite. It is easy to verify that for any multigraph $\Gamma$, there exists $k$ such that $\Gamma$ is minimum $k$-partite. If a multigraph $\Gamma$ is $k$-partite, then we will say that $(V_i)_{i \in \{1, 2, \dots, k\}}$ is a $k$-representation of $\Gamma$.

Cayley graphs offer a combinatorial depiction of groups and their generators. More precisely, the Cayley graph $\mathrm{Cay}(G, S)$ is the multigraph with vertex set $G$ and two elements $x$ and $y$ of $G$ are adjacent if and only if $y = s \cdot x$ for some $s \in S$. It is well-known that $\mathrm{Cay}(G, S)$ is connected if and only if $G = \langle S \rangle$ (see for example [14]).

## 2.3 G-graphs

**Definition 2.1.** Let $(G, \cdot, e)$ be a finite group. Let $S$ be a nonempty subset of $G$. For $s \in S$, consider the cycles $(s)x = (x, sx, \dots, s^{o(s)^{-1}}x)$ of permutation $g_s: x \mapsto sx$. Note that $\langle s \rangle x$ is the set $\{x, sx, \dots, s^{o(s)^{-1}}x\}$. We define the $G$-graph $\Phi(G, S)$ in the following way:

1. The vertex set of $\Phi(G, S)$ is $V = \bigsqcup_{s \in S} V_s$ where $V_s = \{(s)x, x \in T_{\langle s \rangle}\}$ where $T_{\langle s \rangle}$ is a right transversal for the subgroup $\langle s \rangle$.

2. For each $(s)x, (t)y \in V$, there exists edge between $(s)x$ and $(t)y$ labeled $g$ for each $g \in \langle s \rangle x \cap \langle t \rangle y$, such an edge will be denoted by $(\{(s)x, (t)y\}, g)$. If $\mathrm{card}(\langle s \rangle x \cap \langle t \rangle y) = p, p \ge 1$ then there exists $p$ labeled edges between $(s)x$ and $(t)y$, or $\{(s)x, (t)y\}$ is a multi-edge with multiplicity $p$.

Since the cosets of $\langle s \rangle$ form a partition of $G$, $(V_s)_{s \in S}$ is a $|S|$-representation of $\Phi(G, S)$. Every vertex $(s)x$ has $o(s)$ loops. We denote by $\tilde{\Phi}(G, S)$ the multigraph $\Phi(G, S)$ without loops. The multigraph $\tilde{\Phi}(G, S)$ is the simple graph underlying $\Phi(G, S)$, that is, the vertices $(s)x$ and $(t)y$ in $V(\tilde{\Phi}(G, S))$ are connected by a single edge if $\langle s \rangle x \cap \langle t \rangle y$ is non-empty. If $S = \{s_1, \dots, s_k\}$ then the level of any $s_i$, noted $V_{s_i}$ (or simply $V_i$), is the stable set of $\tilde{\Phi}(G, S)$ which comprises all the vertices of the form $(s_i)x$ where $x \in G$. Note that each level $V_s$ contains $\frac{|G|}{o(s)}$ vertices, therefore we have the following relation:

$$ |V(\tilde{\Phi}(G, S))| = |G| \sum_{s \in S} \frac{1}{o(s)}. $$
The principal clique<fnref n="1" /> of $x \in G$, denoted by $C_x$, is the subgraph of $\tilde{\Phi}(G, S)$ induced by the set of vertices which contain $x$. In $\tilde{\Phi}(G, S)$ there are $|G|$ principal cliques; each contains $|S|$ vertices.

**Example 2.2.** Let $G$ be the cyclic group of order 6, i.e. $G = \{e, a, a^2, a^3, a^4, a^5\}$. Clearly $G$ can be generated by an element of order 3 and another of order 2. Let $S$ be $\{a^2, a^3\}$. Then the vertices of the corresponding $G$-graph without loops $\tilde{\Phi}(G, S)$ are

$$ (a^2)e = (e, a^2e, a^4e) = (e, a^2, a^4), \quad (a^2)a = (a, a^2a, a^4a) = (a, a^3, a^5) $$

which are the 3-cycles and

$$ (a^3)e = (e, a^3), \quad (a^3)a = (a, a^3a) = (a, a^4), \quad (a^3)a^2 = (a^2, a^3a^2) = (a^2, a^5) $$

which are the 2-cycles. Obviously, in this case the multigraph $\tilde{\Phi}(G, S)$ is isomorphic to $K_{2,3}$ (Figure 1). The levels $V_{a^2}$ and $V_{a^3}$ are respectively $\{(a^2)e, (a^2)a\}$ and $\{(a^3)e, (a^3)a, (a^3)a^2\}$. There are 6 principal cliques each of size $|S| = 2$. For instance, the principal cliques $C_e$ and $C_a$ are the induced subgraphs of $\tilde{\Phi}(G, S)$ with vertex set $\{(a^2)e, (a^3)e\}$ and $\{(a^2)a, (a^3)a\}$ respectively.

<figure><img src="image_2.png" /><figcaption>Figure 1: The bipartite multigraph $K_{2,3}$.</figcaption></figure>

The next 3 propositions can be found in [5].

**Proposition 2.3 ([5]).** $\Phi(G, S)$ and $\tilde{\Phi}(G, S)$ are minimum $|S|$-partite graphs.

**Proposition 2.4 ([5]).** $\tilde{\Phi}(G, S)$ is connected if and only if $S$ is a generating set of $G$.

**Proposition 2.5 ([5]).** Let $\tilde{\Phi}(G, S) = (\bigcup_{s \in S} V_s; E)$ be a $G$-graph with $|G| = n$ and $|S| = k$. Then the following holds.

$$ d((s)x) = o(s)(k-1), \quad \text{for all } (s)x \in V_s, $$

$$ \sum_{(s)x \in V_s} d((s)x) = n(k-1), \quad \text{for all } s \in S, $$

$$ |E(\tilde{\Phi}(G, S))| = \frac{nk(k-1)}{2}. $$

### 2.3.1 New results on $G$-graphs

**Proposition 2.6.** Let $\tilde{\Phi}(G, S)$ be any $G$-graph such that $|S| = \{s_1, \dots, s_k\}$. Then the following are equivalent:

<footnote n="1">¹This definition is due to [4].</footnote>
The principal clique<fnref n="1" /> of $x \in G$, denoted by $C_x$, is the subgraph of $\tilde{\Phi}(G, S)$ induced by the set of vertices which contain $x$. In $\tilde{\Phi}(G, S)$ there are $|G|$ principal cliques; each contains $|S|$ vertices.

**Example 2.2.** Let $G$ be the cyclic group of order 6, i.e. $G = \{e, a, a^2, a^3, a^4, a^5\}$. Clearly $G$ can be generated by an element of order 3 and another of order 2. Let $S$ be $\{a^2, a^3\}$. Then the vertices of the corresponding $G$-graph without loops $\tilde{\Phi}(G, S)$ are

$$(a^2)e = (e, a^2e, a^4e) = (e, a^2, a^4), \quad (a^2)a = (a, a^2a, a^4a) = (a, a^3, a^5)$$

which are the 3-cycles and

$$(a^3)e = (e, a^3), \quad (a^3)a = (a, a^3a) = (a, a^4), \quad (a^3)a^2 = (a^2, a^3a^2) = (a^2, a^5)$$

which are the 2-cycles. Obviously, in this case the multigraph $\tilde{\Phi}(G, S)$ is isomorphic to $K_{2,3}$ (Figure 1). The levels $V_{a^2}$ and $V_{a^3}$ are respectively $\{(a^2)e, (a^2)a\}$ and $\{(a^3)e, (a^3)a, (a^3)a^2\}$. There are 6 principal cliques each of size $|S| = 2$. For instance, the principal cliques $C_e$ and $C_a$ are the induced subgraphs of $\tilde{\Phi}(G, S)$ with vertex set $\{(a^2)e, (a^3)e\}$ and $\{(a^2)a, (a^3)a\}$ respectively.

<figure><img src="image_2.png" /><figcaption>Figure 1: The bipartite multigraph $K_{2,3}$.</figcaption></figure>

The next 3 propositions can be found in [5].

**Proposition 2.3 ([5]).** $\Phi(G, S)$ and $\tilde{\Phi}(G, S)$ are minimum $|S|$-partite graphs.

**Proposition 2.4 ([5]).** $\tilde{\Phi}(G, S)$ is connected if and only if $S$ is a generating set of $G$.

**Proposition 2.5 ([5]).** Let $\tilde{\Phi}(G, S) = (\bigcup_{s \in S} V_s; E)$ be a $G$-graph with $|G| = n$ and $|S| = k$. Then the following holds.

$$d((s)x) = o(s)(k-1), \quad \text{for all } (s)x \in V_s,$$

$$\sum_{(s)x \in V_s} d((s)x) = n(k-1), \quad \text{for all } s \in S,$$

$$|E(\tilde{\Phi}(G, S))| = \frac{nk(k-1)}{2}.$$

### 2.3.1 New results on $G$-graphs

**Proposition 2.6.** Let $\tilde{\Phi}(G, S)$ be any $G$-graph such that $|S| = \{s_1, \dots, s_k\}$. Then the following are equivalent:

<footnote n="1">¹This definition is due to [4].</footnote>
i. $\tilde{\Phi}(G, S)$ is $d$-regular,

ii. $o(s_i) = \frac{d}{k-1}$, for all $i \in \{1, \dots, k\}$,

iii. $|V_{s_i}| = |V_{s_j}|$, for all $i, j \in \{1, \dots, k\}$.

*Proof.* Let $(s)x \in V_s$, where $s \in S$. From Proposition 2.5, we have

$$d((s)x) = o(s)(k-1) \quad \text{or} \quad o(s) = \frac{d((s)x)}{k-1},$$

and then

$$|V_s| = \frac{|G|}{o(s)} = \frac{|G|(k-1)}{d((s)x)}.$$

Therefore $o(s_i) = o(s_j)$ if and only if $|V_{s_i}| = |V_{s_j}|$, for all $i, j \in \{1, \dots, k\}$. $\square$

<figure><img src="image_3.png" /></figure>

**Remark 2.7.** When $\tilde{\Phi}(G, S)$ is a regular multigraph, we use the notation $O$ instead of $o(s)$ for any $s \in S$.

The following lemma can be found in [22].

**Lemma 2.8 ([22]).** Let $\Phi(G, S)$ be a $G$-graph with $S = \{s_1, \dots, s_k\}$ a generating set of $G$, then all the multi-edges between levels $V_{s_i}$ and $V_{s_j}$ have the same multiplicity $|\langle s_i \rangle \cap \langle s_j \rangle|$.

As a result, we have the following corollary.

**Corollary 2.9.** Let $\tilde{\Phi}(G, S)$ be a $G$-graph with $S = \{s_1, \dots, s_k\}$. Then $\tilde{\Phi}(G, S)$ is a simple graph if and only if $\langle s_i \rangle \cap \langle s_j \rangle = \{e\}$ for all $i, j \in \{1, \dots, k\}$ with $i \neq j$.

## 2.4 Expanders

Before we define expander graphs, we need to define some expansion parameters. Let $\Gamma = (V, E, \xi_\Gamma)$ be a non-oriented multigraph with $|V| \ge 2$ and $V'$ be a subset of $V$. The edge boundary of $V'$ in $\Gamma$ denoted by $\partial V'(\Gamma)$ (or simply $\partial V'$ when no ambiguity occurs) is defined as follows:

$$\partial V'(\Gamma) = \{\alpha \in E; \xi_\Gamma(\alpha) \in V' \times \bar{V}'\}.$$

In other words, this is the set of edges emanating from the set $V'$ to its complement. The rate of expansion of $\Gamma$ is then defined as follows:

$$h(\Gamma) = \min_{0 < |V'| \le \frac{|V|}{2}} \frac{|\partial V'|}{|V'|}.$$

**Definition 2.10.** For $\epsilon \in \mathbb{R}_+^*$, a multigraph $\Gamma$ is said to be an $\epsilon$-expander if

$$\epsilon \le h(\Gamma).$$

**Definition 2.11.** If a family of multigraphs $\{\Gamma_i = (V_i, E_i, \xi_i), i \in \mathbb{N}^+\}$ satisfies the following three conditions:

i. $|V_i| \to \infty$ as $i \to \infty$,
i. $\tilde{\Phi}(G, S)$ is $d$-regular,

ii. $o(s_i) = \frac{d}{k-1}$, for all $i \in \{1, \dots, k\}$,

iii. $|V_{s_i}| = |V_{s_j}|$, for all $i, j \in \{1, \dots, k\}$.

*Proof.* Let $(s)x \in V_s$, where $s \in S$. From Proposition 2.5, we have

$$d((s)x) = o(s)(k-1) \quad \text{or} \quad o(s) = \frac{d((s)x)}{k-1},$$

and then

$$|V_s| = \frac{|G|}{o(s)} = \frac{|G|(k-1)}{d((s)x)}.$$

Therefore $o(s_i) = o(s_j)$ if and only if $|V_{s_i}| = |V_{s_j}|$, for all $i, j \in \{1, \dots, k\}$. $\square$

<figure><img src="image_3.png" /></figure>

**Remark 2.7.** When $\tilde{\Phi}(G, S)$ is a regular multigraph, we use the notation $O$ instead of $o(s)$ for any $s \in S$.

The following lemma can be found in [22].

**Lemma 2.8 ([22]).** Let $\Phi(G, S)$ be a $G$-graph with $S = \{s_1, \dots, s_k\}$ a generating set of $G$, then all the multi-edges between levels $V_{s_i}$ and $V_{s_j}$ have the same multiplicity $|\langle s_i \rangle \cap \langle s_j \rangle|$.

As a result, we have the following corollary.

**Corollary 2.9.** Let $\tilde{\Phi}(G, S)$ be a $G$-graph with $S = \{s_1, \dots, s_k\}$. Then $\tilde{\Phi}(G, S)$ is a simple graph if and only if $\langle s_i \rangle \cap \langle s_j \rangle = \{e\}$ for all $i, j \in \{1, \dots, k\}$ with $i \neq j$.

## 2.4 Expanders

Before we define expander graphs, we need to define some expansion parameters. Let $\Gamma = (V, E, \xi_\Gamma)$ be a non-oriented multigraph with $|V| \ge 2$ and $V'$ be a subset of $V$. The edge boundary of $V'$ in $\Gamma$ denoted by $\partial V'(\Gamma)$ (or simply $\partial V'$ when no ambiguity occurs) is defined as follows:

$$\partial V'(\Gamma) = \{\alpha \in E; \xi_\Gamma(\alpha) \in V' \times \bar{V}'\}.$$

In other words, this is the set of edges emanating from the set $V'$ to its complement. The rate of expansion of $\Gamma$ is then defined as follows:

$$h(\Gamma) = \min_{0 < |V'| \le \frac{|V|}{2}} \frac{|\partial V'|}{|V'|}.$$

**Definition 2.10.** For $\epsilon \in \mathbb{R}_+^*$, a multigraph $\Gamma$ is said to be an $\epsilon$-expander if

$$\epsilon \le h(\Gamma).$$

**Definition 2.11.** If a family of multigraphs $\{\Gamma_i = (V_i, E_i, \xi_i), i \in \mathbb{N}^+\}$ satisfies the following three conditions:

i. $|V_i| \to \infty$ as $i \to \infty$,
ii. There exists $r \in \mathbb{N}^+$ such that $\Delta(\Gamma_i) \le r$ for all $i \in \mathbb{N}^+$. That is $\{\Gamma_i, i \in \mathbb{N}^+\}$ is a sequence of bounded degree multigraphs,

iii. There exists $\epsilon \in \mathbb{R}_+^*$ such that $\Gamma_i$ is an $\epsilon$-expander for all $i \in \mathbb{N}^+$,

then this family is called an *扩增器 family* and an element of this family is an *扩增器 graph*.

If $\Gamma$ is a $d$-regular multigraph, then in [14] it is proved that $\log_d|V(\Gamma)| \le \text{diam}(\Gamma)$. The next proposition is a simple generalization of this result.

**Proposition 2.12.** Let $\Gamma$ be a connected multigraph such that $\Delta(\Gamma) \le r \in \mathbb{N}^+$. Then

$$ \log_r |V(\Gamma)| \le \text{diam}(\Gamma). $$

*Proof.* Consider $v \in V(\Gamma)$ and define $B_l(v) = \{u \in V(\Gamma); d(v, u) \le l\}$. We show by induction that $|B_l(v)| \le r^l$. The result is trivial for $l=0$. Suppose it is true up to $l-1$ and let's prove it for $l$. Since every vertex in $B_{l-1}(v)$ has at most $r-1$ neighbors in $B_{l-1}(v)$, then $|B_l(v)| \le (r-1)|B_{l-1}(v)| + |B_{l-1}(v)| = r|B_{l-1}(v)| \le rr^{l-1} = r^l$. If $l = \text{diam}(\Gamma)$, then $B_l(v) = V(\Gamma)$ and therefore $|V(\Gamma)| \le r^{\text{diam}(\Gamma)}$. $\square$

# 3 Cay-expanders and G-expanders

In this section, we are mainly concerned with proving Theorem 1.1. First, we need to introduce more auxiliary materials. We start with the following definition which is virtually an interpretation of Definition 2.11 for the G-graph and Cayley graph cases.

**Definition 3.1.** Let $\{G_i, i \in \mathbb{N}^+\}$ be a family of finite groups. We say that $\{G_i, i \in \mathbb{N}^+\}$ is a *G-expander family*, if for every $i \in \mathbb{N}^+$ there exists a generating subset $S_i$ of $G_i$ such that $\{\tilde{\Phi}(G_i, S_i), i \in \mathbb{N}^+\}$ is an expander family. More precisely, $\{G_i, i \in \mathbb{N}^+\}$ is a *G-expander family* if the following 3 conditions are satisfied:

i. $|V(\tilde{\Phi}(G_i, S_i))| = |G_i| \sum_{s \in S_i} \frac{1}{o(s)} \to \infty$ as $i \to \infty$.

ii. There exists a positive integer $r$ such that $\Delta(\tilde{\Phi}(G_i, S_i)) \le r$ for all $i \in \mathbb{N}^+$ which by Proposition 2.5 means that for every $(s)x \in V_s$ we have $d((s)x) = (|S_i| - 1)\alpha(s) \le \Delta(\tilde{\Phi}(G_i, S_i)) \le r \in \mathbb{N}^+$ for all $i \in \mathbb{N}^+$. This in turn means that there exists $r_1, r_2 \in \mathbb{N}^+$ such that $2 \le |S_i| \le r_1$ and $\alpha(s) \le r_2$ for all $s \in S_i$ and for all $i \in \mathbb{N}^+$. In addition, since $\Delta(\tilde{\Phi}(G_i, S_i)) \le r$ for all $i \in \mathbb{N}^+$, then clearly Condition i. is equivalent to saying that $|G_i| \to \infty$ as $i \to \infty$.

iii. There exists an $\epsilon \in \mathbb{R}_+^*$ such that $\epsilon \le h(\tilde{\Phi}(G_i, S_i))$ for all $i \in \mathbb{N}^+$.

Note that $2 \le |S_i|$ since otherwise $\tilde{\Phi}(G_i, S_i)$ will be a disconnected multigraph so that $h(\tilde{\Phi}(G_i, S_i)) = 0$, and so it is clear that $\max\{r_1, r_2\} \le r$.

On the other hand, we say that $\{G_i, i \in \mathbb{N}^+\}$ is a *Cay-expander family*, if for every $i \in \mathbb{N}^+$ there exists a symmetric generating subset $S_i$ of $G_i$ such that $\{|S_i| : i \in \mathbb{N}^+\}$ is uniformly bounded and provided that $\{\text{Cay}(G_i, S_i), i \in \mathbb{N}^+\}$ is an expander family. More explicitly, $\{G_i, i \in \mathbb{N}^+\}$ is a *Cay-expander family* if the following 2 conditions are satisfied:

i. $|V(\text{Cay}(G_i, S_i))| = |G_i| \to \infty$ as $i \to \infty$,
ii. There exists $r \in \mathbb{N}^+$ such that $\Delta(\Gamma_i) \le r$ for all $i \in \mathbb{N}^+$. That is $\{\Gamma_i, i \in \mathbb{N}^+\}$ is a sequence of bounded degree multigraphs,

iii. There exists $\epsilon \in \mathbb{R}_+^*$ such that $\Gamma_i$ is an $\epsilon$-expander for all $i \in \mathbb{N}^+$,

then this family is called an *扩增器 family* and an element of this family is an *扩增器 graph*.

If $\Gamma$ is a $d$-regular multigraph, then in [14] it is proved that $\log_d|V(\Gamma)| \le \text{diam}(\Gamma)$. The next proposition is a simple generalization of this result.

**Proposition 2.12.** Let $\Gamma$ be a connected multigraph such that $\Delta(\Gamma) \le r \in \mathbb{N}^+$. Then

$$ \log_r |V(\Gamma)| \le \text{diam}(\Gamma). $$

*Proof.* Consider $v \in V(\Gamma)$ and define $B_l(v) = \{u \in V(\Gamma); d(v, u) \le l\}$. We show by induction that $|B_l(v)| \le r^l$. The result is trivial for $l=0$. Suppose it is true up to $l-1$ and let's prove it for $l$. Since every vertex in $B_{l-1}(v)$ has at most $r-1$ neighbors in $B_{l-1}(v)$, then $|B_l(v)| \le (r-1)|B_{l-1}(v)| + |B_{l-1}(v)| = r|B_{l-1}(v)| \le rr^{l-1} = r^l$. If $l = \text{diam}(\Gamma)$, then $B_l(v) = V(\Gamma)$ and therefore $|V(\Gamma)| \le r^{\text{diam}(\Gamma)}$. $\square$

# 3 Cay-expanders and G-expanders

In this section, we are mainly concerned with proving Theorem 1.1. First, we need to introduce more auxiliary materials. We start with the following definition which is virtually an interpretation of Definition 2.11 for the G-graph and Cayley graph cases.

**Definition 3.1.** Let $\{G_i, i \in \mathbb{N}^+\}$ be a family of finite groups. We say that $\{G_i, i \in \mathbb{N}^+\}$ is a *G-expander family*, if for every $i \in \mathbb{N}^+$ there exists a generating subset $S_i$ of $G_i$ such that $\{\tilde{\Phi}(G_i, S_i), i \in \mathbb{N}^+\}$ is an expander family. More precisely, $\{G_i, i \in \mathbb{N}^+\}$ is a *G-expander family* if the following 3 conditions are satisfied:

i. $|V(\tilde{\Phi}(G_i, S_i))| = |G_i| \sum_{s \in S_i} \frac{1}{o(s)} \to \infty$ as $i \to \infty$.

ii. There exists a positive integer $r$ such that $\Delta(\tilde{\Phi}(G_i, S_i)) \le r$ for all $i \in \mathbb{N}^+$ which by Proposition 2.5 means that for every $(s)x \in V_s$ we have $d((s)x) = (|S_i| - 1)\omega(s) \le \Delta(\tilde{\Phi}(G_i, S_i)) \le r \in \mathbb{N}^+$ for all $i \in \mathbb{N}^+$. This in turn means that there exists $r_1, r_2 \in \mathbb{N}^+$ such that $2 \le |S_i| \le r_1$ and $\omega(s) \le r_2$ for all $s \in S_i$ and for all $i \in \mathbb{N}^+$. In addition, since $\Delta(\tilde{\Phi}(G_i, S_i)) \le r$ for all $i \in \mathbb{N}^+$, then clearly Condition i. is equivalent to saying that $|G_i| \to \infty$ as $i \to \infty$.

iii. There exists an $\epsilon \in \mathbb{R}_+^*$ such that $\epsilon \le h(\tilde{\Phi}(G_i, S_i))$ for all $i \in \mathbb{N}^+$.

Note that $2 \le |S_i|$ since otherwise $\tilde{\Phi}(G_i, S_i)$ will be a disconnected multigraph so that $h(\tilde{\Phi}(G_i, S_i)) = 0$, and so it is clear that $\max\{r_1, r_2\} \le r$.

On the other hand, we say that $\{G_i, i \in \mathbb{N}^+\}$ is a *Cay-expander family*, if for every $i \in \mathbb{N}^+$ there exists a symmetric generating subset $S_i$ of $G_i$ such that $\{|S_i| : i \in \mathbb{N}^+\}$ is uniformly bounded and provided that $\{\text{Cay}(G_i, S_i), i \in \mathbb{N}^+\}$ is an expander family. More explicitly, $\{G_i, i \in \mathbb{N}^+\}$ is a *Cay-expander family* if the following 2 conditions are satisfied:

i. $|V(\text{Cay}(G_i, S_i))| = |G_i| \to \infty$ as $i \to \infty$,
ii. There exists an $\epsilon \in \mathbb{R}_+^*$ such that $\epsilon \le h(\text{Cay}(G_i, S_i))$ for all $i \in \mathbb{N}^+$.

**Example 3.2.** For every $i \in \mathbb{N}^+$, let $D_{2i}$ be the dihedral group:

$$D_{2i} = \langle s, f \mid s^2 = f^i = e, sf = f^{-1}s \rangle.$$

In 2002, Rosenhouse [21] showed that $h(\text{Cay}(D_{2i}, \{f, f^{-1}, s\})) = \frac{4}{i}$. Hence, $h(\text{Cay}(D_{2i}, \{f, f^{-1}, s\})) \to 0$ as $i \to \infty$. Thus $\{\text{Cay}(D_{2i}, \{f, f^{-1}, s\}), i \in \mathbb{N}^+\}$ is not an expander family. In fact, it was shown later (see [14]) that for any set of generator $S_i$ of $D_{2i}$, $\{\text{Cay}(D_{2i}, S_i), i \in \mathbb{N}^+\}$ is not an expander family. Thus $\{D_{2i}, i \in \mathbb{N}^+\}$ is not a Cay-expander family.

It is well-known that no family of abelian groups is a Cay-expander [14]. Before we prove the same result for the G-expander case, we need the following lemma.

**Lemma 3.3.** Let G be an abelian group generated by $S = \{s_1, \dots, s_k\}$ and let $\tilde{\Phi}(G, S)$ be the corresponding G-graph, then

$$\mathrm{diam}(\tilde{\Phi}(G, S)) \le |S|.$$

*Proof.* Let $(s_p)x, (s_q)y \in V(\tilde{\Phi}(G, S))$, where $x, y \in G$ and $1 \le p, q \le |S| = k$. Since $G = \langle S \rangle$ is an abelian group, then

$$x = s_1^{i_1} \dots s_p^{i_p} \dots s_q^{i_q} \dots s_k^{i_k} y = s_1^{i_1} \dots s_p^{i_p} \dots s_{q-1}^{i_{q-1}} s_{q+1}^{i_{q+1}} \dots s_k^{i_k} s_q^{i_q} y,$$

where $1 \le i_l \le o(s_l)$ for all $1 \le l \le k$. It is easy to see that $(s_p)x$ is adjacent to $(s_1)s_2^{i_2} \dots s_k^{i_k} y$ which is in turn connected to $(s_2)s_3^{i_3} \dots s_k^{i_k} y$ and so on up to $(s_k)s_q^{i_q} y$ which is connected to $(s_q)y$. Thus $d((s_p)x, (s_q)y) \le |S|$. $\square$

**Corollary 3.4.** No family of abelian groups is a G-expander.

*Proof.* Suppose that $\{G_i, i \in \mathbb{N}^+\}$ is a family of finite abelian groups and that $\{\tilde{\Phi}(G_i, S_i), i \in \mathbb{N}^+\}$ is an expander family. Then there exists $r \in \mathbb{N}^+$ such that $|S_i| \le r$ for all $i \in \mathbb{N}^+$. But then by the preceding lemma $\mathrm{diam}(\tilde{\Phi}(G_i, S_i)) \le |S_i| \le r \in \mathbb{N}^+$, and that contradicts Proposition 2.12. $\square$

Now we are ready to prove the main result of this paper which is Theorem 1.1.

*Proof of Theorem 1.1.* Since $\text{Cay}(G_n, S_n^*)$ is an expander family, then $|G_n| \to \infty$ as $n \to \infty$ and there is an $r \in \mathbb{N}^+$ such that $|S_n^*| \le r$ for all $n \in \mathbb{N}^+$. Hence $|S_n| \le r$ and $\text{O}_{\text{max}}(S_n) \le r$ for every $n \in \mathbb{N}^+$. Then $|V(\tilde{\Phi}(G_n, S_n))| \to \infty$ as $n \to \infty$ and $\Delta(\tilde{\Phi}(G_n, S_n)) < r^2$ for all $n \in \mathbb{N}^+$.

Suppose that $H \subset V(\tilde{\Phi}(G_n, S_n))$ where $0 < |H| < \frac{|V(\tilde{\Phi}(G_n, S_n))|}{2}$, and $H_i = H \cap V_i$ for every $1 \le i \le |S_n|$. Then, clearly we have

$$H = \bigsqcup_i H_i.$$

Let $W = \bigcap_i \bigsqcup_{(s_i) \in H_i} \langle s \rangle x \subset G$. Since $|H| \le \frac{|V(\tilde{\Phi}(G_n, S_n))|}{2}$, we have $|W| \le \frac{|G|}{2}$. Now let $X_i = \{(s_i) \in H_i \mid \langle s_i \rangle x \subset W\}$, then $|X_i| \le |W|$. Denote by X and Y the following sets of vertices,

$$X = \bigsqcup_{i=1}^{|S_n|} X_i, \quad \text{and} \quad Y = H \setminus X.$$
If $(s)x \in Y$, there is an edge between $(s)x$ and a vertex in $V(\tilde{\Phi}(G_n, S_n)) \setminus H$. Hence

$$|\partial H| \ge |Y|.$$

In Cay$(G_n, S_n^*)$, we have $|\partial W| \ge \epsilon|W|$. Let $f: \partial W \to \partial H$, $\{x, y\} \mapsto (\{(s_i)x, (s_j)y\}, y)$, where $x \in W$, $y \notin W$, $i$ and $j$ are chosen so that $xy^{-1} \in \langle s_i \rangle$ and $y \notin \bigsqcup_{(s)x \in H_j} \langle s \rangle x$ (note here that there may be several possible choices for $i$ and $j$). Now observe that if $f(x, y) = f(x', y')$, then $xx'^{-1} \in \langle s_i \rangle$ and $y = y'$. So for all $\alpha \in \partial H$, $|f^{-1}(\alpha)| \le O_{\max}(S_n)$. Hence,

$$|\partial H| \ge \frac{|\partial W|}{O_{\max}(S_n)} \ge \frac{\epsilon|W|}{O_{\max}(S_n)} \ge \frac{\epsilon \max_i |X_i|}{O_{\max}(S_n)} \ge \frac{\epsilon|X|}{O_{\max}(S_n)|S_n|}.$$

Using $|\partial H| \ge |Y|$ and $|H| = |X| + |Y|$, we obtain

$$|\partial H| \ge \frac{1}{2} \min \left\{ \frac{\epsilon}{O_{\max}(S_n)|S_n|}, 1 \right\} |H| \ge \frac{1}{2} \min \left\{ \frac{\epsilon}{r^2}, 1 \right\} |H|.$$

This completes the proof.

<figure><img src="image_4.png" /></figure>

The following results are obvious consequences of Theorem 1.1.

**Corollary 3.5.** If $\{G_n, n \in \mathbb{N}^+\}$ is a Cay-expander family, then it is also a G-expander family.

**Corollary 3.6.** If $\{\text{Cay}(G_i, S_i^*)$, $i \in \mathbb{N}^+\}$ is an expander family, then $\{\tilde{\Phi}(G_i, S_i)\}$, $i \in \mathbb{N}^+\}$ is also an expander family.

*Proof.* By Theorem 1.1, $\{\tilde{\Phi}(G_i, S_i)\}$, $i \in \mathbb{N}^+$ is an expander family. By Definition 3.1, there exists $r \in \mathbb{N}^+$ such that $o(s_j) \le r$, for every $s_j \in S_i$. Then $|\langle s_{j_1} \rangle \cap \langle s_{j_2} \rangle| \le r$ for all $s_{j_1}, s_{j_2} \in S_i$. Thus $\frac{h(\tilde{\Phi}(G_i, S_i))}{r} \le h(\tilde{\Phi}(G_i, S_i))$. $\square$

<figure><img src="image_5.png" /></figure>

**Remark 3.7.**

1. Unlike most constructed expander families which are d-regular, our construction produces expander families that may be d-regular, regular, or irregular. More specifically, by Proposition 2.6, if the order of all elements in the generating set $S_i$ is the same, then the constructed family is either a d-regular or regular family depending on whether there exist $s_i \in S_i$ and $s_j \in S_j$ such that $o(s_i) \ne o(s_j)$. Otherwise, it will be an irregular family.

2. By Corollary 2.9, if $\langle s_{j_1} \rangle \cap \langle s_{j_2} \rangle = \{e\}$ for all $s_{j_1} \in S_i$, $s_{j_2} \in S_i \setminus s_{j_1}$, and for every $i \in \mathbb{N}^+$, then the constructed expander family $\{\tilde{\Phi}(G_i, S_i)\}$, $i \in \mathbb{N}^+$ is formed of simple graphs. Note that $\{\tilde{\Phi}(G_i, S_i)\}$, $i \in \mathbb{N}^+$ is always an expander family of simple graphs.

3. In Table 1, we compare some graph invariants for the Cayley graph Cay$(G, S^*)$ and the G-graph $\tilde{\Phi}(G, S)$.

It is worthy to note that $|S^*| = \sum_{s \in S} o(s) - |S|$ and every vertex in level $V_s$ of $\tilde{\Phi}(G, S)$ has degree equal to $o(s)(|S| - 1)$ where $|V_s| = \frac{|G|}{o(s)}$. Thus, the degree
If $(s)x \in Y$, there is an edge between $(s)x$ and a vertex in $V(\tilde{\Phi}(G_n, S_n)) \setminus H$. Hence

$$|\partial H| \ge |Y|.$$

In Cay$(G_n, S_n^*)$, we have $|\partial W| \ge \epsilon|W|$. Let $f: \partial W \to \partial H$, $\{x, y\} \mapsto (\{(s_i)x, (s_j)y\}, y)$, where $x \in W$, $y \notin W$, $i$ and $j$ are chosen so that $xy^{-1} \in \langle s_i \rangle$ and $y \notin \bigsqcup_{(s)x \in H_j} \langle s \rangle x$ (note here that there may be several possible choices for $i$ and $j$). Now observe that if $f(x, y) = f(x', y')$, then $xx'^{-1} \in \langle s_i \rangle$ and $y = y'$. So for all $\alpha \in \partial H$, $|f^{-1}(\alpha)| \le O_{\max}(S_n)$. Hence,

$$|\partial H| \ge \frac{|\partial W|}{O_{\max}(S_n)} \ge \frac{\epsilon|W|}{O_{\max}(S_n)} \ge \frac{\epsilon \max_i |X_i|}{O_{\max}(S_n)} \ge \frac{\epsilon|X|}{O_{\max}(S_n)|S_n|}.$$

Using $|\partial H| \ge |Y|$ and $|H| = |X| + |Y|$, we obtain

$$|\partial H| \ge \frac{1}{2} \min \left\{ \frac{\epsilon}{O_{\max}(S_n)|S_n|}, 1 \right\} |H| \ge \frac{1}{2} \min \left\{ \frac{\epsilon}{r^2}, 1 \right\} |H|.$$

This completes the proof.

<figure><img src="image_4.png" /></figure>

The following results are obvious consequences of Theorem 1.1.

**Corollary 3.5.** If $\{G_n, n \in \mathbb{N}^+\}$ is a Cay-expander family, then it is also a G-expander family.

**Corollary 3.6.** If $\{\text{Cay}(G_i, S_i^*)\}$, $i \in \mathbb{N}^+$ is an expander family, then $\{\tilde{\Phi}(G_i, S_i)\}$, $i \in \mathbb{N}^+$ is also an expander family.

*Proof.* By Theorem 1.1, $\{\tilde{\Phi}(G_i, S_i)\}$, $i \in \mathbb{N}^+$ is an expander family. By Definition 3.1, there exists $r \in \mathbb{N}^+$ such that $o(s_j) \le r$, for every $s_j \in S_i$. Then $|\langle s_{j_1} \rangle \cap \langle s_{j_2} \rangle| \le r$ for all $s_{j_1}, s_{j_2} \in S_i$. Thus $\frac{h(\tilde{\Phi}(G_i, S_i))}{r} \le h(\tilde{\Phi}(G_i, S_i))$. $\square$

<figure><img src="image_5.png" /></figure>

**Remark 3.7.**

1. Unlike most constructed expander families which are d-regular, our construction produces expander families that may be d-regular, regular, or irregular. More specifically, by Proposition 2.6, if the order of all elements in the generating set $S_i$ is the same, then the constructed family is either a d-regular or regular family depending on whether there exist $s_i \in S_i$ and $s_j \in S_j$ such that $o(s_i) \ne o(s_j)$. Otherwise, it will be an irregular family.

2. By Corollary 2.9, if $\langle s_{j_1} \rangle \cap \langle s_{j_2} \rangle = \{e\}$ for all $s_{j_1} \in S_i$, $s_{j_2} \in S_i \setminus s_{j_1}$, and for every $i \in \mathbb{N}^+$, then the constructed expander family $\{\tilde{\Phi}(G_i, S_i)\}$, $i \in \mathbb{N}^+$ is formed of simple graphs. Note that $\{\tilde{\Phi}(G_i, S_i)\}$, $i \in \mathbb{N}^+$ is always an expander family of simple graphs.

3. In Table 1, we compare some graph invariants for the Cayley graph Cay$(G, S^*)$ and the G-graph $\tilde{\Phi}(G, S)$.

It is worthy to note that $|S^*| = \sum_{s \in S} o(s) - |S|$ and every vertex in level $V_s$ of $\tilde{\Phi}(G, S)$ has degree equal to $o(s)(|S| - 1)$ where $|V_s| = \frac{|G|}{o(s)}$. Thus, the degree
<table><caption>Table 1: Some graph invariants of Cay(G, S*) and $\tilde{\Phi}(G, S)$.</caption><thead><tr><th></th><th>Cay(G, S*)</th><th>Φ̃(G, S)</th></tr></thead><tbody><tr><th>Order</th><td>|G|</td><td>∑<sub>s∈S</sub> |G|/o(s)</td></tr><tr><th>Degree</th><td>|S*|-regular multigraph</td><td>d(u) = o(s)(|S| - 1)<br>for all u ∈ V<sub>s</sub> and s ∈ S</td></tr><tr><th>Size</th><td><sup>1</sup>⁄<sub>2</sub>|G||S*| = <sup>1</sup>⁄<sub>2</sub>|G|(|∑<sub>s∈S</sub> o(s)| - |S|)</td><td><sup>1</sup>⁄<sub>2</sub>|G||S|(|S| - 1)</td></tr></tbody></table>

of most vertices of $\tilde{\Phi}(G, S)$ is smaller than $|S^*|$ (see also the remark after Theorem 5.10). In other words, this means that $G$-graphs enable us to construct sparser multigraphs than those which can be constructed using the family Cay(G, S*), and in some cases even sparser than the ones constructed from the family Cay(G, S), with possibly smaller expansion ratios (see the proof of Theorem 1.1).

# 4 Applications

In this section, we present some direct results of Theorem 1.1. But first we start with some auxiliary materials.

**Proposition 4.1.** Let $x_i \in G_i \setminus S_i$. If $\{\mathrm{Cay}(G_i, S_i), i \in \mathbb{N}^+\}$ is an expander family, then $\{\mathrm{Cay}(G_i, S_i \cup x_i^{\pm 1}), i \in \mathbb{N}^+\}$ is also an expander family.

*Proof.* Since $\{\mathrm{Cay}(G_i, S_i), i \in \mathbb{N}^+\}$ is an expander family, then there exists $r \in \mathbb{N}^+$ such that $|S_i| \le r$, for all $i \in \mathbb{N}^+$. Thus $|S_i \cup x_i^{\pm 1}| \le r + 2$ for all $i \in \mathbb{N}^+$, so the second condition of Definition 2.11 is satisfied. Note that $\mathrm{Cay}(G_i, S_i)$ is a spanning subgraph of $\mathrm{Cay}(G_i, S_i \cup x_i^{\pm 1})$, hence

$$0 < \epsilon \le h(\mathrm{Cay}(G_i, S_i)) \le h(\mathrm{Cay}(G_i, S_i \cup x_i^{\pm 1})). \quad \square$$

A direct consequence of the preceding proposition is the following.

**Corollary 4.2.** Let $\{\mathrm{Cay}(G_i, S_i), i \in \mathbb{N}^+\}$ be an expander family. If there exists $l \in \mathbb{N}^+$ such that $|S_i^*| \le l$ for all $i \in \mathbb{N}^+$, then $\{\mathrm{Cay}(G_i, S_i^*), i \in \mathbb{N}^+\}$ is also an expander family.

The following theorem was proved by Breuillard and Gamburd in [8].

**Theorem 4.3 ([8]).** There exists $\epsilon \in \mathbb{R}_+^*$ and an infinite set of prime numbers $\mathbb{P}'$ such that for every $p \in \mathbb{P}'$ and every generating set $\{x, y\}$ of $\mathrm{SL}(2, \mathbb{Z}/p\mathbb{Z})$, the family

$$\mathrm{Cay}(\mathrm{SL}(2, \mathbb{Z}/p\mathbb{Z}), \{x^{\pm 1}, y^{\pm 1}\})$$

is an $\epsilon$-expander.

Let

$$S_1 = \begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix}, \quad S_2 = \begin{pmatrix} 0 & 1 \\ -1 & 0 \end{pmatrix} \quad \text{and} \quad S_3 = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}.$$
<table><caption>Table 1: Some graph invariants of Cay(G, S*) and $\tilde{\Phi}(G, S)$.</caption><thead><tr><th></th><th>Cay(G, S*)</th><th>Φ̃(G, S)</th></tr></thead><tbody><tr><th>Order</th><td>|G|</td><td>∑<sub>s∈S</sub> |G|/o(s)</td></tr><tr><th>Degree</th><td>|S*|-regular multigraph</td><td>d(u) = o(s)(|S| - 1)<br>for all u ∈ V<sub>s</sub> and s ∈ S</td></tr><tr><th>Size</th><td><sup>1</sup>⁄<sub>2</sub>|G||S*| = <sup>1</sup>⁄<sub>2</sub>|G|(|∑<sub>s∈S</sub> o(s)| - |S|)</td><td><sup>1</sup>⁄<sub>2</sub>|G||S|(|S| - 1)</td></tr></tbody></table>

of most vertices of $\tilde{\Phi}(G, S)$ is smaller than $|S^*|$ (see also the remark after Theorem 5.10). In other words, this means that $G$-graphs enable us to construct sparser multigraphs than those which can be constructed using the family Cay(G, S*), and in some cases even sparser than the ones constructed from the family Cay(G, S), with possibly smaller expansion ratios (see the proof of Theorem 1.1).

# 4 Applications

In this section, we present some direct results of Theorem 1.1. But first we start with some auxiliary materials.

**Proposition 4.1.** Let $x_i \in G_i \setminus S_i$. If $\{\mathrm{Cay}(G_i, S_i), i \in \mathbb{N}^+\}$ is an expander family, then $\{\mathrm{Cay}(G_i, S_i \cup x_i^{\pm 1}), i \in \mathbb{N}^+\}$ is also an expander family.

*Proof.* Since $\{\mathrm{Cay}(G_i, S_i), i \in \mathbb{N}^+\}$ is an expander family, then there exists $r \in \mathbb{N}^+$ such that $|S_i| \le r$, for all $i \in \mathbb{N}^+$. Thus $|S_i \cup x_i^{\pm 1}| \le r + 2$ for all $i \in \mathbb{N}^+$, so the second condition of Definition 2.11 is satisfied. Note that $\mathrm{Cay}(G_i, S_i)$ is a spanning subgraph of $\mathrm{Cay}(G_i, S_i \cup x_i^{\pm 1})$, hence

$$0 < \epsilon \le h(\mathrm{Cay}(G_i, S_i)) \le h(\mathrm{Cay}(G_i, S_i \cup x_i^{\pm 1})). \quad \square$$

A direct consequence of the preceding proposition is the following.

**Corollary 4.2.** Let $\{\mathrm{Cay}(G_i, S_i), i \in \mathbb{N}^+\}$ be an expander family. If there exists $l \in \mathbb{N}^+$ such that $|S_i^*| \le l$ for all $i \in \mathbb{N}^+$, then $\{\mathrm{Cay}(G_i, S_i^*), i \in \mathbb{N}^+\}$ is also an expander family.

The following theorem was proved by Breuillard and Gamburd in [8].

**Theorem 4.3 ([8]).** There exists $\epsilon \in \mathbb{R}_+^*$ and an infinite set of prime numbers $\mathbb{P}'$ such that for every $p \in \mathbb{P}'$ and every generating set $\{x, y\}$ of $\mathrm{SL}(2, \mathbb{Z}/p\mathbb{Z})$, the family

$$\mathrm{Cay}(\mathrm{SL}(2, \mathbb{Z}/p\mathbb{Z}), \{x^{\pm 1}, y^{\pm 1}\})$$

is an $\epsilon$-扩散.

Let

$$S_1 = \begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix}, \quad S_2 = \begin{pmatrix} 0 & 1 \\ -1 & 0 \end{pmatrix} \quad \text{and} \quad S_3 = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}.$$
It is well-known that $SL(2, \mathbb{Z}/p\mathbb{Z}) = \langle S_1, S_3 \rangle = \langle S_2, S_3 \rangle$. The order of $S_1, S_2$ is 4, while the order of $S_3$ in $\mathbb{Z}/p\mathbb{Z}$ is $p$. Thus $SL(2, \mathbb{Z}/p\mathbb{Z})$ is also generated by one of the following sets: $\{S_1, S_1S_3\}, \{S_1, S_3S_1\}, \{S_2, S_2S_3\}, \{S_2, S_3S_2\}$. Where

$$ 
\begin{aligned}
S_1S_3 &= \begin{pmatrix} 0 & -1 \\ 1 & 1 \end{pmatrix}, & S_3S_1 &= \begin{pmatrix} 1 & -1 \\ 1 & 0 \end{pmatrix}, \\
S_2S_3 &= \begin{pmatrix} 0 & 1 \\ -1 & -1 \end{pmatrix}, \text{ and} & S_3S_2 &= \begin{pmatrix} -1 & 1 \\ -1 & 0 \end{pmatrix}.
\end{aligned}
$$

Note that the orders of $S_1S_3, S_3S_1, S_2S_3$, and $S_3S_2$ are respectively 6, 6, 3 and 3. With the above notation, we have the following conclusion.

**Corollary 4.4.** Let

$$ 
\begin{aligned}
A_1 &= \{S_1^{\pm 1}, S_1S_3, S_3^{-1}S_1^{-1}\}, & A_2 &= \{S_1^{\pm 1}, S_3S_1, S_1^{-1}S_3^{-1}\}, \\
A_3 &= \{S_2^{\pm 1}, S_2S_3, S_3^{-1}S_2^{-1}\}, & A_4 &= \{S_2^{\pm 1}, S_3S_2, S_2^{-1}S_3^{-1}\}.
\end{aligned}
$$

There exist sets $\mathbb{P}_i^a$ of prime numbers such that $\{\text{Cay}(\text{SL}(2, \mathbb{Z}/p\mathbb{Z}), A_i); p \in \mathbb{P}_i^a\}$ is an expander family for all $1 \le i \le 4$.

Let $B_1 = \{S_1, S_1S_3\}$, by Corollaries 4.2 and 4.4 we directly deduce that there exists a set $\mathbb{P}'$ of prime numbers such that $\{\text{Cay}(\text{SL}(2, \mathbb{Z}/p\mathbb{Z}), B_1^*); p \in \mathbb{P}'\}$ is an expander family. Using Theorem 1.1, we can easily deduce that $\{\tilde{\Phi}(\text{SL}(2, \mathbb{Z}/p\mathbb{Z}), B_1); p \in \mathbb{P}'\}$ is an expander family. By the same analogy, we obtain the following.

**Corollary 4.5.** Let

$$ 
\begin{aligned}
B_1 &= \{S_1, S_1S_3\}, & B_2 &= \{S_1, S_3S_1\}, \\
B_3 &= \{S_2, S_2S_3\}, \text{ and} & B_4 &= \{S_2, S_3S_2\}.
\end{aligned}
$$

There exist sets $\mathbb{P}_i^b$ of prime numbers such that $\{\tilde{\Phi}(\text{SL}(2, \mathbb{Z}/p\mathbb{Z}), B_i); p \in \mathbb{P}_i^b\}$ is an expander family for all $1 \le i \le 4$.

In a similar fashion, many other G-graph families on the special linear group $SL(2, \mathbb{Z}/q\mathbb{Z})$ can be constructed.

# 5 New expander families of G-graphs

In this section, we present a method for constructing a family of Cayley graphs from another given family by rearrangement of edges in such a way to almost maintain the same expansion ratio. Consequently, we prove that if the family of Cayley graphs $\{\text{Cay}(G_i, \{s_1^{\pm 1}, s_2^{\pm 1}\}); i \in \mathbb{N}^+\}$ is an expander, then so is the family of Cayley graphs $\{\text{Cay}(G_i, \{s_1^{\pm 1}, s_1s_2, s_2^{-1}s_1^{-1}\}); i \in \mathbb{N}^+\}$. Then using Theorem 1.1, several expander families of G-graphs are constructed. But first we need to introduce more notation.

**Remark 5.1.** Let $\text{Cay}(G, S)$ be a Cayley graph and let $H' \subseteq H \subseteq G$. Let $s \in S$, we denote by $N_s(H)$ and $N_s(H)(H')$ the set of vertices of $\text{Cay}(G, S)$ that are defined in the following way:

i. $N_s(H) = sH \cap \bar{H}$,
It is well-known that $SL(2, \mathbb{Z}/p\mathbb{Z}) = \langle S_1, S_3 \rangle = \langle S_2, S_3 \rangle$. The order of $S_1, S_2$ is 4, while the order of $S_3$ in $\mathbb{Z}/p\mathbb{Z}$ is $p$. Thus $SL(2, \mathbb{Z}/p\mathbb{Z})$ is also generated by one of the following sets: $\{S_1, S_1S_3\}, \{S_1, S_3S_1\}, \{S_2, S_2S_3\}, \{S_2, S_3S_2\}$. Where

$$ 
\begin{aligned}
S_1S_3 &= \begin{pmatrix} 0 & -1 \\ 1 & 1 \end{pmatrix}, & S_3S_1 &= \begin{pmatrix} 1 & -1 \\ 1 & 0 \end{pmatrix}, \\
S_2S_3 &= \begin{pmatrix} 0 & 1 \\ -1 & -1 \end{pmatrix}, \text{ and} & S_3S_2 &= \begin{pmatrix} -1 & 1 \\ -1 & 0 \end{pmatrix}.
\end{aligned}
$$

Note that the orders of $S_1S_3, S_3S_1, S_2S_3$, and $S_3S_2$ are respectively 6, 6, 3 and 3. With the above notation, we have the following conclusion.

**Corollary 4.4.** Let

$$ 
\begin{aligned}
A_1 &= \{S_1^{\pm 1}, S_1S_3, S_3^{-1}S_1^{-1}\}, & A_2 &= \{S_1^{\pm 1}, S_3S_1, S_1^{-1}S_3^{-1}\}, \\
A_3 &= \{S_2^{\pm 1}, S_2S_3, S_3^{-1}S_2^{-1}\}, \text{ and} & A_4 &= \{S_2^{\pm 1}, S_3S_2, S_2^{-1}S_3^{-1}\}.
\end{aligned}
$$

There exist sets $\mathbb{P}_i^a$ of prime numbers such that $\{\text{Cay}(\text{SL}(2, \mathbb{Z}/p\mathbb{Z}), A_i); p \in \mathbb{P}_i^a\}$ is an expander family for all $1 \le i \le 4$.

Let $B_1 = \{S_1, S_1S_3\}$, by Corollaries 4.2 and 4.4 we directly deduce that there exists a set $\mathbb{P}'$ of prime numbers such that $\{\text{Cay}(\text{SL}(2, \mathbb{Z}/p\mathbb{Z}), B_1^*); p \in \mathbb{P}'\}$ is an expander family. Using Theorem 1.1, we can easily deduce that $\{\tilde{\Phi}(\text{SL}(2, \mathbb{Z}/p\mathbb{Z}), B_1); p \in \mathbb{P}'\}$ is an expander family. By the same analogy, we obtain the following.

**Corollary 4.5.** Let

$$ 
\begin{aligned}
B_1 &= \{S_1, S_1S_3\}, & B_2 &= \{S_1, S_3S_1\}, \\
B_3 &= \{S_2, S_2S_3\}, \text{ and} & B_4 &= \{S_2, S_3S_2\}.
\end{aligned}
$$

There exist sets $\mathbb{P}_i^b$ of prime numbers such that $\{\tilde{\Phi}(\text{SL}(2, \mathbb{Z}/p\mathbb{Z}), B_i); p \in \mathbb{P}_i^b\}$ is an expander family for all $1 \le i \le 4$.

In a similar fashion, many other G-graph families on the special linear group $SL(2, \mathbb{Z}/q\mathbb{Z})$ can be constructed.

# 5 New expander families of G-graphs

In this section, we present a method for constructing a family of Cayley graphs from another given family by rearrangement of edges in such a way to almost maintain the same expansion ratio. Consequently, we prove that if the family of Cayley graphs $\{\text{Cay}(G_i, \{s_1^{\pm 1}, s_2^{\pm 1}\}); i \in \mathbb{N}^+\}$ is an expander, then so is the family of Cayley graphs $\{\text{Cay}(G_i, \{s_1^{\pm 1}, s_1s_2, s_2^{-1}s_1^{-1}\}); i \in \mathbb{N}^+\}$. Then using Theorem 1.1, several expander families of G-graphs are constructed. But first we need to introduce more notation.

**Remark 5.1.** Let $\text{Cay}(G, S)$ be a Cayley graph and let $H' \subseteq H \subseteq G$. Let $s \in S$, we denote by $N_s(H)$ and $N_s(H)(H')$ the set of vertices of $\text{Cay}(G, S)$ that are defined in the following way:

i. $N_s(H) = sH \cap \bar{H}$,
ii. $N_s(H)(H') = sH' \cap \bar{H}$.

Next, we start by the following simple lemma.

**Lemma 5.2.** Let Cay$(G, S)$ be a Cayley graph, where $S = \{s_1^{\pm 1}, \dots, s_k^{\pm 1}\}$. Let $H \subseteq G$, then

$$|\partial H(\mathrm{Cay}(G, S))| = 2 \sum_{i|o(s_i)>2} |N_{s_i}(H)| + \sum_{i|o(s_i)=2} |N_{s_i}(H)| = \sum_{1 \le i \le k} |N_{s_i^{\pm 1}}(H)|.$$

*Proof.* Let $x, y \in H$ such that $y = s_ix$ for some $s_i \in S$, then $x = s_i^{-1}y$. Thus the number of edges in the subgraph $H$ of $G$ that corresponds to $s_i$ is equal to that of $s_i^{-1}$ and $|N_{s_i}| = |N_{s_i^{-1}}|$. It is easy to see that: $|\partial H(\mathrm{Cay}(G, S))| = \sum_{1 \le i \le k} |N_{s_i^{\pm 1}}(H)|$ and the proof is complete. $\square$

**Example 5.3.** Let $(\mathbb{Z}/n\mathbb{Z}, +, 0)$, $n \ge 10$ and $S = \{\pm 1, \pm 2\}$. Then Cay$(\mathbb{Z}/n\mathbb{Z}, S)$ is 4-regular multigraph on $n$ vertices. Let $H$ be a subgraph of Cay$(\mathbb{Z}/n\mathbb{Z}, S)$ such that $V(H) = \{1, 2, 3, 7\}$. Let $s_1 = +1$ and $s_2 = +2$. Then $N_{s_1}(H) = \{4, 8\}$, $N_{s_1^{-1}}(H) = \{0, 6\}$, $N_{s_2}(H) = \{4, 5, 9\}$, and $N_{s_2^{-1}}(H) = \{0, 5, n-1\}$. Thus

$$|\partial H(\mathrm{Cay}(\mathbb{Z}/n\mathbb{Z}, S))| = 2(|N_{s_1}(H)| + |N_{s_2}(H)|) = 10.$$

Next, we shall show that it is possible to construct an expander family of Cayley graphs from another one by switching some of its edges.

**Corollary 5.4.** Let $\{\mathrm{Cay}(G_i, \{s_1^{\pm 1}, s_2^{\pm 1}\})$; $i \in \mathbb{N}^+$} be an expander family. If $o(s_1)$, $o(s_2)$, and $o(s_1s_2) > 2$, then $\{\mathrm{Cay}(G_i, \{s_1^{\pm 1}, s_1s_2, s_2^{-1}s_1^{-1}\})$; $i \in \mathbb{N}^+$} is also an expander family.

*Proof.* Let $V(H) = \{x_1, \dots, x_t\} \in G$. Define $\partial'H$, $\partial''H$ to be the sets of emanating edges from $V(H)$ in the multigraphs $\mathrm{Cay}(G_i, \{s_1^{\pm 1}, s_2^{\pm 1}\})$ and $\mathrm{Cay}(G_i, \{s_1^{\pm 1}, s_1s_2, s_2^{-1}s_1^{-1}\})$ respectively. By Lemma 5.2, we have:

$$|\partial'H| = 2|N_{s_1}(H)| + 2|N_{s_2}(H)|, \quad \text{and} \quad (1)$$

$$|\partial''H| = 2|N_{s_1}(H)| + 2|N_{s_1s_2}(H)|. \quad (2)$$

Let $y \in N_{s_2}(H)$, $y = s_2x$ for some $x \in H$.

i. If $s_1y \notin H$, then $s_1s_2x \notin H$ and $s_1s_2x \in N_{s_1s_2}(H)$.

ii. And if $s_1y \in H$, then $s_1s_2x \in H$.

Let $H_1$ and $H_2$ be the set of vertices of $H$ defined as follows:

$$H_1 = \{x \in H/s_2x \notin H \text{ and } s_1s_2x \notin H\},$$

$$H_2 = \{x \in H/s_2x \notin H \text{ and } s_1s_2x \in H\}.$$

From equalities (1) and (2), we have

$$2|N_{s_1}(H)| + 2|N_{s_2}(H)(H_1)| + 2|N_{s_2}(H)(H_2)| = |\partial'H|, \\ 2|N_{s_1}(H)| + 2|N_{s_1s_2}(H)(H_1)| + 2|N_{s_1s_2}(H)(H_2)| \le |\partial''H|.$$
ii. $N_s(H)(H') = sH' \cap \bar{H}$.

Next, we start by the following simple lemma.

**Lemma 5.2.** Let Cay$(G, S)$ be a Cayley graph, where $S = \{s_1^{\pm 1}, \dots, s_k^{\pm 1}\}$. Let $H \subseteq G$, then

$$|\partial H(\mathrm{Cay}(G, S))| = 2 \sum_{i|o(s_i)>2} |N_{s_i}(H)| + \sum_{i|o(s_i)=2} |N_{s_i}(H)| = \sum_{1 \le i \le k} |N_{s_i^{\pm 1}}(H)|.$$

*Proof.* Let $x, y \in H$ such that $y = s_i x$ for some $s_i \in S$, then $x = s_i^{-1} y$. Thus the number of edges in the subgraph $H$ of $G$ that corresponds to $s_i$ is equal to that of $s_i^{-1}$ and $|N_{s_i}| = |N_{s_i^{-1}}|$. It is easy to see that: $|\partial H(\mathrm{Cay}(G, S))| = \sum_{1 \le i \le k} |N_{s_i^{\pm 1}}(H)|$ and the proof is complete. $\square$

**Example 5.3.** Let $(\mathbb{Z}/n\mathbb{Z}, +, 0)$, $n \ge 10$ and $S = \{\pm 1, \pm 2\}$. Then Cay$(\mathbb{Z}/n\mathbb{Z}, S)$ is 4-regular multigraph on $n$ vertices. Let $H$ be a subgraph of Cay$(\mathbb{Z}/n\mathbb{Z}, S)$ such that $V(H) = \{1, 2, 3, 7\}$. Let $s_1 = +1$ and $s_2 = +2$. Then $N_{s_1}(H) = \{4, 8\}$, $N_{s_1^{-1}}(H) = \{0, 6\}$, $N_{s_2}(H) = \{4, 5, 9\}$, and $N_{s_2^{-1}}(H) = \{0, 5, n-1\}$. Thus

$$|\partial H(\mathrm{Cay}(\mathbb{Z}/n\mathbb{Z}, S))| = 2(|N_{s_1}(H)| + |N_{s_2}(H)|) = 10.$$

Next, we shall show that it is possible to construct an expander family of Cayley graphs from another one by switching some of its edges.

**Corollary 5.4.** Let $\{\mathrm{Cay}(G_i, \{s_1^{\pm 1}, s_2^{\pm 1}\})$; $i \in \mathbb{N}^+$} be an expander family. If $o(s_1)$, $o(s_2)$, and $o(s_1s_2) > 2$, then $\{\mathrm{Cay}(G_i, \{s_1^{\pm 1}, s_1s_2, s_2^{-1}s_1^{-1}\})$; $i \in \mathbb{N}^+$} is also an expander family.

*Proof.* Let $V(H) = \{x_1, \dots, x_t\} \in G$. Define $\partial'H$, $\partial''H$ to be the sets of emanating edges from $V(H)$ in the multigraphs $\mathrm{Cay}(G_i, \{s_1^{\pm 1}, s_2^{\pm 1}\})$ and $\mathrm{Cay}(G_i, \{s_1^{\pm 1}, s_1s_2, s_2^{-1}s_1^{-1}\})$ respectively. By Lemma 5.2, we have:

$$|\partial'H| = 2|N_{s_1}(H)| + 2|N_{s_2}(H)|, \quad \text{and} \quad (1)$$

$$|\partial''H| = 2|N_{s_1}(H)| + 2|N_{s_1s_2}(H)|. \quad (2)$$

Let $y \in N_{s_2}(H)$, $y = s_2x$ for some $x \in H$.

i. If $s_1y \notin H$, then $s_1s_2x \notin H$ and $s_1s_2x \in N_{s_1s_2}(H)$.

ii. And if $s_1y \in H$, then $s_1s_2x \in H$.

Let $H_1$ and $H_2$ be the set of vertices of $H$ defined as follows:

$$H_1 = \{x \in H/s_2x \notin H \text{ and } s_1s_2x \notin H\},$$

$$H_2 = \{x \in H/s_2x \notin H \text{ and } s_1s_2x \in H\}.$$

From equalities (1) and (2), we have

$$2|N_{s_1}(H)| + 2|N_{s_2}(H)(H_1)| + 2|N_{s_2}(H)(H_2)| = |\partial'H|, \\ 2|N_{s_1}(H)| + 2|N_{s_1s_2}(H)(H_1)| + 2|N_{s_1s_2}(H)(H_2)| \le |\partial''H|.$$
From the definition of $H_2$, we have $|N_{s_1s_2}(H)(H_2)| = 0$, then

$$2|N_{s_1}(H)| + 2|N_{s_1s_2}(H)(H_1)| \leq |\partial''H|.$$

Therefore, it holds that

$$2|N_{s_1}(H)| + 4|N_{s_1s_2}(H)(H_1)| - 2|N_{s_2}(H)(H_1)| - 2|N_{s_2}(H)(H_2)| \leq 2|\partial''H| - |\partial'H|.$$

From the definition of $H_1$, we have $|N_{s_1s_2}(H)(H_1)| = |N_{s_2}(H)(H_1)|$ and similarly from the definition of $H_2$, we have $|N_{s_2}(H)(H_2)| = |N_{s_1^{-1}}(H) \cap N_{s_2}(H)|$. Thus,

$$2|N_{s_1}(H)| + 2|N_{s_2}(H)(H_1)| - 2|N_{s_1^{-1}}(H) \cap N_{s_2}(H)| \leq 2|\partial''H| - |\partial'H|.$$

Noticing that

$$|N_{s_1^{-1}}(H) \cap N_{s_2}(H)| \leq |N_{s_1^{-1}}(H)| = |N_{s_1}(H)|,$$

then

$$2|N_{s_2}(H)(H_1)| \leq 2|\partial''H| - |\partial'H|.$$

Finally, we obtain

$$0 < \epsilon \leq \frac{|\partial'H|}{2|H|} \leq \frac{|\partial''H|}{|H|}. \quad \square$$

**Remark 5.5.** Note that in general $\{\mathrm{Cay}(G_i, \{s_1^{\pm 1}, s_2^{\pm 1}\}); i \in \mathbb{N}^+\}$ and $\{\mathrm{Cay}(G_i, \{s_1^{\pm 1}, s_1s_2, s_2^{-1}s_1^{-1}\}); i \in \mathbb{N}^+\}$ may be not isomorphic. An example of this situation is given by the dihedral group $D_{2i}$ which is defined earlier as follows:

$$D_{2i} = \langle s, f \mid s^2 = f^i = e, sf = f^{-1}s \rangle.$$

Let $s_1 = s$ and $s_2 = f$, then $S = \{s_1^{\pm 1}, s_2^{\pm 1}\} = \{s, f^{\pm 1}\}$ and $L = \{s_1^{\pm 1}, s_1s_2, s_2^{-1}s_1^{-1}\} = \{s, sf\}$. Clearly, the 3-regular $\mathrm{Cay}(D_{2i}, \{s_1^{\pm 1}, s_2^{\pm 1}\})$ is not isomorphic to the 2-regular multigraph $\mathrm{Cay}(D_{2i}, \{s_1^{\pm 1}, s_1s_2, s_2^{-1}s_1^{-1}\})$.

The next theorem is Theorem 4.4.2 in [16].

**Theorem 5.6 ([16]).** Let $\mathbb{P}$ be the set of all prime numbers, then $\{\mathrm{Cay}(\mathrm{PSL}(2, \mathbb{Z}/p\mathbb{Z}), \{S_2^{\pm 1}, S_3^{\pm 1}\}); p \in \mathbb{P}\}$ is an expander family.

As a consequence, we have the following.

**Corollary 5.7.** Let $\mathbb{P}$ be the set of all prime numbers, then $\{\mathrm{Cay}(\mathrm{PSL}(2, \mathbb{Z}/p\mathbb{Z}); \{S_2^{\pm 1}, S_2S_3, S_3^{-1}S_2^{-1}\}); p \in \mathbb{P}\}$ is an expander family.

**Corollary 5.8.** Let $\mathbb{P}$ be the set of all prime numbers, then $\{\mathrm{PSL}(2, \mathbb{Z}/p\mathbb{Z}); p \in \mathbb{P}\}$ is a Cay-expander family.

**Remark 5.9.** The order of $S_2$ and $S_2S_3$ are 4 and 3 respectively. Let $L = \{S_2, S_2S_3\}$ and $W = \{S_2, S_2^2, S_2S_3\}$, then we see that $\max\{|L^*|, |W^*|\} \leq 7$. Using Corollaries 4.2 and 5.7, we deduce that $\{\mathrm{Cay}(\mathrm{PSL}(2, \mathbb{Z}/p\mathbb{Z}), L^*\}$; $p \in \mathbb{P}\}$ and $\{\mathrm{Cay}(\mathrm{PSL}(2, \mathbb{Z}/p\mathbb{Z}), W^*\}$; $p \in \mathbb{P}\}$ are all expander families. Now by Theorem 1.1, we are able to directly construct several expander families of G-graphs.

Thus, we can conclude the following.
From the definition of $H_2$, we have $|N_{s_1s_2}(H)(H_2)| = 0$, then

$$2|N_{s_1}(H)| + 2|N_{s_1s_2}(H)(H_1)| \leq |\partial''H|.$$

Therefore, it holds that

$$2|N_{s_1}(H)| + 4|N_{s_1s_2}(H)(H_1)| - 2|N_{s_2}(H)(H_1)| - 2|N_{s_2}(H)(H_2)| \leq 2|\partial''H| - |\partial'H|.$$

From the definition of $H_1$, we have $|N_{s_1s_2}(H)(H_1)| = |N_{s_2}(H)(H_1)|$ and similarly from the definition of $H_2$, we have $|N_{s_2}(H)(H_2)| = |N_{s_1^{-1}}(H) \cap N_{s_2}(H)|$. Thus,

$$2|N_{s_1}(H)| + 2|N_{s_2}(H)(H_1)| - 2|N_{s_1^{-1}}(H) \cap N_{s_2}(H)| \leq 2|\partial''H| - |\partial'H|.$$

Noticing that

$$|N_{s_1^{-1}}(H) \cap N_{s_2}(H)| \leq |N_{s_1^{-1}}(H)| = |N_{s_1}(H)|,$$

then

$$2|N_{s_2}(H)(H_1)| \leq 2|\partial''H| - |\partial'H|.$$

Finally, we obtain

$$0 < \epsilon \leq \frac{|\partial'H|}{2|H|} \leq \frac{|\partial''H|}{|H|}. \quad \square$$

**Remark 5.5.** Note that in general $\{\mathrm{Cay}(G_i, \{s_1^{\pm 1}, s_2^{\pm 1}\}); i \in \mathbb{N}^+\}$ and $\{\mathrm{Cay}(G_i, \{s_1^{\pm 1}, s_1s_2, s_2^{-1}s_1^{-1}\}); i \in \mathbb{N}^+\}$ may be not isomorphic. An example of this situation is given by the dihedral group $D_{2i}$ which is defined earlier as follows:

$$D_{2i} = \langle s, f \mid s^2 = f^i = e, sf = f^{-1}s \rangle.$$

Let $s_1 = s$ and $s_2 = f$, then $S = \{s_1^{\pm 1}, s_2^{\pm 1}\} = \{s, f^{\pm 1}\}$ and $L = \{s_1^{\pm 1}, s_1s_2, s_2^{-1}s_1^{-1}\} = \{s, sf\}$. Clearly, the 3-regular $\mathrm{Cay}(D_{2i}, \{s_1^{\pm 1}, s_2^{\pm 1}\})$ is not isomorphic to the 2-regular multigraph $\mathrm{Cay}(D_{2i}, \{s_1^{\pm 1}, s_1s_2, s_2^{-1}s_1^{-1}\})$.

The next theorem is Theorem 4.4.2 in [16].

**Theorem 5.6 ([16]).** Let $\mathbb{P}$ be the set of all prime numbers, then $\{\mathrm{Cay}(\mathrm{PSL}(2, \mathbb{Z}/p\mathbb{Z}), \{S_2^{\pm 1}, S_3^{\pm 1}\}); p \in \mathbb{P}\}$ is an expander family.

As a consequence, we have the following.

**Corollary 5.7.** Let $\mathbb{P}$ be the set of all prime numbers, then $\{\mathrm{Cay}(\mathrm{PSL}(2, \mathbb{Z}/p\mathbb{Z}); \{S_2^{\pm 1}, S_2S_3, S_3^{-1}S_2^{-1}\}); p \in \mathbb{P}\}$ is an expander family.

**Corollary 5.8.** Let $\mathbb{P}$ be the set of all prime numbers, then $\{\mathrm{PSL}(2, \mathbb{Z}/p\mathbb{Z}); p \in \mathbb{P}\}$ is a Cay-expander family.

**Remark 5.9.** The order of $S_2$ and $S_2S_3$ are 4 and 3 respectively. Let $L = \{S_2, S_2S_3\}$ and $W = \{S_2, S_2^2, S_2S_3\}$, then we see that $\max\{|L^*|, |W^*|\} \leq 7$. Using Corollaries 4.2 and 5.7, we deduce that $\{\mathrm{Cay}(\mathrm{PSL}(2, \mathbb{Z}/p\mathbb{Z}), L^*\}$; $p \in \mathbb{P}\}$ and $\{\mathrm{Cay}(\mathrm{PSL}(2, \mathbb{Z}/p\mathbb{Z}), W^*\}$; $p \in \mathbb{P}\}$ are all expander families. Now by Theorem 1.1, we are able to directly construct several expander families of G-graphs.

Thus, we can conclude the following.
**Theorem 5.10.** Let $\mathbb{P}$ be the set of all prime numbers. Then the $G$-graphs families given by

1. $\{\tilde{\Phi}(\text{PSL}(2, \mathbb{Z}/p\mathbb{Z}), \{S_2, S_2S_3\}); p \in \mathbb{P}\}$,

2. $\{\tilde{\Phi}(\text{PSL}(2, \mathbb{Z}/p\mathbb{Z}), \{S_2, S_2^2, S_2S_3\}); p \in \mathbb{P}\}$.

are expanders.

**Remark 5.11.**

1. Using Corollary 2.9, it is easy to check that the first expander family given in Theorem 5.10 is formed of simple graphs, while the second one is not. By Proposition 2.6, we also deduce that the multigraphs in both families are semiregular; in other words the above two expander families are irregular.

2. Each $\{\text{Cay}(G_i, S_i^*); i \in \mathbb{N}^+\}$ expander family enables us to construct several expander families of $G$-graphs depending on the choice of $S_i$ in $S_i^*$ with the possibility that some of these families may be isomorphic. For example, the following expander families $\{\tilde{\Phi}(\text{PSL}(2, \mathbb{Z}/p\mathbb{Z}), \{S_2, S_3^{-1}S_2^{-1}\}); p \in \mathbb{P}\}$, $\{\tilde{\Phi}(\text{PSL}(2, \mathbb{Z}/p\mathbb{Z}), \{S_2^{-1}, S_2S_3\}); p \in \mathbb{P}\}$, and $\{\tilde{\Phi}(\text{PSL}(2, \mathbb{Z}/p\mathbb{Z}), \{S_2^{-1}, S_3^{-1}S_2^{-1}\}); p \in \mathbb{P}\}$ are all isomorphic to $\{\tilde{\Phi}(\text{PSL}(2, \mathbb{Z}/p\mathbb{Z}), \{S_2, S_2S_3\}); p \in \mathbb{P}\}$. Similarly, the expander families $\{\tilde{\Phi}(\text{PSL}(2, \mathbb{Z}/p\mathbb{Z}), \{S_2, S_2^2, S_3^{-1}S_2^{-1}\}); p \in \mathbb{P}\}$, $\{\tilde{\Phi}(\text{PSL}(2, \mathbb{Z}/p\mathbb{Z}), \{S_2^{-1}, S_2^2, S_2S_3\}); p \in \mathbb{P}\}$, and $\{\tilde{\Phi}(\text{PSL}(2, \mathbb{Z}/p\mathbb{Z}), \{S_2^{-1}, S_2^2, S_3^{-1}S_2^{-1}\}); p \in \mathbb{P}\}$ are all isomorphic to $\{\tilde{\Phi}(\text{PSL}(2, \mathbb{Z}/p\mathbb{Z}), \{S_2, S_2^2, S_2S_3\}); p \in \mathbb{P}\}$.

<table><caption>Table 2: Comparison of some graph invariants between $\text{Cay}(G, S^*)$ and $\tilde{\Phi}(G, S)$ for $S = L$ and $S = W$.</caption><thead><tr><th></th><th>Cay(G, L*)</th><th>Φ̃(G, L)</th></tr></thead><tbody><tr><td>Order</td><td>|G|</td><td>Σ<sub>s∈S</sub> |G| / o(s) = 7/12 |G|</td></tr><tr><td>Degree</td><td>5-regular multigraph</td><td>d(u) = 4 for all u ∈ V<sub>S<sub>2</sub></sub><br>d(v) = 3 for all v ∈ V<sub>S<sub>2</sub>S<sub>3</sub></sub></td></tr><tr><td>Size</td><td>5/2 |G|</td><td>|G|</td></tr><tr><td></td><td>Cay(G, W*)</td><td>Φ̃(G, W)</td></tr><tr><td>Order</td><td>|G|</td><td>13/12 |G|</td></tr><tr><td>Degree</td><td>6-regular multigraph</td><td>d(u) = 8 for all u ∈ V<sub>S<sub>2</sub></sub><br>d(v) = 6 for all v ∈ V<sub>S<sub>2</sub>S<sub>3</sub></sub><br>d(w) = 4 for all w ∈ V<sub>S<sub>2</sub><sup>2</sup></sub></td></tr><tr><td>Size</td><td>3|G|</td><td>3|G|</td></tr></tbody></table>

3. Let $G$ be the projective special linear group, that is $G = \text{PSL}(2, \mathbb{Z}/p\mathbb{Z})$. In Table 2, we compare the order, the degree, and the size of the following expander family of
**Theorem 5.10.** Let $\mathbb{P}$ be the set of all prime numbers. Then the $G$-graphs families given by

1. $\{\tilde{\Phi}(\text{PSL}(2, \mathbb{Z}/p\mathbb{Z}), \{S_2, S_2S_3\}); p \in \mathbb{P}\}$,

2. $\{\tilde{\Phi}(\text{PSL}(2, \mathbb{Z}/p\mathbb{Z}), \{S_2, S_2^2, S_2S_3\}); p \in \mathbb{P}\}$.

are expanders.

**Remark 5.11.**

1. Using Corollary 2.9, it is easy to check that the first expander family given in Theorem 5.10 is formed of simple graphs, while the second one is not. By Proposition 2.6, we also deduce that the multigraphs in both families are semiregular; in other words the above two expander families are irregular.

2. Each $\{\text{Cay}(G_i, S_i^*); i \in \mathbb{N}^+\}$ expander family enables us to construct several expander families of $G$-graphs depending on the choice of $S_i$ in $S_i^*$ with the possibility that some of these families may be isomorphic. For example, the following expander families $\{\tilde{\Phi}(\text{PSL}(2, \mathbb{Z}/p\mathbb{Z}), \{S_2, S_3^{-1}S_2^{-1}\}); p \in \mathbb{P}\}, \{\tilde{\Phi}(\text{PSL}(2, \mathbb{Z}/p\mathbb{Z}), \{S_2^{-1}, S_2S_3\}); p \in \mathbb{P}\}, \text{ and } \{\tilde{\Phi}(\text{PSL}(2, \mathbb{Z}/p\mathbb{Z}), \{S_2^{-1}, S_3^{-1}S_2^{-1}\}); p \in \mathbb{P}\}$ are all isomorphic to $\{\tilde{\Phi}(\text{PSL}(2, \mathbb{Z}/p\mathbb{Z}), \{S_2, S_2S_3\}); p \in \mathbb{P}\}$. Similarly, the expander families $\{\tilde{\Phi}(\text{PSL}(2, \mathbb{Z}/p\mathbb{Z}), \{S_2, S_2^2, S_3^{-1}S_2^{-1}\}); p \in \mathbb{P}\}, \{\tilde{\Phi}(\text{PSL}(2, \mathbb{Z}/p\mathbb{Z}), \{S_2^{-1}, S_2^2, S_2S_3\}); p \in \mathbb{P}\}, \text{ and } \{\tilde{\Phi}(\text{PSL}(2, \mathbb{Z}/p\mathbb{Z}), \{S_2^{-1}, S_2^2, S_3^{-1}S_2^{-1}\}); p \in \mathbb{P}\}$ are all isomorphic to $\{\tilde{\Phi}(\text{PSL}(2, \mathbb{Z}/p\mathbb{Z}), \{S_2, S_2^2, S_2S_3\}); p \in \mathbb{P}\}$.

<table><caption>Table 2: Comparison of some graph invariants between $\text{Cay}(G, S^*)$ and $\tilde{\Phi}(G, S)$ for $S = L$ and $S = W$.</caption><thead><tr><th></th><th>Cay(G, L*)</th><th>Φ̃(G, L)</th></tr></thead><tbody><tr><th>Order</th><td>|G|</td><td>Σ<sub>s∈S</sub> |G| / o(s) = 7/12 |G|</td></tr><tr><th>Degree</th><td>5-regular multigraph</td><td>d(u) = 4 for all u ∈ V<sub>S<sub>2</sub></sub><br>d(v) = 3 for all v ∈ V<sub>S<sub>2</sub>S<sub>3</sub></sub></td></tr><tr><th>Size</th><td>5/2 |G|</td><td>|G|</td></tr><tr><th></th><td>Cay(G, W*)</td><td>Φ̃(G, W)</td></tr><tr><th>Order</th><td>|G|</td><td>13/12 |G|</td></tr><tr><th>Degree</th><td>6-regular multigraph</td><td>d(u) = 8 for all u ∈ V<sub>S<sub>2</sub></sub><br>d(v) = 6 for all v ∈ V<sub>S<sub>2</sub>S<sub>3</sub></sub><br>d(w) = 4 for all w ∈ V<sub>S<sub>2</sub><sup>2</sup></sub></td></tr><tr><th>Size</th><td>3|G|</td><td>3|G|</td></tr></tbody></table>

3. Let $G$ be the projective special linear group, that is $G = \text{PSL}(2, \mathbb{Z}/p\mathbb{Z})$. In Table 2, we compare the order, the degree, and the size of the following expander family of
Cayley graphs {$\text{Cay}(G, L^*)$, $p \in \mathbb{P}$} (resp. {$\text{Cay}(G, W^*)$, $p \in \mathbb{P}$}) with their corresponding ones in the G-graphs family {$\tilde{\Phi}(G, L)$; $p \in \mathbb{P}$} (resp. {$\tilde{\Phi}(G, W)$; $p \in \mathbb{P}$}) (see Theorem 5.10). Form the preceding table, it is easy to see that the infinite expander family of G-graphs $\tilde{\Phi}(G, L)$ is sparser than the original expander family of the 4-regular graphs $\text{Cay}(G, L^{\pm 1})$ and the 5-regular graphs $\text{Cay}(G, L^*)$. The same can be said concerning the infinite expander family of G-graphs $\tilde{\Phi}(G, W)$ and the Cayley graph one $\text{Cay}(G, W^*)$.

We close this section by the following corollary which can be easily obtained by using Theorem 5.10 and Corollary 3.6.

**Corollary 5.12.** Let $\mathbb{P}$ be the set of all prime numbers. Then the family of G-graphs given by

$$ \{\tilde{\tilde{\Phi}}(\text{PSL}(2, \mathbb{Z}/p\mathbb{Z}), \{S_2, S_2^2, S_2S_3\}); p \in \mathbb{P}\} $$

is an expander family.

## References

[1] M. Ajtai, J. Komlós and E. Szemerédi, An $O(n \log n)$ sorting network, in: D. S. Johnson, R. Fagin, M. L. Fredman, D. Harel, R. M. Karp, N. A. Lynch, C. H. Papadimitriou, R. L. Rivest, W. L. Ruzzo and J. I. Seiferas (eds.), STOC '83, ACM Press, New York, 1983 pp. 1-9, doi:10.1145/800061.808726, proceedings of the 15th Annual ACM Symposium on Theory of Computing, Boston, Massachusetts, April 25-27, 1983.

[2] J. A. Bondy and U. S. R. Murty, Graph Theory, volume 244 of Graduate Texts in Mathematics, Springer, London, 2008, doi:10.1007/978-1-84628-970-5.

[3] S. Bonvicini and T. Pisanski, A novel characterization of cubic Hamiltonian graphs via the associated quartic graphs, *Ars Math. Contemp.* **12** (2017), 1-24, https://amc-journal.eu/index.php/amc/article/view/921.

[4] A. Bretto and A. Faisant, Cayley graphs and G-graphs: some applications, *J. Symbolic Comput.* **46** (2011), 1403-1412, doi:10.1016/j.jsc.2011.08.016.

[5] A. Bretto, A. Faisant and L. Gillibert, G-graphs: a new representation of groups, *J. Symbolic Comput.* **42** (2007), 549-560, doi:10.1016/j.jsc.2006.08.002.

[6] A. Bretto, A. Faisant and L. Gillibert, New graphs related to $(p, 6)$ and $(p, 8)$-cages, *Comput. Math. Appl.* **62** (2011), 2472-2479, doi:10.1016/j.camwa.2011.07.033.

[7] A. Bretto, L. Gillibert and B. Laget, Symmetric and semisymmetric graphs construction using G-graphs, in: M. Kauers (ed.), *ISSAC '05*, ACM Press, New York, 2005 pp. 61-67, doi:10.1145/1073884.1073895, proceedings of the 30th International Symposium on Symbolic and Algebraic Computation held in Beijing, July 24-27, 2005.

[8] E. Breuillard and A. Gamburd, Strong uniform expansion in $SL(2, p)$, *Geom. Funct. Anal.* **20** (2010), 1201-1209, doi:10.1007/s00039-010-0094-3.

[9] J.-F. Culus, M. Demange, R. Marinescu-Ghemeci and C. Tanasescu, About some robustness and complexity properties of G-graphs networks, *Discrete Appl. Math.* **182** (2015), 34-45, doi:10.1016/j.dam.2014.11.003.

[10] J. Friedman, *A Proof of Alon's Second Eigenvalue Conjecture and Related Problems*, Memoirs of the American Mathematical Society, American Mathematical Society, Providence, RI, 2008, doi:10.1090/memo/0910.
Cayley graphs {$Cay(G, L^*), p \in \mathbb{P}$} (resp. {$Cay(G, W^*), p \in \mathbb{P}$}) with their corresponding ones in the G-graphs family {$\tilde{\Phi}(G, L); p \in \mathbb{P}$} (resp. {$\tilde{\Phi}(G, W); p \in \mathbb{P}$}) (see Theorem 5.10). Form the preceding table, it is easy to see that the infinite expander family of G-graphs $\tilde{\Phi}(G, L)$ is sparser than the original expander family of the 4-regular graphs $Cay(G, L^{\pm 1})$ and the 5-regular graphs $Cay(G, L^*)$. The same can be said concerning the infinite expander family of G-graphs $\tilde{\Phi}(G, W)$ and the Cayley graph one $Cay(G, W^*)$.

We close this section by the following corollary which can be easily obtained by using Theorem 5.10 and Corollary 3.6.

**Corollary 5.12.** Let $\mathbb{P}$ be the set of all prime numbers. Then the family of G-graphs given by

$$ \{\tilde{\Phi}(\text{PSL}(2, \mathbb{Z}/p\mathbb{Z}), \{S_2, S_2^2, S_2S_3\}); p \in \mathbb{P}\} $$

is an expander family.

## References

[1] M. Ajtai, J. Komlós and E. Szemerédi, An $O(n \log n)$ sorting network, in: D. S. Johnson, R. Fagin, M. L. Fredman, D. Harel, R. M. Karp, N. A. Lynch, C. H. Papadimitriou, R. L. Rivest, W. L. Ruzzo and J. I. Seiferas (eds.), STOC '83, ACM Press, New York, 1983 pp. 1–9, doi:10.1145/800061.808726, proceedings of the 15th Annual ACM Symposium on Theory of Computing, Boston, Massachusetts, April 25 – 27, 1983.

[2] J. A. Bondy and U. S. R. Murty, *Graph Theory*, volume 244 of *Graduate Texts in Mathematics*, Springer, London, 2008, doi:10.1007/978-1-84628-970-5.

[3] S. Bonvicini and T. Pisanski, A novel characterization of cubic Hamiltonian graphs via the associated quartic graphs, *Ars Math. Contemp.* **12** (2017), 1–24, https://amc-journal.eu/index.php/amc/article/view/921.

[4] A. Bretto and A. Faisant, Cayley graphs and G-graphs: some applications, *J. Symbolic Comput.* **46** (2011), 1403–1412, doi:10.1016/j.jsc.2011.08.016.

[5] A. Bretto, A. Faisant and L. Gillibert, G-graphs: a new representation of groups, *J. Symbolic Comput.* **42** (2007), 549–560, doi:10.1016/j.jsc.2006.08.002.

[6] A. Bretto, A. Faisant and L. Gillibert, New graphs related to $(p, 6)$ and $(p, 8)$-cages, *Comput. Math. Appl.* **62** (2011), 2472–2479, doi:10.1016/j.camwa.2011.07.033.

[7] A. Bretto, L. Gillibert and B. Laget, Symmetric and semisymmetric graphs construction using G-graphs, in: M. Kauers (ed.), *ISSAC '05*, ACM Press, New York, 2005 pp. 61–67, doi:10.1145/1073884.1073895, proceedings of the 30th International Symposium on Symbolic and Algebraic Computation held in Beijing, July 24 – 27, 2005.

[8] E. Breuillard and A. Gamburd, Strong uniform expansion in $SL(2, p)$, *Geom. Funct. Anal.* **20** (2010), 1201–1209, doi:10.1007/s00039-010-0094-3.

[9] J.-F. Culus, M. Demange, R. Marinescu-Ghemeci and C. Tanasescu, About some robustness and complexity properties of G-graphs networks, *Discrete Appl. Math.* **182** (2015), 34–45, doi:10.1016/j.dam.2014.11.003.

[10] J. Friedman, *A Proof of Alon's Second Eigenvalue Conjecture and Related Problems*, Memoirs of the American Mathematical Society, American Mathematical Society, Providence, RI, 2008, doi:10.1090/memo/0910.
[11] K. P. Hart, J. van Mill and P. Simon (eds.), *Recent Progress in General Topology III*, Atlantis Press, Paris, 2014, doi:10.2991/978-94-6239-024-9.

[12] S. Hoory, N. Linial and A. Wigderson, Expander graphs and their applications, *Bull. Amer. Math. Soc. (N. S.)* **43** (2006), 439–561, doi:10.1090/s0273-0979-06-01126-8.

[13] M. Klawe, Limitations on explicit constructions of expanding graphs, *SIAM J. Comput.* **13** (1984), 156–166, doi:10.1137/0213011.

[14] M. Krebs and A. Shaheen, *Expander Families and Cayley Graphs: A Beginner's Guide*, Oxford University Press, New York, 2011.

[15] Z. Landau and A. Russell, Random Cayley graphs are expanders: a simple proof of the Alon-Roichman theorem, *Electron. J. Combin.* **11** (2004), #R62, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v11i1r62.

[16] A. Lubotzky, *Discrete Groups, Expanding Graphs and Invariant Measures*, Modern Birkhäuser Classics, Birkhäuser Verlag, Basel, 2010, doi:10.1007/978-3-0346-0332-4, with an appendix by Jonathan D. Rogawski.

[17] A. Lubotzky, Expander graphs in pure and applied mathematics, *Bull. Amer. Math. Soc. (N. S.)* **49** (2012), 113–162, doi:10.1090/s0273-0979-2011-01359-3.

[18] F. Merola, A. Pasotti and M. A. Pellegrini, Cyclic and symmetric hamiltonian cycle systems of the complete multipartite graph: even number of parts, *Ars Math. Contemp.* **12** (2017), 219–233, https://amc-journal.eu/index.php/amc/article/view/847.

[19] O. Reingold, S. Vadhan and A. Wigderson, Entropy waves, the zig-zag graph product, and new constant-degree expanders, *Ann. of Math.* **155** (2002), 157–187, doi:10.2307/3062153.

[20] D. J. S. Robinson, *A Course in the Theory of Groups*, volume 80 of *Graduate Texts in Mathematics*, Springer-Verlag, New York, 2nd edition, 1996, doi:10.1007/978-1-4419-8594-1.

[21] J. Rosenhouse, Isoperimetric numbers of Cayley graphs arising from generalized dihedral groups, *J. Combin. Math. Combin. Comput.* **42** (2002), 127–138.

[22] M.-C. Tanasescu, *Graphs, Partitions and Cosets: G-graphs and Their Applications*, Ph.D. thesis, Université des Antilles et de la Guyane, 2014, http://www.theses.fr/2014AGUY0787.

[23] A. Terras, *Fourier Analysis on Finite Groups and Applications*, volume 43 of *London Mathematical Society Student Texts*, Cambridge University Press, Cambridge, 1999, doi:10.1017/cbo9780511626265.
[11] K. P. Hart, J. van Mill and P. Simon (eds.), *Recent Progress in General Topology III*, Atlantis Press, Paris, 2014, doi:10.2991/978-94-6239-024-9.

[12] S. Hoory, N. Linial and A. Wigderson, Expander graphs and their applications, *Bull. Amer. Math. Soc. (N. S.)* **43** (2006), 439–561, doi:10.1090/s0273-0979-06-01126-8.

[13] M. Klawe, Limitations on explicit constructions of expanding graphs, *SIAM J. Comput.* **13** (1984), 156–166, doi:10.1137/0213011.

[14] M. Krebs and A. Shaheen, *Expander Families and Cayley Graphs: A Beginner's Guide*, Oxford University Press, New York, 2011.

[15] Z. Landau and A. Russell, Random Cayley graphs are expanders: a simple proof of the Alon-Roichman theorem, *Electron. J. Combin.* **11** (2004), #R62, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v11i1r62.

[16] A. Lubotzky, *Discrete Groups, Expanding Graphs and Invariant Measures*, Modern Birkhäuser Classics, Birkhäuser Verlag, Basel, 2010, doi:10.1007/978-3-0346-0332-4, with an appendix by Jonathan D. Rogawski.

[17] A. Lubotzky, Expander graphs in pure and applied mathematics, *Bull. Amer. Math. Soc. (N. S.)* **49** (2012), 113–162, doi:10.1090/s0273-0979-2011-01359-3.

[18] F. Merola, A. Pasotti and M. A. Pellegrini, Cyclic and symmetric hamiltonian cycle systems of the complete multipartite graph: even number of parts, *Ars Math. Contemp.* **12** (2017), 219–233, https://amc-journal.eu/index.php/amc/article/view/847.

[19] O. Reingold, S. Vadhan and A. Wigderson, Entropy waves, the zig-zag graph product, and new constant-degree expanders, *Ann. of Math.* **155** (2002), 157–187, doi:10.2307/3062153.

[20] D. J. S. Robinson, *A Course in the Theory of Groups*, volume 80 of *Graduate Texts in Mathematics*, Springer-Verlag, New York, 2nd edition, 1996, doi:10.1007/978-1-4419-8594-1.

[21] J. Rosenhouse, Isoperimetric numbers of Cayley graphs arising from generalized dihedral groups, *J. Combin. Math. Combin. Comput.* **42** (2002), 127–138.

[22] M.-C. Tanasescu, *Graphs, Partitions and Cosets: G-graphs and Their Applications*, Ph.D. thesis, Université des Antilles et de la Guyane, 2014, http://www.theses.fr/2014AGUY0787.

[23] A. Terras, *Fourier Analysis on Finite Groups and Applications*, volume 43 of *London Mathematical Society Student Texts*, Cambridge University Press, Cambridge, 1999, doi:10.1017/cbo9780511626265.