ARS MATHEMATICA CONTEMPORANEA ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 15 (2018) 425-440 https://doi.org/10.26493/1855-3974.1537.97c (Also available at http://amc-journal.eu) On constructing expander families of G-graphs* Mohamad Badaoui Normandie Univ-Caen, GREYC CNRS UMR-6072, Campus II, Bd MarechalJuin 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 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 *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. 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) Abstract ©® This work is licensed under https://creativecommons.org/licenses/by/3.0/ 426 Ars Math. Contemp. 15 (2018) 441-466 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* = |Js£S (s) \ {e} (i.e. if S = {si,..., sk}, then S* = {si,..., s0(si)-i,..., sk,..., sk(sk)-1}, where o(sj) denotes the order of s4), we prove the following main result (see below for terminology). Theorem 1.1. If {Cay(Gn,Sn*), n G N+} is an expander family, then {i>(G„,S„), n G 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 M. Badaoui et al.: On constructing expander families of G-graphs 427 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,., 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 g1 = e. Let S = {si,...,sfc } be anon-empty subset of G, and let Omax(S) and Omin(S) be respectively the maximum and the minimum o(sj) for all i e {1,..., k}. A subset S of G is said to be symmetric if every element in S has its inverse in S. We define (S} to be the smallest subgroup of G which contains S. If (S) = 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 TH of G is said to be a right transversal for H if TH 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 \ A = {x e B and x e A} and A = U \ A. The special linear group SL(2, Z/qZ) is defined as follows: The projective special linear group PSL(2, Z/qZ) = SL(2, Z/qZ)/{± 12}, where 12 is the 2 x 2 identity matrix. 2.2 Multigraphs All multigraphs considered in this paper are undirected and finite. Generally, we define an undirected multigraph r as the triple (V (r), E(r), £r), where V (r) is the set of vertices, E(r) is the set of edges, and £r is an incidence function that associates with each edge of r an unordered pair of vertices of r. 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 r, denoted by d(v) is the number of edges 428 Ars Math. Contemp. 15 (2018) 441-466 of r incident to v where each loop counts as two edges. The maximum and minimum degree of a multigraph r are denoted by A(T) and ¿(r) respectively. A multigraph r is d-regular if d(u) = d for all u G V(r). 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(r) of a multigraph r is defined by: diam(r) = max{d(u, v); u, v G V(r)}. Let r = (Vi, Ei, ^i) and r2 = (V2, E2, £2) be two multigraphs, a homomorphism from r1 to r2 is a couple (f, f #) where f: V ^ V2 and f # : E1 ^ E2 such that if ^1(a) = {u,v} then £2(f#(a)) = {f(u),f(v)}. A graph isomorphism is the couple (f, f #) where f and f # are bijective. We say that r1 is isomorphic to r2 if there exists an isomorphism between r1 and r2. In such a case, we write r ~ r'. A multigraph r = (V, E, £r) is k-partite if there is a partition of V into k parts such that each part is a stable set. We will write r = ([JieI Vi; E) where I = {1,..., k}. A multigraph is minimum k-partite (k > 1) if it is k-partite and not (k - 1)-partite. It is easy to verify that for any multigraph r, there exists k such that r is minimum k-partite. If a multigraph r is k-partite, then we will say that (Vi)ie{1j2 ...jfc} is a k-representation of r. Cayley graphs offer a combinatorial depiction of groups and their generators. More precisely, the Cayley graph 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.x for some s G S. It is well-known that Cay(G, S) is connected if and only if G = (S) (see for example [14]). 2.3 G-graphs Definition 2.1. Let (G,., e) be a finite group. Let S be a nonempty subset of G. For s G S, consider the cycles (s)x = (x, sx,..., so(s)-1 x) of permutation gs: x ^ sx. Note that (s)x is the set {x, sx,..., so(s)-1x}. We define the G-graph $(G, S) in the following way: 1. The vertex set of $(G, S) is V = |Js£S Vs where Vs = {(s)x, x G T(s)} where T(s) is a right transversal for the subgroup (s). 2. For each (s)x, (t)y G V, there exists edge between (s)x and (t)y labeled g for each g G (s)x n (t)y, such an edge will be denoted by ({(s)x, (t)y}, g). If card((s)x n (t)y) = p, p > 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 (s) form a partition of G, (Vs)seS is a |S|-representation of $(G, S). Every vertex (s)x has o(s) loops. We denote by $(G, S) the multigraph $(G, S) without loops. The multigraph (G, S) = ([JseS Vs; E) be a G-graph with \G\ = n and \S\ = k. Then the following holds. d((s)x) = o(s)(k — 1), for all (s)x G Vs, d((s)x) = n(k — 1), for all s G S, (s)xevs \E(*(G,S))\ = . 2.3.1 New results on G-graphs Proposition 2.6. Let $(G, S) be any G-graph such that \S\ = {si,..., sk}. Then the following are equivalent: 1 This definition is due to [4]. 430 Ars Math. Contemp. 15 (2018) 441-466 i. $(G, S) is d-regular, ii. o(si) = kzi, for all i € {1, ...,k}, iii. |Vsi | = | VSj |, for all i,j € {1,..., k}. Proof. Let (s)x € Vs, where s € S. From Proposition 2.5, we have d((s)x) = o(s)(k - 1) or o(s) = ^ifM, k - 1 and then = JG[ = |G|(k - 1) 1 s| o(s) d((s)x) . Therefore o(si) = o(sj) if and only if |VSi | = |VSj |, for all i, j € {1,..., k}. □ Remark 2.7. When $(G, S) is a regular multigraph, we use the notation O instead of o(s) for any s € S. The following lemma can be found in [22]. Lemma 2.8 ([22]). Let $(G, S) be a G-graph with S = {si,..., sk} a generating set of G, then all the multi-edges between levels Vsi and Vsj have the same multiplicity l(si)n(sj )|. As a result, we have the following corollary. Corollary 2.9. Let $(G, S) be a G-graph with S = {si,..., sk}. Then $(G, S) is a simple graph if and only if (si) n (sj) = {e} for all i, j € {1,..., k} with i = j. 2.4 Expanders Before we define expander graphs, we need to define some expansion parameters. Let r = (V, E, £r) be a non-oriented multigraph with |V| > 2 and V' be a subset of V. The edge boundary of V' in r denoted by dV'(r) (or simply dV' when no ambiguity occurs) is defined as follows: 5V'(r) = {a € E; £r(a) € V' x V'}. In other words, this is the set of edges emanating from the set V' to its complement. The rate of expansion of r is then defined as follows: h(r)= min . ( ) o ^o as i — to. iii. There exists an e e R+ such that e < h($(Gj, Sj)) for all i e N+. Note that 2 < |Sj| since otherwise <&(Gj, Sj) will be a disconnected multigraph so that h(<&(Gj, Sj)) = 0, and so it is clear that maxjr1, r2} < r. On the other hand, we say that {Gj, i e N+ } is a Gay-expander family, if for every i e N+ there exists a symmetric generating subset Sj of Gj such that j|Sj| : i e N+} is uniformly bounded and provided that {Cay(Gj, Sj), i e N+} is an expander family. More explicitly, {Gj, i e N+} is a Cay-expander family if the following 2 conditions are satisfied: i. |V(Cay(Gj, Sj))| = |Gj| — to as i — to, 432 Ars Math. Contemp. 15 (2018) 441-466 ii. There exists an e G R+ such that e < fe(Cay(G,, S,)) for all i G N+. Example 3.2. For every i G N+, let D2i be the dihedral group: D2i = (s,/ | s2 = / = e, s/ = /-1s) . In 2002, Rosenhouse [21] showed that h(Cay(D2i, {/, /-1, s})) = 4. Hence, h(Cay(D2i, {/, /-1,s})) ^ 0 as i ^ to. Thus {Cay(D2i, {/, /-1,s}), i G N+} is not an expander family. In fact, it was shown later (see [14]) that for any set of generator S, of D2i, {Cay(D2i, S,), i G N+} is not an expander family. Thus {D2i, i G N+} is not a -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 = {s1,..., sk} and let $(G, S) be the corresponding G-graph, then diam($(G,S)) < |S|. Proof. Let (sp)x, (sq)y G V($(G, S)), where x, y G G and 1 < p, q < |S| = k. Since G = (S) is an abelian group, then il ip iq ik il ip iq — 1 iq+1 ik iq = s11 . . . spp . . . sqq ... skky = s11 . . . spp ... sq-1 sqq_+1 . . . sfcfc sgqy, where 1 < i; < o(s;) for all 1 < l < k. It is easy to see that (sp)x is adjacent to (s1)s22 ... skky which is in turn connected to (s2)s33 ... s^y and so on up to (sk)s^qy which is connected to (sq)y. Thus d((sp)x, (sq)y) < |S|. □ Corollary 3.4. No family of abelian groups is a G-expander. Proof. Suppose that {G,, i G N+} is a family of finite abelian groups and that {^(G^ S,), i G N+ } is an expander family. Then there exists r G N+ such that |S,| < r for all i G N+. But then by the preceding lemma diam( |Y|. In Cay(Gn,S;), we have |dW | > e|W |.Let f: dW ^ dH, {x,y} ^ ({(s, )x, (sj )y},y), where x € W, y € W, i and j are chosen so that xy-1 € (s,) and y € U(s)xeH- (s)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 € (s,) and y = y'. So for all a € dH, |f-1(a)| < Omax(Sn). Hence, |dH| > IdWI > e|W| > emax, |Xj| > e|X| Omax(Sn) °max(Sn) °max(Sn) °max(Sn) |Sn1 Using |dH| > |Y| and |H| = |X| + |Y|, we obtain |dH|>1mi" {omaxcSn)!^ •1}|H|> 2min {• 1}|H|. This completes the proof. □ The following results are obvious consequences of Theorem 1.1. Corollary 3.5. If {Gn, n € N+} is a Cay-expanderfamily, then it is also a G-expander family. Corollary 3.6. If {Cay(Gj,S*), i € N+} is an expander family, then {$(Gj,Sj), i € N+} is also an expander family. Proof. By Theorem 1.1, {$(Gj, S,), i € N+} is an expander family. By Definition 3.1, there exists r € N+ such that o(sj) < r, for every sj € S,. Then | (sj1) n (sj2) | < r for all sj1, sj2 € Sj. Thus h($((;i'Si)) < h(2 i|o(si)=2 1 10 and S = {±1, ±2}. Then Cay(Z/nZ, S) is 4-regular multigraph on n vertices. Let H be a subgraph of Cay(Z/nZ, S) such that V(H) = {1, 2,3,7}. Let s1 = +1 and s2 = +2. Then Nsi (H) = {4,8}, Ns-i (H) = {o, 6}, NS2 (H) = {4, 5,9}, and Ns-i (H) = {0, 5,n - 1}. Thus 1 |dH(Cay(Z/nZ, S))| = 2(|N,i (H)| + |NS2 (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 {Cay(G,, { s±1,s±1}); i G N+} be an expander family. If o(s1), o(s2), and o(s1s2) > 2, then {Cay(Gj, {s^1, s1s2, s-1s-1}); i G N+} is also an expander family. Proof. Let V(H) = {x1,..., xt} G G. Define d'H, d"H to be the sets of emanating edges from V(H) in the multigraphs Cay(Gj, { s±\s^1}) and Cay(Gj, {s^1, S1S2, s-1s-1}) respectively. By Lemma 5.2, we have: |d'H| = 2|NSi(H)| + 2|NS2(H)|, and (1) |d''H | = 2|NSi (H )| + 2|NSiS2 (H )|. (2) Let y G Ns2 (H), y = s2x for some x G H. i. If s1y G H, then s1s2x G H and s1s2x G Nsis2 (H). ii. And if s1y G H, then s1s2x G H. Let H1 and H2 be the set of vertices of H defined as follows: H1 = {x G H/s2x G H and s1s2x G H}, H2 = {x G H/s2x G H and s1s2x G H}. From equalities (1) and (2), we have 2|NSi (H )| + 2|NS2 (H )(H1)| + 2^ (H )(H2 )| = |d'H |, 2|NSi(H)| +2|NSiS2(H)(H1)| + 2^(H)(H2)| < |d''H|. M. Badaoui et al.: On constructing expander families of G-graphs 437 From the definition of H2, we have |NSlS2 (H)(H2)| = 0, then 2|NS1 (H)| + 2|nSiS2(H)(Hi)| < |d''H|. Therefore, it holds that 2|NSi(H)| + 4|NSiS2(H)(Hi)| - 2^(H)(Hi)| - 2^(H)(H2)| < 2|d''H| - |d'H|. From the definition of H1, we have |NSlS2(H)(H1)| = |NS2(H)(H1)| and similarly from the definition of H2, we have |NS2(H)(Hf)| = |Ns-i (H) nNS2 (h)|. Thus, 2|NSi(H)| + 2|NS2(H)(Hi)|- 2|Ns-i(H) n (H)| < 2|d''H| - |d'H|. Noticing that |Ns-i (H) n NS2 (H)| < |Ns-i (H)| = |Nsi (H)|, then 2|NS2(H)(Hi)| < 2|d''H| - |d'H|. Finally, we obtain 0 « (PSL(2, Z/pZ), {S-1, S2, S-1S-1}); p e P} are all isomorphic to {$(PSL( 2, Z/pZ), {S2,S|, S2S3}); p e P}. Table 2: Comparison of some graph invariants between Cay(G, S*) and $(G, S) for S = L and S = W. Cay(G, L*) $(G, L) Order |G| dtcS) = 12|G| Degree 5-regular multigraph d(u) =4 for all u G VS2 d(v) = 3 for all v G Vs2s3 Size 2 |G| |G| Cay(G, W*)