Keywords: 48

d'un graphe. . . . . . .

I would like to dedicate this thesis to my first honest love, to my loyal fan and motivational source, to my mom, rest in peace, to the most honorable man I ever knew, to my best life teacher, to my dad, to my loving parents, thank you. The reason that stands behind our choice is first a notable identifiable link between these two classes of graphs that we prove. This relation is employed significantly to get many new results. Another reason is the general form of G-graphs, that gives us the intuition that they must have in many cases such as the relatively high connectivity property.

The adopted methodology in this thesis leads to the identification of various approaches for constructing an infinite family of expander graphs. The effectiveness of our techniques is illustrated by presenting new infinite expander families of Cayley and G-graphs on certain groups. Also, since expanders stand in no single stem of graph theory, this brings us to investigate several closely related threads from a new angle. For instance, we obtain new results concerning the computation of spectra of certain Cayley and G-graphs, and the construction of several new infinite classes of integral and strongly regular Cayley graphs.

Chapters Description

This thesis contains seven chapters and they are organized as follows:

1. In Chapter 1, we recall some standard terminologies and results from the theory of groups, graphs, and hypergraphs as well as algebraic graph theory.

2. In Chapter 2, we present the different definitions and results from the theory of Ggraphs. Many new results regarding principal cliques, the regularity, and the simplicity of G-graphs are revealed. This paves the way to approach certain problems in this theory from a new perspective.

3. In Chapters 3 and 4, we collect and generalize some results from the theory of expanders. A method for constructing expander families of G-graphs is presented and is used to construct new expander families of regular and irregular graphs. Also, we

show that G-graphs on abelian groups, like the case for Cayley graphs, can never yield a family of expander graphs. 4. In Chapter 5, several results concerning spectral hypergraph theory are revealed. These results can be considered as simple generalizations to their corresponding ones for the case of graphs. Also, several isomorphic relations between the Cayley graphs and G-graphs are presented. This leads to certain results regarding some extensively studied problems in the theory of Cayley and G-graphs.

5. Finally, in Chapter 6, we discuss the possible horizons for future researches, the road- En quelques mots, un graphe d'expansion est un graphe qui combine tous ces trois aspects que l'on demande à un réseau de communication pour être « acceptable ».

maps
Une autre raison importante qui rend les graphes expansion si populaires est qu'ils peuvent être étudiés sous angles différents. Les approches peuvent être considérées, par exemple par le biais de la combinatoire, des marches aléatoires, de l'algébrique (voir par exemple [START_REF] Klawe | Limitations on explicit constructions of expanding graphs[END_REF][START_REF] Rogawski | Discrete Groups, Expanding Graphs and Invariant Measures[END_REF]). Cela conduit à des liens extrêmement profonds et fascinants entre la théorie des graphes d'une part, l'informatique et les mathématiques pures, comme la théorie des nombres d'autre part.

En théorie des nombres, ils sont utilisés pour donner une généralisation de la méthode du affine sieve. De nombreuses applications à la géométrie et aux 3-variétés hyperboliques sont présentées dans [START_REF] Lubotzky | Expander graphs in pure and applied mathematics[END_REF]. De plus, le fait que de nombreuses familles d'expansion construites soient des graphes de Cayley montre le lien étroit existant entre les graphes d'expansion et la théorie des groupes. Dans l'autre sens et de façon surprenante, les graphes d'expansion apparaissent également dans la preuve de nombreux résultats dans la théorie des groupes [START_REF] Hoory | Expander graphs and their applications[END_REF].

List of tables xix Familles d'expansion

Soit Γ = (V, E, ξ Γ ) un graphe avec |V | ≥ 2 et V ′ un sous-ensemble de V . La frontière de V ′ dans Γ notée ∂V ′ (Γ) est définie comme suit:

∂V ′ (Γ) = {α ∈ E; ξ Γ (α) ∈ V ′ ×V ′ }.
En d'autres termes, c'est l'ensemble des arêtes émanant de l'ensemble V ′ à son complément.

Le taux d'expansion de Γ est défini comme suit :

h(Γ) = min |∂V ′ | |V ′ | ; V ′ ⊂ V et |V ′ | ≤ |V | |2| . Pour ε ∈ R * + , le graphe Γ est ε-expander si ε ≤ h(Γ).
Notons que

1. Pour un graphe Γ et V ′ ⊂ V (Γ) où |V ′ | ≤ V (Γ) 2 , nous avons h(Γ)|V ′ | ≤ |∂V ′ |.
Alors, quand h(Γ) augmente, la connectivité du graphe Γ augmentera aussi, puisque chaque ensemble de sommets avec une cardinalité inférieure à la moitié de V (Γ) aura plus de voisins par rapport à sa cardinalité. En d'autres termes, nous évitons autant que possible la situation de goulot d'étranglement (bottleneck situation), où un ensemble de sommets a relativement -à sa cardinalité-une petite quantité d'arêtes à son complément.

2. Si V ′ un sous-ensemble de l'ensemble de sommets V (Γ), alors l'ensemble des arêtes de V ′ à son complément est le même dans le sens opposé, c'est-à-dire ∂V ′ = ∂ (Γ\V ′ ). Par conséquent, il ne sert à rien d'inclure les ensembles de sommets

V ′ lorsque |V ′ | ≥ |V (Γ)| 2 .
Si une famille de graphes Γ = (V, E, ξ Γ ) a les trois conditions suivantes:

i. |V i | → ∞ quand i → ∞.
ii. Il existe r ∈ N + où ∆(Γ i ) ≤ r pour tous i ∈ N + . C'est-à-dire {Γ i , i ∈ N + } est une séquence de graphes à degré borné.

iii. Il existe ε ∈ R * + où Γ i est un ε-expansion pour tous i ∈ N + , alors cette famille est une famille d'expansion et un élément de cette famille est un graphe d'expansion.

Quelques approches précédentes pour la construction de graphes d'expansion 2 Les différentes relations entre les trois invariants.

λ 2 (Γ) or µ n-1 diam(Γ) h(Γ) ou υ Γ d-λ 2 2 ≤ h(Γ) ≤ (d + λ 2 )(d -λ 2 ) 1 2 µ n-1 ≤ υ Γ ≤ √ 2µ n-1 diam(Γ) ≤ 2 log 1 + h(Γ) d log(|Γ|) λ 2 (Γ) - diam(Γ) ≤ ⌈log(|Γ| - 1)\ log(d\|λ 2 (Γ)|)⌉ Table
En utilisant ces invariants de graphes et certaines techniques algébriques, de nombreux résultats partiels ont été obtenus. En fait, la plupart de ces résultats ont donné des réponses négatives à cette question posée ci-dessus pour certains groupes. Par exemple, il a été prouvé qu'aucune famille de graphes de Cayley sur les groupes abéliens ou le groupe diédral n'est pas un graphe d'expansion (voir [START_REF] Hoory | Expander graphs and their applications[END_REF][START_REF] Lubotzky | Expander graphs in pure and applied mathematics[END_REF]).

En 1973, Margulis [START_REF] Margulis | Explicit constructions of expanders[END_REF] a donné la première construction explicite d'une famille d'expansion de graphes de Cayley les graphes de Cayley restent pendant environ trois décennies et malgré les efforts énormes la seule méthode principale pour construire des graphes d'expansion. En 2002, Reingold et al (voir [START_REF] Reingold | Entropy waves, the zig-zag graph product, and new constant-degree expanders[END_REF]) présentent une méthode combinatoire directe pour construire une famille d'expansion le "produit zig-zag". Le produit zig-zag de deux graphes Γ et Γ ′ produit un graphe plus grand dont la deuxième plus grande valeur propre λ 2 dépend des spectres de Γ et Γ ′ , le taux d'expansion du graphe produit est légèrement plus petit que celui de Γ ′ .

G-graphes

Soit G un groupe fini et Soit S = {s 1 , . . . , s k } un multiset non vide de G. Nous définissons le G-graphe Φ(G, S) de la façon suivante :

1. L'ensemble des sommets de Φ(G, S) est V = s∈S V s où V s = {(s)x, x ∈ T ⟨s⟩ } est une transversale à droite pour le sous-groupe ⟨s⟩ .

2. Pour chaque (s)x, (t)y ∈ V , si card(⟨s⟩ x∩⟨t⟩ y) = p, p ≥ 1, alors il existe un multi-arête d'ordre p entre (s)x et (t)y.

Notons que

1. Puisque S est un multiset, la répétition d'un élément s ∈ S est autorisée. Si le multiset S contient p occurrences de s, alors le G-graphe Φ(G, S) a p copies du même niveau V s . Les sommets de ces niveaux sont des sommets jumeaux puisqu'ils ont le même nombre d'arêtes entre eux et n'importe quel autre sommet de leurs voisins.

2. Les cosets de ⟨s⟩ forment une partition de G, alors (V s ) s∈S est une |S|-representation de Φ(G, S). Notons aussi que si card(⟨s⟩ x ∩ ⟨s⟩ x) = o(s), alors chaque sommet (s)x de Φ(G, S) a o(s) boucles. Dans la définition suivante, G-graphes sont présentés comme des graphe sans boucles. • Soit Φ(G, S) un G-graph et S = {s 1 , . . . , s k }. Alors, les éléments suivants sont équiva-

lents: i. Φ(G, S) est d-régulière graphe, ii. o(s i ) = d k -1 pour tout i ∈ {1, . . . , k}, iii. |V s i | = |V s j | pour tout i, j ∈ {1, . . . , k}.
De plus, le nombre d'arêtes à l'intérieur de chaque clique principale est

1 2 ∑ s i ∈S ∑ s j ∈S\{s i } | ⟨s i ⟩ ∩ s j |. • Soit V 1 ,V 2 deux sous-ensembles de V ( Φ(G, S)). Nous dénotons par E(V 1 ,V 2 ) l'ensemble de tous les arêtes entre V 1 et V 2 .
Pour x ∈ G, E x est le nombre de tous les arêtes entre la clique principale C x et le reste du graphe, c'est

E x = |E V (C x ),V (C x ) |.
1. Soit Φ(G, S) un G-graph et S = {s 1 , . . . , s k }. Alors pour tous x ∈ G, nous avons

E x = k ∑ i=1 (k -1)o(s i ) -∑ s i ∈S ∑ s j ∈S\{s i } | ⟨s i ⟩ ∩ s j |.

Si Φ(G, S) est simple, alors

E x = (k -1)( k ∑ i=1 o(s i ) -k).
De plus, si Φ(G, S) est un graphe simple régulier, alors

E x = k(k -1)(O -1). xxiv List of tables 3. Le G-graph Φ(G, S) est simple si et seulement si E x = (k -1)( k ∑ i=1 o(s i ) -k) où x ∈ G.
G-graphes : Une nouvelle méthode pour construire des graphes d'expansion

}.

Si {Cay(G n , S * n ), n ∈ N + } est une famille d'expansion, alors Soit

{ Φ(G n , S n ), n ∈ N + }, et { Φ(G n , S n ), n ∈ N + },
degré graphe |S * |-régulier d(u) = o(s)(|S| -1) pour tous u ∈ V s et s ∈ S Nombre d'arêtes 1 2 |G||S * | = 1 2 |G|(∑ s∈S o(s) - |S|) 1 2 |G||S|(|S| -1)
S 1 = 0 -1 1 0 , S 2 = 0 1 -1 0 et S 3 = 1
G, L * ), i ∈ P} et {Cay(G,W * ), i ∈ P} avec leurs G-graphes correspondants { Φ(G; L), i ∈ P} et { Φ(G;W ), i ∈ N + }. Cay(G, L * ) Φ(G; L) Nombre de sommets |G| ∑ s∈S |G| o(s) = 7 12 |G| degré graphe 5-régulier d(u) = 4 pour tous u ∈ V S 2 d(v) = 3 pour tous v ∈ V S 2 S 3 Nombre d'arêtes 5 2 |G| |G|
u ∈ V S 2 d(v) = 6 pour tous v ∈ V S 2 S 3 d(w) = 4 pour tous w ∈ V S 2 2 Nombre d'arêtes 3|G| 3|G|
1 = {S 1 , S 1 S 3 }, B 2 = {S 1 , S 3 S 1 }, B 3 = {S 2 , S 2 S 3 }, et B 4 = {S 2 , S 3 S 2 }, 2. { Φ(SL(2, Z/pZ); C i ), p ∈ P c i } pour tous 1 ≤ i ≤ 6, où P c i est un ensemble de nom- bres premiers et C 1 = {S 1 , S -1 3 S -1 1 }, C 2 = {S -1 1 , S 1 S 3 }, C 3 = {S -1 1 , S -1 3 S -1 1 }, C 4 = {S 1 , S -1 1 S -1 3 }, C 5 = {S -1 1 , S 3 S 1 }, et C 6 = {S -1 1 , S -1 1 S -1 3 }, 3. { Φ(SL(2, Z/pZ); D i ), p ∈ P d i } pour tous 1 ≤ i ≤ 6, où P d i est un ensemble de nombres premiers et D 1 = {S 2 , S -1 3 S -1 2 }, D 2 = {S -1 2 , S 2 S 3 }, D 3 = {S -1 2 , S -1 3 S -1 2 }, D 4 = {S 2 , S -1 2 S -1 3 }, D 5 = {S -1 2 , S 3 S 2 }, et D 6 = {S -1 2 , S -1 2 S -1 3 }, 4. { Φ(SL(2, Z/pZ); F i ), p ∈ P f i } pour tous 1 ≤ i ≤ 5, où P f i est un ensemble de nombres premiers et F 1 = {S 1 , S 2 1 , S 1 S 3 , (S 1 S 3 ) 2 }, F 2 = {S 1 , S 2 1 , S 1 S 3 , (S 1 S 3 ) 3 }, F 3 = {S 1 , S 2 1 , (S 1 S 3 ) 2 , (S 1 S 3 ) 3 }, F 4 = {S 2 , S 2 2 , S 2 S 3 , (S 2 S 3 ) 2 }, et F 5 = {S 1 , S 2 2 , (S 2 S 3 ) 2 , (S 2 S 3 ) 3 }.
De plus, une nouvelle méthode pour générer une famille régulière infinie de graphe de

P(H l , λ ) = (λ + t) a( r t -1) P(H, λ + t -r).
b. Si r ≤ t, alors

P(H, λ ) = (λ + r) a(1-r t ) P(H l , λ + r -t).
En utilisant les résultats ci-dessus, un lien est présenté dans le chapitre 5 entre le spectre des G-graphes d-réguliers Φ(G, S) et celui de Cay(G, S * ). Plus spécifiquement si |G| = n,

|S| = k, et o(s) = O pour tout s ∈ S. a. Si O ≤ k, alors P( Φ(G, S), λ ) = (λ + O) n( k O -1) P(Cay(G, S * ), λ + O -k). b. Si k ≤ O, alors P(Cay(G, S * ), λ ) = (λ + k) n(1-k O ) P( Φ(G, S), λ + k -O).
Ces relations conduisent à une grande variété de résultats concernant plusieurs problèmes largement étudiés dans la théorie des graphes de

{4 cos 2πi 4m + 2/i = 1, . . . , 4m} {-2[4m]}. 2. Soit G = Z/nZ × Z/nZ et S = {(1, 0), (0, 1)} où n ≥ 2.
Alors les valeurs propres du graphe de Cayley Cay(G, S * ) sont :

{2n -2} {n -2[2n -2]} {-2[n 2 -2n + 1]}. 3. Soit G = Z/nZ×Z/nZ et S = {(1, 0), (0, 1), (1, 1)} où n ≥ 3. Alors les valeurs propres du graphe de Cayley Cay(G, S * ) sont {3n -3} {n -3[3n -3]} {-3[n 2 -3n + 2]}.
{2 cos 2πi n + 1, 2 cos 2πi n -1/i = 1, . . . , n} {-2[ 3n 2 -n]}.
(e, s) (r, sr) (r graphes intégraux [START_REF] Balińska | A Survey on Integral Graphs. Publikacije Elektrotehničkog fakulteta[END_REF]. Le problème de la construction de classes infinies de graphes intégraux est intensivement étudié (voir par exemple [START_REF] Indulal | Some New Integral Graphs[END_REF][START_REF] Wang | Constructing Fifteen Infinite Classes of Nonregular Bipartite Integral Graphs[END_REF][START_REF] Wang | Integral complete multipartite graphs[END_REF]). Récemment, les graphes de Cayley ont été efficacement utilisés pour construire une famille infinie de graphes intégraux (voir par exemple [1] et [START_REF] Minchenko | Quartic integral Cayley graphs[END_REF]).

Dans la littérature, la plupart de ces classes sont construites en appliquant un produit de graphes, soit en utilisant le graphe complet K n ou le graphe bipartite complet K n,n (voir par exemple [START_REF] Indulal | Some New Integral Graphs[END_REF][START_REF] Mohammadian | Some constructions of integral graphs[END_REF]).

Fig. 5 Le graphe intégral K 2,2 △ K 2 avec spectre (5, 1, 1, -1, -1, -1, -1, -3).

Dans la sous-section 5.4. Chapter 1

Preliminaries

Graphs are among the most ubiquitous forms of both natural and man-made structures.

Graph theory has witnessed a huge growth starting from the thirties of the last century. The main reason for this growth is that these objects serve as models to analyze many difficult real-life problems. Another reason is their applicability to many other domains, such as computer science, physics, chemistry, sociology, and psychology. In the natural, life, and social sciences they model relations between species, societies, countries, companies and so on. In computer science, they may represent networks of communication, computational devices, data organization, and so on. On the other hand, we see graph theory has also close connections with many branches of pure and applied mathematics, such as group theory, probability, geometry, and topology. The study of these models leads to the realization of the significant structural characteristics of the relevant graphs. But are there certain nontrivial structural aspects which are dramatically more important? Is it possible to put a certain condition on the expansion of a graph? Or equivalently, is it possible that the graph itself be at the same time sparse and highly connected? Expanders existence was first proved by Pinsker [START_REF] Pinsker | On the complexity of a concentrator[END_REF] without giving an actual construction. These graphs play a key role in many of the above subjects. For instance, since expanders serve as basic building bricks for various types of communication networks, an explicit construction is very desirable.

As the reader can anticipate from their name "expander graphs", the relative high connectivity, or equivalently the consistent degree of expansion 1 , is one of the main principles for their existence. So what we exactly mean by expansion? If we take a look at Cambridge dictionary we find expansion [noun], is the increase of something in size, number, or importance. The formal mathematical definition is completely another story (see e.g. the following two books [START_REF] Krebs | Expander Families and Cayley Graphs: A Beginner's Guide. EBSCO ebook academic collection[END_REF][START_REF] Rogawski | Discrete Groups, Expanding Graphs and Invariant Measures[END_REF] two surveys [START_REF] Hoory | Expander graphs and their applications[END_REF][START_REF] Lubotzky | Expander graphs in pure and applied mathematics[END_REF]). It can be given using at least languages: combinatorial, random walks, algebraic. Combinatorially, this definition can be summarized in one statement, it is a sparse graph that has strong connectivity properties. Literally, this means, it combines the preferable properties of a graph or communication network, which are in some sense contradictory, its sparsity or price, and its connectivity or reliability and speed.

This chapter has been designed to give a general introduction to some of the basic facts needed from the theory of groups, graphs, and hypergraph, in addition to algebraic graph theory. This introduction is given to provide a convenient repository for all readers. We discuss briefly the material we shall require from these theories and in each section we point the reader to the suitable reference(s).

Useful definitions from group theory

In this section, we exhibit standard terminology from the theory of groups. For further prerequisites from this subject, see e.g. [69].

Some general definitions

Group

A group is a set of elements, G, together with the group operation "." that combines any two elements g and g ′ to form another element of G, denoted by g.g ′ or simply gg ′ . Both the set and the and group operation must satisfy the four group axioms:

• Closure: For all g, g ′ in G, then g.g ′ is also in G.

• Associativity: For all g, g ′ and g ′′ in G, g.(g ′ .g ′′ ) = (g.g ′ ).g ′′ • Identity element: There exists an element in G denoted by e, sometimes denoted by 1, such that every g in G, we have g.e = e.g = g.

• Inverse element: For each element g in G, there exists an element g -1 in G, such that

g.g -1 = g -1 .g = e.
A group is generally denoted by (G, .) where "." denotes the group operation. In this thesis, we very often use the underlying set G as a short notation for the group (G, .)

Abelian group

The result of combining elements g and g ′ may be different to that of g ′ with element g. That is, the following statement is not always true.

• Commutativity: For all g, g ′ in G, we have g.g ′ = g ′ .g

An abelian group is a group that satisfies the commutativity axiom. For instance, the group (Z/nZ, +) is an abelian group, while the groups defined in Table 1.1 are all non-abelian.

Order of an element

Throughout this thesis, we are mainly concerned with finite groups, that is, a group with a finite number of elements. The order of the group G, or |G|, is the number of elements in group. 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, where g l represents the application of the group operation "." to l copies of g. Let S = {s 1 , ..., 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 ∈ {1, . . . , k}.

Subgroup

Let (G, .) be a group, a subset H is called a subgroup of G if it also satisfies the four group axioms under the same group operation ".". It must therefore include the identity element of G. The order of any subgroup H of G, or |H|, must be a divisor of |G|.

Generating set of a group

Generating set and cyclic group

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. The elements of the generating set S are called generators of the group G. A cyclic group is a group that is generated by a single generator.

Rank of a group

The rank of group G, denoted by rank(G), is the cardinality of the smallest generating set, that is,

rank(G) = min{|S|; S ⊂ G and ⟨S⟩ = G}.
A generating set S is minimal if its cardinality |S| is equal to the rank of G.

Some operations on sets

Let A and B be subsets of the universal set U.

Action of a group

Group action

The left group action of G on a set X is the function ϕ from G × X to X: (g, x) → g • x, satisfying the following two conditions for all elements x in X:

• Identity: e • x = x, • Compatibility: (g • g ′ ) • x = g • (g ′ • x) for all g, g ′ ∈ G.
In this case, we say that the group G acts on the left of the set X. The right action of a group is defined in a similar way.

The orbit (with respect to the left action) of x ∈ X, denoted by O x , is the set of all elements in X to which x can be moved (to them) by the elements of G. That is, O x = {g • x/g ∈ G}. Note that since y = g • x if and only if x = g -1 • y, then y ∈ O x if and only if x ∈ O y . Consequently, the orbits of action form a partition of X. For every x ∈ X, the stabilizer subgroup of x, denoted by G x , is the set of all elements of G that fix x. That is,

G x = {g ∈ G/g • x = x}.
The action is transitive if X is non-empty set if for each pair of elements x, y ∈ X, there exists an element g ∈ G such that g • x = y. Note that the action is transitive if and only if it has exactly one orbit, that is if there exists an element x ∈ X such that G • x = X. The action is said to be regular, if for all x, y ∈ X, there exists a unique g ∈ G such that g • x = y. Clearly, a regular action is also transitive.

Left and right cosets

Let H be a subgroup of a group G and let g be an element of G. A subset of G of the form Hg = {hg/h in H} is said to be a right coset of H in G. A subset T H of G is said to be a right transversal of H if T H contains exactly one element from each right coset of H in G. In a similar way, we can define left cosets of a group and the left transversal set. Two right cosets of H in G are either identical or disjoint. That is to say, every element of the group G belongs to exactly one right coset, and so the set of right cosets form a partition of the group

G, G = t∈T H
Ht.

The same statement stands for the set of left cosets.

Isomorphism of groups

Isomorphism of groups Given two groups G and H, a morphism from G to H, is a function ϕ : G → H such that ϕ(gh) = ϕ(g)ϕ(h), for every g, h ∈ G. A bijective morphism from G to H, is called an isomorphism. Two groups G and H are said to be isomorphic, if there exists an isomorphism between them. In this case, we write G ≃ H. An isomorphism from G onto itself is called automorphism. The automorphism group, denoted by Aut(G), is the set of all automorphisms of G

The fundamental theorem of finite abelian groups

The fundamental theorem of finite abelian groups [69] states that every finite abelian group of rank k is isomorphic to a direct product of k cyclic groups of prime-power order, that is G ≃ Z/m 1 Z × . . . × Z/m k Z where m 1 , . . . , m k are are powers of prime numbers uniquely determined by the group G.

Group presentation

A common way to define certain groups G is by using group presentation. Let S be a set of generators of the group G, and R a set of relations between these generators. Formally, we say that G has the group presentation ⟨S|R⟩ if it is isomorphic to the group generated by S, subjected to the relations of R. For example, the well-known non-abelian group D 2n , the dihedral group of order 2n, generated by r rotations of 2π/n and reflection s, has the following group presentation,

D 2n = s, r|s 2 = r n = 1, (sr) 2 = 1 .
One of the group presentations of the cyclic group of order n is ⟨a|a n = 1⟩ .

If a group G is finite then it has a finite presentation ⟨S|R⟩ (that is both S and R are both finite). Every group (infinite or finite) has a presentation, and indeed many different presentations. A presentation is usually the most compact way to describe the structure of its corresponding group. That is, group presentation is in general the simplest and most concrete method to define a group. For this reason, we mainly refer to this notation throughout this thesis. Below we present some groups with their corresponding presentations/definitions. These groups are frequently used in Chapters 4 and 5 to construct new infinite families of regular and irregular expander graphs, integral Cayley graphs, and strongly regular Cayley graphs, etc.

Preliminaries Group name/notation Group presentation/definition

The dihedral group D 2n s, r|s

2 = r n = 1, sr = r -1 s The dicyclic group Dic n s, r|r 2n = 1, r n = s 2 , sr = r -1 s The group V 8n s, r|r 2n = s 4 = 1, sr = r -1 s -1 , s -1 r = r -1 s The Coxeter group Cox(m i, j , 1 ≤ i, j ≤ n) r 1 , . . . , r n | (r i r j ) m i, j = 1, m i,i = 1, m i, j ≥ 2 if i ̸ = j
The special linear group

SL m (Z/qZ) (A) m×m = (a i, j ) where a i, j ∈ Z/qZ for all 1 ≤ i, j ≤ m and |A m×m | = 1 The projective special lin- ear group PSL m (Z/qZ) SL m (Z/qZ)/{± I m }
, where I m is the m × m identity matrix Table 1.1 Some groups with their presentations ⟨S|R⟩.

Useful definitions from graph theory

This section has been designed to give a general introduction to some of the basic facts of graph theory, for more details on this subject, see e.g. [START_REF] Lauri | Topics in Graph Automorphisms and Reconstruction[END_REF][START_REF] Bondy | Graph Theory[END_REF]. In this thesis, we consider only non-directed and finite graphs.

Some general definitions

Non-directed and simple graphs

An undirected graph Γ is the triple (V (Γ), E(Γ), ξ Γ ), or (V, E, ξ ) when no ambiguous occurs, where V (Γ) is the set of vertices, E(Γ) is the set of edges, and ξ Γ is an incidence function that associates to each edge e ∈ E(Γ) an unordered pair of vertices u, v ∈ V (Γ). If ξ Γ (e) = {u, v} then we say that the edge e is incident to the vertices u and v and that u and v are adjacent. A loop is an edge with identical endpoints, that is an edge that joins the same vertex. Two or more edges with the same pair of end-points, or vertices, are said to be parallel edges. The multiplicity of an edge between vertices u and v is the number of parallel edges that are incident to both u and v. A graph with neither parallel edges nor loops is called simple graph. That it is to say, if it has neither loops nor edges of multiplicity greater than or equal to 2.

Induced, spanning, and cover sub-graphs Definition 1.2.1. A subgraph Γ ′ of Γ is a graph such that its vertices and edges sets are subsets of those of

Γ. A subgraph Γ ′ is spanning if V (Γ ′ ) = V (Γ). Likewise, a subgraph Γ ′ is said to be induced if the following condition is satisfied, {u, v} ∈ E(Γ ′ ) if and only if {u, v} ∈ E(Γ) for all u, v ∈ V (Γ ′ ). A subgraph Γ ′ is said to be a cover subgraph of Γ if V (Γ ′ ) = V (Γ)
and any two vertices u and v of Γ ′ are adjacent if and only if they are also adjacent in Γ.

Γ 1 Γ 2 Fig. 1.1 The graph Γ 1 is a cover subgraph of Γ 2 .
Remark. It is easy to see that every cover subgraph Γ ′ of Γ is necessarily a spanning subgraph, yet the converse is not true (see graph Γ 1 and Γ 2 in Figure 1.1).

Walk, trail, and path

A walk in a graph is a sequence v 0 , e 1 , v 1 , ..., v l of graph vertices and graph edges (not necessarily distinct), such that v i-1 and v i are the ends of e i for 1 ≤ i ≤ l. A trail is a walk in which all its edges are distinct. A path is a trail in which all its vertices are distinct (except possibly the first and last). A graph is connected if there exists is a path between any two of its vertices.

k-representation of a graph

A graph Γ = (V, E, ξ Γ ) is k-partite if there is a partition of V into k parts such that each part is a independent set. We will write Γ = ( i∈I V i ; E) where I = {1, . . . , k}. A graph is minimum k-partite (k ≥ 1) if it is k-partite and not (k -1)-partite. It is easy to verify that for any graph Γ, there exists k such that Γ is minimum k-partite. If a graph Γ is k-partite, then we will say that (V i ) i∈{1,2,...,k} is a k-representation of Γ and we will call (Γ, (V i ) i∈{1,2,...,k} ) a k-graph.

Some useful graph invariants

Vertex degree, diameter of a graph Definition 1.2.2. Let Γ be a graph with vertex set V. The neighborhood of a vertex u ∈ V denoted by N Γ (u), or N(u) when no ambiguous occurs, is the set of all vertices that are adjacent to u. The degree of a vertex v in a graph Γ, denoted by d Γ (v), or d(u) when no ambiguous occurs, is the number of edges of Γ incident to v where each loop counts as two edges. The maximum and the minimum degree of a graph Γ is denoted by ∆(Γ) and δ (Γ), respectively. A graph Γ is d-regular if d(u) = d for all u ∈ V (Γ). Two vertices u, v ∈ V (Γ) are twins if they have the same neighbors N(u) = N(v) and the same number of edges between them and any fixed neighbor.

Remark. In Chapter 4 and 5, we deal with infinite families of d-regular and regular graphs. The difference between these families is that the first one contains regular graphs of degree d each, while the second is formed of regular graphs but possibly with different degrees.

Definition 1.2.3. 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(Γ) of a graph Γ is defined by:

diam(Γ) = max{d(u, v); u, v ∈ V (Γ)}.

Clique and independent set

An independent set of a graph Γ, sometimes called the stable set, is an induced subgraph of Γ such that no pair of its vertices are adjacent. A maximum independent set of a graph Γ is an independent set with the largest possible size. The independence number of graph Γ, denote by α(Γ), is a cardinal of a maximum independent set in Γ. Literally, this means, α(Γ) = max{|U|;U is an independent set of Γ}.

A clique of graph Γ is an induced subgraph of Γ such any pair of its vertices are adjacent. Note any clique of graph Γ has a spanning complete subgraph. A maximum clique of a graph Γ is a clique with the largest possible size. The clique number of a graph Γ, denoted by ω(Γ), is the size of the maximum clique of Γ. Literally, this means,

ω(Γ) = max{|U|;U is a clique of Γ}.
The chromatic number of a graph Γ denoted by χ(Γ), is equal to the smallest integer k such that Γ is k-partite and not k -1-partite. It is easy to see that ω(Γ) ≤ χ(Γ) and that χ(Γ) ≤ ∆(Γ) + 1. In 1941, Brooks [START_REF] Brooks | On Colouring the Nodes of a Network[END_REF] gives a sharper upper bound, where he proves that the chromatic number χ(Γ) ≤ ∆(Γ), unless the graph Γ is complete or an odd cycle.

Symmetric and semi-symmetric graphs

Definition 1.2.4. Let Γ 1 = (V 1 , E 1 , ξ 1 ) and Γ 2 = (V 2 , E 2 , ξ 2 ) be two graphs, a graph homo- morphism from Γ 1 to Γ 2 is a couple ( f , f # ) where f : V 1 → V 2 and f # : E 1 → E 2 such that if ξ 1 (a) = {u, v} then ξ 2 ( f # (a)) = { f (u), f (v)}. A graph isomorphism is a couple ( f , f # )
where f and f # are bijective. A graph Γ 1 is isomorphic to Γ 2 if there exists an isomorphism between Γ 1 and Γ 2 . In this case, we write Γ ≃ Γ ′ . An automorphism of a graph is a graph isomorphism with itself.

Definition 1.2.5. A graph Γ = (V, E, ξ ) is vertex-transitive if for any v 1 , v 2 ∈ V there exists a graph automorphism (h, h # ) such that h(v 1 ) = v 2 .
Similarly, graph Γ is edge-transitive if for any e 1 , e 2 ∈ E there exists a graph automorphism (h, h # ) such that h # (e 1 ) = e 2 . A symmetric graph is a graph that is both vertex-transitive and edge-transitive. Note that every vertex-transitive graph is also regular, but this is not true for the edge-transitive case. A regular graph that is edge-transitive but not vertex-transitive is semi-symmetric.

Remarkable classes of graphs/operations Hamiltonian and Eulerian graphs

A Hamiltonian path is a path that visits each vertex exactly once. A Hamiltonian cycle is a Hamiltonian path that is a cycle, that is it starts and ends in the same vertex. A graph is Hamiltonian if it contains a Hamiltonian cycle. Similarly an Eulerian trail is a trail that visits every edge exactly once. An Eulerian tour is a trail that is a cycle, that is it passes through every edge exactly once. A graph is Eulerian if it contains an Eulerian tour.

Eulerian graphs were first introduced and discussed in 1736 by the famous Swiss mathematician Leonhard Euler, in an attempt to solve the Seven Bridges Königsberg problem. In the process, a necessary condition is given for the existence of Eulerian graphs, that is the degree of all vertices must be even integers. He conjectured the opposite, that is to say, if the vertex degree set of a connected graph is formed of even integers then the graph is Eulerian. This claim was later proved in 1873 by Carl Hierholzer [START_REF] Biggs | Graph Theory, 1736-1936[END_REF].

Theorem 1.2.6. [Euler and [START_REF] Biggs | Graph Theory, 1736-1936[END_REF]] Let Γ be a nontrivial connected graph. Then Γ has an Euler tour if and only if every vertex is of even degree.

Line graph of graph

The line graph of a simple graph Γ is the graph Γ l such that the vertices are the edges of Γ and e, e ′ ∈ V (Γ l ) are adjacent Γ l if they have a common vertex.

A simple graph Γ is edge-transitive if and only if its line graph Γ l is vertex-transitive. This property is used to generate families of graphs that are vertex-transitive graphs that are not Cayley graphs. More particularly, it was proved [START_REF] Lauri | Topics in Graph Automorphisms and Reconstruction[END_REF] that if Γ is a non-bipartite and edge-transitive graph with least five vertices, and with odd vertex degrees, then Γ l is vertex-transitive and is not a Cayley graph.

Cayley graph

Let G be a group and S be a symmetric subset of G, that is s ∈ S if and only if s -1 ∈ S. The Cayley graph associated to the group G with respect to S, denoted by Cay(G, S), is the graph with vertex set G and two elements x and y of G are adjacent if and only if y = s.x for some s ∈ S. In the following example, we present a short list some well-known Cayley graphs.

Example 1.

1. The complete graph K n ; for any group G such that |G| = n and S = G. 4. The infinite grid on the plane R 2 ; G = Z × Z and S = {(±1, 0), (0, ±1)}.

5. The finite grid on a torus. R 2 ; G = Z/nZ × Z/mZ and S = {(±1, 0), (0, ±1)}.

Many other examples of symmetric Cayley graphs which have in general, as their names indicate, very symmetrical and nice shape can be found in [START_REF] Bray | Cayley type graphs and cubic graphs of large girth[END_REF][START_REF] Godsil | Algebraic Graph Theory[END_REF], where the authors demonstrate the efficiency of Cayley graphs in constructing symmetric graphs. In Figure 1.2, we present two of these graphs, the cubic Cayley graphs Cay(Z/4Z, {1, 2, 3}) and Cay(Z/8Z, {1, 4, 7}).

Complement graph

The complement, also called the inverse, of a graph Γ = (V, E, ξ Γ ) is the graph Γ with the same vertex set V where any two of its distinct vertices u, v of are adjacent if and only if they are not in Γ. Note that if Γ is a simple graph then Γ = Γ.

A maximum independent set of a graph Γ is a maximum clique in the complement graph Γ, and vice-versa. Then we have the equality ω(Γ) = α(Γ). It is easy to see that the automorphism group of a graph Γ is the automorphism group of its complement Γ.

Cartesian product

Let Γ and Γ ′ be two simple graphs with vertex sets V (Γ) and V (Γ ′ ) respectively. The Cartesian product Γ□Γ ′ of Γ and Γ ′ is defined as follows. The vertex set of Γ□Γ ′ is

V (Γ) ×V (Γ ′ ), and two vertices (u, v) and (u ′ , v ′ ) of Γ□Γ ′ are adjacent if either u = u ′ and v is adjacent to v ′ in Γ ′ , or v = v ′ and u is adjacent to u ′ in Γ.
The Cartesian product Γ□Γ ′ of Γ and Γ ′ is formed of V (Γ) vertical copies of the graph Γ ′ and by V (Γ ′ ) horizontal copies of the graph Γ where each horizontal and vertical copy meet at exactly one vertex. Th reader can notice this property from Figure 1.3, where the Cartesian product of the graphs C 3 and P 2 is given. Example 2. The Cartesian product of P 2 and the path graph on n vertices P n is the ladder graph L n or the (2 × n)-grid graph. More generally, the Cartesian product of paths P m and P n is the (m × n)-grid graph. For n ≥ 3, the Cartesian product the cycle C n and K 2 is a polyhedral graph, the n-prism.

Useful definitions from hypergraph theory

In this section, we recall some auxiliary materials related to hypergraph theory which can be thought as a simple generalization to their corresponding ones in graph theory. Many of the above definitions/notations from the theory of graphs are carried verbatimly to that of hypergraphs. For more details on this subject see for example [START_REF] Bretto | Hypergraph Theory: An Introduction[END_REF].

Some general definitions

Uniform hypergraphs

A hypergraph H = (V ; E = (e i ) i∈I ) on a finite set V is a family (e i ) i∈I (I is a finite set of indices) of non-empty subsets of V called hyperedges with,

i∈I e i = V.
A hypergraph is simple if e i = e j implies that i = j that is there are no repeated hyperedges in

H. The degree of vertex u ∈ V denoted by d(u) is the number of hyperedges which contains u. A hypergraph is said to be k-uniform if |e i | = k for all i ∈ I. Note that any graph Γ is 2-uniform hypergraph. A hypergraph is linear if |e i ∩ e j | ≤ 1 for i ̸ = j.

Remarkable classes of graphs Incidence graph of a hypergraph

The incidence graph, also called the Levi graph, of a hypergraph H = (V, E) is a bipartite graph I(H) whose vertex set is the union V E, and two vertices v ∈ V and e ∈ E are adjacent if and only if v ∈ e. Note that for every incidence graph, there is an equivalent hypergraph, and vice-versa.

Line graph, dual, and 2-section of hypergraphs

The line graph of a hypergraph H is the graph H l such that the vertices are the hyperedges of H and two distinct vertices u, v form an edge of H l if the hyperedges standing for u and v have a non-empty intersection. The dual of a hypergraph H = ((v i ) i∈I ; (e i ) i∈I ′ ) is the hypergraph

H * = ((e i ) i∈I ′ ); ((X i ) i∈I )
whose vertices (e i ) i∈I ′ correspond to the hyperedges of H and such that its hyperedges are given by:

(X i ) i∈I = ({e j , v i ∈ e j }) i∈I .
Note that H * * = H, that is the dual of hypergraph is an involution relation.

The 2-section of a hypergraph H is the graph [H] 2 such that its vertices are those of H and two vertices form an edge if and only if they are in the same hyperedge in H. The dual and 2-section of a hypergraph are illustrated in an example shown in Figure 3.

Remark. It is well-known [START_REF] Bretto | Hypergraph Theory: An Introduction[END_REF] that the 2-section of a hypergraph H is isomorphic to the line graph of H * , namely [H] 2 = (H * ) l . This relation (and few others) combined with the special structural properties of G-graphs presented in Chapter 2 pave our way to establish Such a relation between the two "twin" graphs will be the key to compute the spectra of infinite families of Cayley and G-graphs, and to present new classes of strongly regular Cayley graphs, integral Cayley graphs, etc.

Useful definitions from algebraic graph theory

In this section, we shall collect together some of the background material and standard results needed from algebraic graph theory. We discuss briefly the material we shall require from this theory and for more details on this subject, we encouraged the reader to consult [START_REF] Godsil | Algebraic Graph Theory[END_REF][START_REF] Biggs | Algebraic Graph Theory[END_REF][START_REF] Bapat | Graphs and Matrices[END_REF]. Generally speaking, applying algebraic methods to solve graph problems leads to the birth of algebraic graph theory. There are three principal branches of algebraic graph theory:

1. Spectral graph theory. This branch is concerned with the study of graphs in relation with linear algebra. For instance, computing the spectrum of the adjacency/Laplacian matrix of a graph. The aspects of graph spectrum have been effectively used to analysis the synchronizability of networks [START_REF] Biggs | Algebraic Graph Theory[END_REF]. There are many theorems that relate the properties of a graph to that of its spectrum. For instance, a connected graph Γ with diameter diam(Γ) have at least diam(Γ) + 1 distinct eigenvalues (see Proposition 1.4.5, see also [START_REF] Godsil | Algebraic Graph Theory[END_REF][START_REF] Bapat | Graphs and Matrices[END_REF]). Also, Γ is connected if and only if the second smallest Laplacian eigenvalue µ |Γ|-1 , also known as algebraic connectivity of Γ, is not zero.

2. Studying graph using group theory. This branch involves the study of graphs in connection to the theory of groups, in particular, the graph automorphism and the geometric group theory. In general, this study is based on the symmetry of certain families of graphs and the different relationships between these graphs families. For example, symmetric graphs, vertex-transitive/edge-transitive graphs, distance-transitive graphs, distance-regular graphs, and strongly regular graphs. Another connection with the theory of groups, which was first proved by Robert Frucht in 1939, states that any group can be represented as the automorphism group of some connected graph, in particular, a cubic graph [START_REF] Frucht | Herstellung von Graphen mit vorgegebener abstrakter Gruppe[END_REF]. The symmetrical graphs known as Cayley graphs (defined in Section 1.5), represent another connection with the theory of groups. From any given group we can construct many corresponding Cayley graphs. These graphs have many properties that related in a way or another to the structure of the group [START_REF] Biggs | Algebraic Graph Theory[END_REF].

The symmetry properties of graphs are reflected by their spectra, this leads to directly relate this branch of algebraic graph theory to the above one. More specifically, a highly symmetrical graph has few distinct eigenvalues in its spectrum [START_REF] Biggs | Algebraic Graph Theory[END_REF]. For instance, the spectrum of Petersen graph given in Figure 1.

6 is (3, 1, 1, 1, 1, 1, -2, -2, -2, -2)
then it has 3 distinct eigenvalues, which is by Proposition 1.4.5 the minimum possible number. For the case of Cayley graphs, their spectra can be directly related to the structure of the corresponding groups, particularly to their irreducible characters [START_REF] Biggs | Algebraic Graph Theory[END_REF].

3.

Studying some graph invariants. The third and the last area of algebraic graph theory is concerned with studying the algebraic properties of invariants of graphs, in particular, the chromatic polynomial, the Tutte polynomial, and knot invariants. The chromatic polynomial of a graph, for instance, calculates the number of its proper vertex colorings. Most of the work in this branch was motivated by proving the four color theorem. However, there are still several open problems in this direction. For example, characterizing the graphs that have the same chromatic polynomial, and determining the polynomials that are chromatic.

Some general definitions

Let Γ be a graph with vertex set {v i , 1 ≤ i ≤ n} and edge set {e j , 1 ≤ j ≤ m}.

Adjacency matrix of a graph Γ

The adjacency matrix of Γ, denoted by A(Γ), is the n × n matrix whose (i, j) is the number of edges joining vertex v i and v j , each loop counting as two edges. Note that when dealing with simple graphs then the diagonal entries of A(Γ) are all equal to 0, and the off-diagonal entries are either 1 or 0. Clearly, if Γ is a d-regular graph, then d is the largest eigenvalue of A(Γ) with the eigenvector (1, . . . , 1) t .

Incidence matrix of a graph Γ

The incidence matrix of a simple graph Γ, denoted by M(Γ), is the n × m matrix whose (i, j) is 1 if the vertex v i and the edge e j are incident and 0 otherwise. Laplacian matrix of a graph Γ Let D(Γ) be the diagonal matrix of vertex degrees, that is (i, i) entry of D(G) is equal to d(v i ) for all 1 ≤ i ≤ n, and 0 otherwise. The Laplacian matrix of a graph Γ denoted by L(Γ) is given by L(Γ) = D(Γ) -A(Γ). It is easy for the reader to see that L(Γ) is n × n matrix whose each row and column sum is zero. Thus 0 is an eigenvalues with eigenvector (1, . . . , 1) t . Spectrum and Laplacian spectrum of a graph Γ

The characteristic polynomial of graph Γ in the variable λ denoted by P(Γ, λ ) is the determinant of the matrix A(Γ)-λ I n . The eigenvalues of the graph Γ, say λ n ≤ . . . ≤ λ 2 ≤ λ 1 , are the roots of the characteristic polynomial P(Γ, λ ), these eigenvalues form the spectrum of Γ or σ (Γ). The number of times an eigenvalue λ occurs as a root of the characteristic equation is called the multiplicity of the λ . We denote by λ [α] the multiplicity of eigenvalue

λ is α ∈ N + . The spectral radius of the graph Γ is defined to be ρ(Γ) = max{|λ 1 |, |λ n |}.
The spectral gap of graph Γ is the difference λ 1 -λ 2 , as we will see in Chapter 3 this quantity measures the "expansion quality" of the graph. The Laplacian spectrum of the graph Γ denoted by µ n = 0 ≤ µ n-1 . . . ≤ µ 1 , is defined in an analogical way. The adjacency and the Laplacian matrix of Γ are,

A(Γ) =         2 1 0 0 1 1 0 1 0 1 0 1 0 1 1 0 0 1 0 1 1 1 1 1 0         and L(Γ) = D(Γ) -A(Γ) =         2 -1 0 0 -1 -1 3 -1 0 -1 0 -1 3 -1 -1 0 0 -1 2 -1 -1 -1 -1 -1 4         .
The spectrum and the Laplacian spectrum are (3.416, 1.55, -0.201, -1.196, -1.569) and (6.125, 3, 2.637, 1.238, 1) respectively.

Remark. In Chapter 5, for our purposes we generalize the concept of the adjacency matrix, the incidence matrix, the characteristic polynomial, and the spectrum to the hypergraph case. The reason that stands behind presenting such generalization, is to benefit as much as possible from Theorem 5.1.2 and the notation of principal clique hypergraph. This leads us to a more comprehensive results regrading the spectral properties of the two "step brothers" the Cayley graph and the G-graph.

Few useful results

The following results can be found in [START_REF] Bapat | Graphs and Matrices[END_REF] and [START_REF] Godsil | Algebraic Graph Theory[END_REF].

Theorem 1.4.1. [START_REF] Bapat | Graphs and Matrices[END_REF] The eigenvalues of the complete graph K n , the complete bipartite graph K p,q , the cycle C n and the path P n on n vertices are respectively,

i. {n -1} {-1}[n -1],
ii.

√ pq {- √ pq} {0}[p + q -2],
iii. {2 cos 2πi n /i = 1, . . . n}, iv. {2 cos 2πi n+1 /i = 1, . . . n}. The following result follows directly from Corollary 3.6 in [START_REF] Mourad | Generalization of some results concerning eigenvalues of a certain class of matrices and some applications[END_REF].

Proposition 1.4.2. [START_REF] Godsil | Algebraic Graph Theory[END_REF] The eigenvalues of the complete partite graph K n,n,n are

{2n} {-n[2]} {0[3n -3]}.
Theorem 1.4.3. [7] Let Γ and Γ ′ be graphs with m and n vertices, respectively. If λ 1 , . . . , λ m and µ 1 , . . . , µ n are the eigenvalues of Γ and Γ ′ , respectively, then the eigenvalues of Γ□Γ ′ are given by λ i + µ j , where i = 1, . . . , m, j = 1, . . . , n. Proposition 1.4.4. [START_REF] Godsil | Algebraic Graph Theory[END_REF] Let A and B be n × n matrices such that AB = BA. Then A and B are simultaneously diagonalizable, i.e. there exists an invertible matrix P made out of the common eigenvectors of A and B, such that P -1 AP and P -1 BP are a diagonal matrix.

Remark. By Proposition 1.4.4 we deduce that if matrices A and B commutes then the eigenvalues of the matrix (A + B) is equal to the sum of eigenvalues of matrices A and B with respect to some order. Similarly, the eigenvalues of matrix (AB) is the multiplication of the eigenvalues of matrices A and B with respect to some order. Note that the above proposition can be generalized for any set of k ≥ 3 matrices that pairwise commute. Proposition 1.4.5. [START_REF] Bapat | Graphs and Matrices[END_REF] Let Γ be a connected graph with t distinct eigenvalues, then t > diam(Γ).

Cayley graphs: properties and limitations

The relation between the theory of graphs and that of groups is arguably the most studied and fruitful area in algebraic graph theory. It has attracted considerable attention for more than one century. This quest had led later to the birth of many notable results in graph theory (see for example [START_REF] Godsil | Algebraic Graph Theory[END_REF][START_REF] Bapat | Graphs and Matrices[END_REF]). The first connection between the two theories was made in 1878 by the means of Cayley graph [START_REF] Cayley | The theory of groups: graphical representations[END_REF], named after the famous British mathematician Arthur Cayley (1821-1895), as a way to construct a pictorial representation of finite groups [START_REF] Cayley | On the theory of groups[END_REF].

In the original definition of Cayley graph, the subset S of G can be either symmetric or non-symmetric set. If S is non-symmetric subset of G, then the corresponding Cayley graph will be a directed graph, where there exists an arc from y to x if y = s.x for some s ∈ S. In this thesis, because we are primarily concerned with constructing and studying expanders which are always undirected graphs, we will stick with the previously stated definition of Cayley graphs and so S will always be a symmetric subset of the group G. Before we review together some limitations of Cayley graphs, we need the following result.

The Cayley graph Cay(G, S) is connected if and only if G = ⟨S⟩.

Each vertex x of Cay(G, S) can be mapped to any other vertex y through the right product of it by x -1 y which is an automorphism since

tt ′ ∈ E(Cay(G, S)) ⇔ t ′ = st, s ∈ S ⇔ t ′ x -1 y = stx -1 y.
Thus, any Cayley graph is vertex transitive, but the opposite does not always hold. For instance, the Petersen graph given in Figure 1.6 below is vertex transitive but not a Cayley graph. However, the majority of the small vertex-transitive graphs, that is to say, the graphs with at most 26 vertices, are indeed Cayley graphs (see [START_REF] Mckay | The transitive graphs with at most 26 vertices[END_REF]). In [START_REF] Mckay | Vertex-transitive graphs which are not Cayley graphs[END_REF], the authors present a number of graph classes that are vertex transitive and not Cayley. The main reason that makes Cayley graphs so desirable is that they have strong regular properties, which make them suitable for many applications in the design of interconnection networks, parallel computing, cryptography and many others (see for example [START_REF] Cooperman | New methods for using Cayley graphs in interconnection networks[END_REF][START_REF] Cooperman | Applications of Cayley graphs[END_REF][START_REF] Dekker | Network Robustness and Graph Topology[END_REF]) Nonetheless, Cayley graphs still have some limitations:

1. Cayley graphs are always vertex-transitive, they can be edge-transitive but this does not always hold. For instance, the Cayley graph Cay(Z/7Z, {±2, ±1}) in Figure 1.7 is not edge-transitive. In other words, Cayley graphs can never be semi-symmetric. ), when the generating set S is defined as the group G where |G| = n, then the corresponding Cayley graph Cay(G, S) will be the complete graph K n and thus, in this case, we can not have any information about the special features of the underlying group. Moreover, the corresponding Cayley graphs of two isomorphic groups are also isomorphic, yet the converse does not always hold.

In Chapter 2, we briefly exhibit some notation of G-graphs, first introduced by Bretto and Faisant in 2005 ( [START_REF] Bretto | Another way for associating a graph to a group[END_REF]), as a new method to associate a graph with a group. The vertices of such a graph are the right cosets of certain cyclic groups. Nonetheless, unlike Cayley graphs, we join two cosets if their intersection is non-empty. The main advantage of using this concept is that they can overcome many of the above listed limitations of Cayley graphs. For instance, the definition of G-graphs is more adaptable than that of Cayley graphs. In addition, such graphs can be regular or irregular, in particular, semi-regular graphs.

G-graphs can be symmetric or semi-symmetric, they also reveal key information about the properties of their underlying group. As we mentioned earlier, the Cayley graph Cay(G, G) is the complete graph K |G| for any group G. Very often, this is not the case for G-graphs, this means that the group structure in this case is more reflected by the graph. Also, unlike Cayley graphs, two Abelian groups are isomorphic if and only if their canonical G-graphs are also isomorphic (see [START_REF] Bretto | Symmetric and Semisymmetric Graphs Construction Using G-graphs[END_REF]).

G-graphs have many nice other properties such as regularity, transitivity, connectivity, and many others. Furthermore, the great correspondence between the theories of Cayley and G-graphs makes these graphs more interesting for approaching many related problems to the theory of Cayley graphs from a new perspective. For instance, G-graphs can be used to construct new classes of Hamiltonian Cayley graphs and in fact any Cayley graph can be constructed from a G-graph (see [START_REF] Bretto | G-graphs: A new representation of groups[END_REF][START_REF] Bretto | New graphs related to (p,6) and (p,8)-cages[END_REF]), the two graphs can be considered as half brothers for the same mother the group theory! Because of their nice properties, and because Cayley graphs are the core for almost all expander graphs constructions, it is natural to pose the following question which is the first problem we deal with in this thesis, Since Cayley graph are effectively used to construct many classes of expander graphs. Can we use G-graphs to accomplish the same task?

The answer to this question is part of the tale of this thesis! Chapter 2

G-graphs: A new representation of groups

This chapter essentially deals with the theory of G-graphs. At first, we start by giving its different definitions and notation. In section 2.2, various examples and applications of Ggraphs are presented. The reader must not be tricked by the modest word "examples" stated in this section title. Some of these examples and many others had led to several remarkable results in recent years. Like introducing new classes of Hamiltonian Cayley graphs and completing Foster list of cubic symmetric graphs started in 1934 (see subsection 2.2.2). In section 2.3, we collect together some useful properties from the theory of G-graphs. In section 2.4, we present new results regarding the principal cliques, the regularity, and the simplicity of G-graphs. Many of these results will later play a key role in our construction.

Definitions, some notations and more

In [START_REF] Bretto | Another way for associating a graph to a group[END_REF], G-graphs were first introduced as a new tool to associate a graph with a group. Since then, several other definitions are presented with minor variations in the produced objects. In the original definition, the vertices of the G-graph are the cycles of the left s-translation on the group G are of the form (x, sx, ..., s o(s)-1 x) for every s that belongs to the generating set S, and with p-edge between any two vertices that shares p elements. Note here that each vertex (s)x has o(s) loops. In [START_REF] Bretto | Cayley graphs and G-graphs: Some applications[END_REF][START_REF] Bretto | G-graphs: A new representation of groups[END_REF][START_REF] Bretto | Symmetric and Semisymmetric Graphs Construction Using G-graphs[END_REF], G-graphs are defined in the same way but without loops. In [START_REF] Bauer | Paths and circuits in G-graphs[END_REF] and then in [START_REF] Tanasescu | Incidence Graphs of Bipartite G-Graphs[END_REF], G-graphs are defined to be intersection graphs, so they are simple graphs, of the cosets of ⟨s⟩ in G for every s ∈ S. In [START_REF] Ellison | G-graphs Characterisation and Incidence Graphs[END_REF], G-graphs are defined as above without loops, but with a labeling or coloring the edges. Also, the authors allow the repetition of the elements of the generating set, that it is to say S is considered as a multiset. This leads to the duplication of the levels of the G-graphs that corresponds to the repeated elements of S, and in such case the vertices of these levels are twins.

In this paragraph, we present three slightly different definitions of G-graphs with and without loops, that produce simple graphs or multigraphs. In these cases, we allow the repetition of the generating elements. Also, for solely technical reasons we include in our definition the labeling of the edges (that will be needed in certain cases for example the proof of Theorem 4.3.3).

Throughout this thesis, we mainly focus on the G-graph Φ(G, S) that do not have loops and with edge labeling.The main reason that stands behind our choice is that we are primarily concerned with constructing expander graphs, and when dealing with their most remarkable invariable "the expansion ratio" the loops can be dropped. Still, the other two "versions" of G-graphs, the simple G-graphs or with loops, are used in certain cases to obtain simplified results of certain theorems. For instance, to construct expander family of simple graphs (see Corollaries 4.3.5 and 4.5.8 in Chapter 4 ), or for their own interest.

Definition 1: G-graphs with edge labeling Definition 2.1.1. Let G be a finite group and let S = {s 1 , . . . , s k } be a nonempty multiset of G. We define the G-graph Φ(G, S) in the following way:

1. The vertex set of Φ(G, S) is V = s∈S V s where V s = {(s)x, x ∈ T ⟨s⟩ }
where T ⟨s⟩ is a right transversal for the subgroup ⟨s⟩ .

2. For each (s)x, (t)y ∈ V , there exists edge between (s)x and (t)y labeled g for each g ∈ ⟨s⟩ x ∩ ⟨t⟩ y, such an edge will be denoted by ({(s)x, (t)y}, g). If card(⟨s⟩ x ∩ ⟨t⟩ y) = p, p ≥ 1, then there exists p labeled edges between (s)x and (t)y, or {(s)x, (t)y} is a multiedge with multiplicity p.

Remark. Note that since S is a multiset, then the repetition of an element s ∈ S is allowed.

If the multiset S contains p occurrences of s, then the G-graph Φ(G, S) has p copies of the same level V s . The vertices of these levels are twin vertices since they have the same number of edges between them and any other vertex of their neighbors. For solely formal reasons, in order for the collection of vertices V to be a set instead of multiset it maybe necessary to distinguish between these vertices in the following way for all if s i = s j ∈ S, then let s i (x) = (s i (x), i) and s j (y) = (s j (x), j). However, in order not to overburden the reader with many notations, we will just allow V to be a multiset.

Remark. Note that the cosets of ⟨s⟩ form a partition of G, then (V s ) s∈S is a |S|-representation of Φ(G, S). Note also that card(⟨s⟩ x ∩ ⟨s⟩ x) = o(s), then every vertex (s)x of Φ(G, S) has o(s) loops. In the following definition, G-graphs are introduced as graphs without loops and with labeling.

Definition 2: G-graphs without loops Definition 2.1.2. We denote by Φ(G, S) the graph Φ(G, S) with edge labeling but without loops. The graph Φ(G, S) is the simple graph underlying Φ(G, S), that is, two distinct vertices (s)x and (t)y in V ( Φ(G, S)) are connected by a single edge if ⟨s⟩ x ∩ ⟨t⟩ y is non-empty.

Levels and principal cliques

If S = {s 1 , ..., s k }, then the level of any s i , denoted V s i or simply V i when no ambiguous occurs, is the independent set of Φ(G, S) which comprises all the vertices of the form (s i )x where x ∈ G. Note that each level V s contains |G| o(s) vertices, therefore we have the following relation:

|V ( Φ(G, S))| = |G| ∑ s∈S 1 o(s) .
The principal clique 1 Remark. It is easy to see that V (C x ) ∩V (V s i ) = (s i )x. That is, the vertex set of any principal cliques C x and level V s i share exactly one element, the vertex (s i )x. A nice observation here is that each maximum independent or independent set of G-graphs (which is a level of the G-graph) and every largest complete induced subgraph (which is a principal clique of the G-graph) have one and only one common vertex. 2Remark. The notations of the levels and the principal cliques pave our way in Section 2.4 to approach some problems concerning G-graphs from a new perspective. For instance, like their simplicity and regularity (see for example Corollary 2.4.7). Because of the nice and simple structure that these two notation depicts for any G-graph, maybe later they can give us insightful gaze concerning certain graph invariants like the crossing number, the chromatic index, the vertex and the edge connectivity.

Particular examples and some applications

In this section, to clarify the idea of G-graphs to the reader we first present some of their examples taking into account their various definitions. In Subsection 2.2.2, we briefly exhibit some applications of G-graphs in several areas of graph theory. V s 1 = {{(0, 0), (1, 0), . . . , (p -1, 0)}, . . . , {(0, q -1), (1, q -1), . . . , (p -1, q -1)}}, V s 2 = {{(0, 0), (0, 1), . . . , (0, q -1)}, . . . , {(p -1, 0), (p -1, 1), . . . , (p -1, q -1)}}.

Particular examples

Thus each vertex u ∈ V s 1 is connected to every v ∈ V s 2 , hence Φ(G, S) is isomorphic to K p,q .

Example 8. Let G = Z/pZ and S the multiset that contains q times the element 1. Then, the G-graph Φ(G, S) contains q vertices each connected by p edges to any other vertex.

A short list of G-graphs

Many common graphs are G-graphs. Here is a short list of well-known graphs that are also G-graphs. The corresponding groups and generating set of each graph is indicated.

Some applications

Many essential properties are can be extracted from G-graphs, they are |S|-partite where S is the generating set, they have high regular properties. Moreover, these graphs reveal key aspects about their underlying groups, their automorphism groups are not trivial. The class of G-graphs is quite wide, almost every familiar graph is indeed a G-graph. This class of graphs includes many well-known graphs, like the two famous semi-symmetric graphs the Ljubljana and the Gray graphs (see Figure 2.4), many generalized Petersen graphs. It also includes the cube, hypercube, octahedral, the Heawood, the cuboctahedral, the Pappus, and the Möbius-Kantor graphs, and many others. Since the algorithm for constructing G-graphs is simple [START_REF] Bretto | G-graphs: A new representation of groups[END_REF], they are used in a highly effective way to generate new classes of symmetric and semi-symmetric graphs [START_REF] Bretto | Symmetric and Semisymmetric Graphs Construction Using G-graphs[END_REF]. Thanks to G-graphs, the Foster list of cubic symmetric graphs started in 1934 is completed [START_REF] Bretto | G-graphs: An efficient tool for constructing symmetric and semisymmetric graphs[END_REF]. Also, G-graphs are used to construct the first list of cubic semi-symmetric graphs which are extremely difficult to produce. Likewise, using G-graphs the first algorithm to generate, until a certain size, almost all the quartic (of degree 4) and quintic (of degree 5) symmetric and semi-symmetric graphs is given [START_REF] Bretto | Symmetric and Semisymmetric Graphs Construction Using G-graphs[END_REF].

Moreover, G-graphs are used to characterize new classes of Hamiltonian Cayley graphs [START_REF] Bretto | Cayley graphs and G-graphs: Some applications[END_REF], and to improve some upper bounds in the cage graphs problem [START_REF] Bretto | New graphs related to (p,6) and (p,8)-cages[END_REF]. In particular, a sharper upper bounds than Sauer bounds for (p, 6)-cage and (p, 8)-cage problems, that is 2p 2 for (p, 6)-cage problem instead of the Sauer bound 4(p -1) 3 , and 2p 3 for (p, 8)-cage problem instead of the Sauer bound 4(p -1) 5 [START_REF] Bretto | New graphs related to (p,6) and (p,8)-cages[END_REF]. Recently in [START_REF] Culus | About some robustness and complexity properties of G-graphs networks[END_REF], 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.

G-graphs: Some structural properties and more

In this section, we first collect some useful properties from the theory of G-graphs. We then present some of these results new proofs which are in some cases simpler than the original proofs. First, we start by the following lemma which can be found in [START_REF] Bauer | Paths and circuits in G-graphs[END_REF].

Lemma 2.3.1. [9] Let Φ(G, S) be a G-graph with S = {s 1 , ..., s k } a generating set of G. If {(s i )x, (s j )y} ∈ E( Φ(G, S)), then | ⟨s i ⟩ x ∩ s j y| = | ⟨s i ⟩ ∩ s j |.
As a direct result of the previous lemma, we obtain the following.

Corollary 2.3.2. Let Φ(G, S) be a G-graph with S = {s 1 , ..., s k }. Then Φ(G, S) is simple if and only if ⟨s i ⟩ ∩ s j = {e} for all i, j ∈ {1, . . . , k} with i ̸ = j.

Propositions 2.3.3, 2.3.4, and 2.3.5 can be found for example in [START_REF] Bretto | G-graphs: A new representation of groups[END_REF]. Here we provide a new simpler proofs to these results.

Proposition 2.3.3. Let Φ(G, S) be a G-graph with S = {s 1 , ..., s k }, then Φ (G, S) is a mini- mum k-partite.
Proof. It is sufficient to prove that the chromatic number χ( Φ(G, S)) of Φ(G, S) is equal to k. On the first hand, we have k independent levels, that are {V s \s ∈ S}, then χ( Φ(G, S)) ≤ k. On the other hand, that are {C x \x ∈ G}, then χ( Φ(G, S)) ≥ k. The result follows directly.

Proposition 2.3.4. Let Φ(G, S) = (V : s∈S V s , E, ξ ) be a G-graph such that|G| = n and |S| = k. Then, i. d(v) = o(s)(k -1) for all v ∈ V s , ii. ∑ v∈V s d(v) = n(k -1) for all s ∈ S, iii. |E( Φ(G, S))| = nk(k -1) 2 .
Proof. The vertices of the levels of Φ(G, S) form a partition of G, then between any two different levels there are |G| = n edges, so that

|E( Φ(G, S))| = n k 2 or |E( Φ(G, S))| = nk(k -1) 2 , ∑ v∈V d(v) = 2|E( Φ(G, S))| = nk(k -1).
Note from Definition 2.1.2 we know that the sum of the vertices degree of levels V s and V s ′ are equal for all s, s ′ ∈ S, that is ∑

u∈V s d(u) = ∑ v∈V s ′ d(u), then ∑ v∈V s d(v) = ∑ v∈V d(v) k = n(k -1) for all s ∈ S.
Now since all the vertices in the same level have equal degrees, then

d(v) = | ∑ v∈V s d(v)| |V s | = o(s)(k -1) for all v ∈ V s .
By the same analogy followed in the proof of Proposition 2.3.4, we obtain the following result for the G-graph with loops Φ(G, S). Proposition 2.3.5. Let Φ(G, S) = (V : s∈S V s , E, ξ ) be a G-graph such that|G| = n and

|S| = k. Then, i. d(v) = o(s)(k + 1) for all v ∈ V s , ii. ∑ v∈V s d(v) = n(k + 1) for all s ∈ S, iii. |EΦ(G, S))| = nk(k + 1) 2 .
Remark. As a consequence of Theorem Remark. The given result in the previous proposition reflects the resemblance between certain properties of Cayley and G-graphs. Here, the necessary and sufficient conditions for connectedness for both the G-graph Φ(G, S) and the Cayley graph Cay(G, S) are exactly the same (see also Proposition 1.5.1). In Chapter 5, we give a new proof for Proposition 2.3.6 which is simpler than the one given [START_REF] Bretto | G-graphs: A new representation of groups[END_REF].

Proposition 2.3.7. [START_REF] Bretto | Symmetric and Semisymmetric Graphs Construction Using G-graphs[END_REF] Let h be an isomorphism between the groups (G 1 , S 1 ) and (G 2 , S 2 ), then there exists an isomorphism φ (h) between the G-graphs Φ(G 1 , S 1 ) and Φ(G 2 , S 2 ).

For the special case of abelian groups, we have the following theorem.

Theorem 2.3.8. [START_REF] Bretto | Symmetric and Semisymmetric Graphs Construction Using G-graphs[END_REF] Let G 1 and G 2 be two abelian groups. These the two groups G 1 and G 2 are isomorphic if and only if the G-graphs Φ(G 1 , G 1 ) and Φ(G 2 , G 2 ) are isomorphic.

Remark. As we have seen in Chapter 1, Cayley graphs can not reveal almost any information about their underlying groups. The result presented in Theorem 2.3.8 demonstrates the effectiveness of G-graphs regarding this issue. Many other results concerning the relation between the theories of groups and G-graphs can be found for example in [START_REF] Bretto | G-graphs: A new representation of groups[END_REF][START_REF] Bretto | Symmetric and Semisymmetric Graphs Construction Using G-graphs[END_REF][START_REF] Tanasescu | Incidence Graphs of Bipartite G-Graphs[END_REF].

For instance, a result in [START_REF] Bretto | Symmetric and Semisymmetric Graphs Construction Using G-graphs[END_REF] deals with finding a necessary condition to recognize if the underlying group of the G-graph is cyclic. Note that Theorem 2.3.8 and Proposition 2.3.7 are also valid for the G-graph Φ(G, S).

G-graphs: Some key features that can be extracted from the principal cliques

In this section, we present new results regarding certain structural properties of G-graphs.

In particular, we establish some relations between the simplicity of the G-graph and the number of edges emanated from any principal clique (see Theorem 2.4. Definition 2.4.4. Let V 1 ,V 2 be any two subsets of V ( Φ(G, S)). We denote by E(V 1 ,V 2 ) the set of all edges between V 1 and V 2 . Now for x ∈ G, we define E x to be the number of all edges between the principal clique C x and the rest of the graph, that is

E x = |E V (C x ),V (C x ) |.
Theorem 2.4.5. Let Φ(G, S) be a G-graph with S = {s 1 , . . . , s k }. Then for all x ∈ G, we have

E x = k ∑ i=1 (k -1)o(s i ) -∑ s i ∈S ∑ s j ∈S\{s i } | ⟨s i ⟩ ∩ s j |.
If Φ(G, S) is simple, then

E x = (k -1)( k ∑ i=1 o(s i ) -k).
Moreover, if Φ(G, S) is a regular simple graph, then

E x = k(k -1)(O -1).
Proof. The principal clique C x contains exactly one vertex from each level. By Proposition

2.3.4, d(v) = (k -1)o(s i ) for all v ∈ V s i , so that the sum of the vertex degrees of C x is k ∑ i=1 (k -1)o(s i ),
∑ s i ∈S ∑ s j ∈S\{s i } | ⟨s i ⟩ ∩ s j | = 2 k 2 .

Introduction

Expander graphs are sparse graphs that have strong connectivity properties. Expanders have attracted the attention of many mathematicians and computer scientists for more than four decades, huge amounts of research have been dedicated to them (see for example [START_REF] Hoory | Expander graphs and their applications[END_REF][START_REF] Krebs | Expander Families and Cayley Graphs: A Beginner's Guide. EBSCO ebook academic collection[END_REF][START_REF] Lubotzky | Expander graphs in pure and applied mathematics[END_REF][START_REF] Rogawski | Discrete Groups, Expanding Graphs and Invariant Measures[END_REF]). Generally speaking, to measure the quality of a graph as a communication network, three main aspects are preferable. The first one is its cost, the sparer the graph the better. The other two are its reliability and speed, these two properties reveal themselves in the theory of graphs as the diameter and the edge connectivity of graph. In other words, the higher the edge connectivity and the smaller the diameter of a graph the more reliable and the faster the network will be. As we shall see in Section 3.2, the last two graph invariants are combined in one quantity, the expansion ratio, which literally measures the degree of expansion or the "expansion quality", and in an indirect way the connectivity of the graph. In few words, an expander graph is a graph that combines all these three "desirable" aspects, which are in some sense contradictory, of a communication network.

Another reason that makes expanders so popular is that they can be viewed from different angles; for instance they can be defined using at least three languages: combinatorial, random walks, algebraic ones (see Section 3.2). This leads to fascinating connections between different subjects in the theory of graphs on the one hand and between computer science and pure mathematics on the other.

Expanders have found extensive applications in computer science, in constructing of algorithms, error correcting codes, random walks, and sorting networks (see Section 3.3). Although expanders exist in great abundance (see for example the Expander Mixing Lemma in [START_REF] Hoory | Expander graphs and their applications[END_REF] see also [START_REF] Pinsker | On the complexity of a concentrator[END_REF]), yet their explicit construction, which is very desirable for application, is in general hard task. Most constructions use deep algebraic and combinatorial techniques, mainly through the Cayley graphs and the Zig-Zag product (see section 3.3, see also [START_REF] Krebs | Expander Families and Cayley Graphs: A Beginner's Guide. EBSCO ebook academic collection[END_REF][START_REF] Rogawski | Discrete Groups, Expanding Graphs and Invariant Measures[END_REF]).

Our chief purpose in this thesis is to present a new method to construct expander graphs, mainly by using G-graphs. Since expanders stand in no one stem of graph theory, this leads to new results on the spectra, integral graphs, and many others. In this conquest, we aim to explicitly construct new families of expander graphs using different approaches.

The huge amount of published research on the theory of expanders can leave the reader easily confused by their various definitions, notations, and properties (see for example the remark after Example 10). This chapter aims to collect and exhibit in a simplified way all the needed results for our work from this theory. Some new notations are presented, others are "terminologically" modified in order not to be confused with the new ones. Also, since we are dealing with G-graphs which can be irregular, some simple generalizations of these results to the irregular case are necessary. For more information on the subject of expanders and their applications, we encourage the reader to review the following two books [START_REF] Krebs | Expander Families and Cayley Graphs: A Beginner's Guide. EBSCO ebook academic collection[END_REF][START_REF] Rogawski | Discrete Groups, Expanding Graphs and Invariant Measures[END_REF] and the two surveys [START_REF] Hoory | Expander graphs and their applications[END_REF][START_REF] Lubotzky | Expander graphs in pure and applied mathematics[END_REF]. In Section 3.2, the combinatorial and algebraic definitions of expanders are given. In Sections 3.3 and 3.4, we give a quick review for some construction and application of expanders. The motivation that stands behind their construction is revealed, and our analysis hopefully helps the reader to distinguish the techniques presented in this thesis for constructing expanders to with other ones. In Section 3.5, the relations between the expansion ratio and certain graph invariants are presented; these invariants are the main tool for most constructions of expanders. Some of these results will play a crucial role in Chapter 4.

Definitions

Our main goal in this thesis is to explicitly construct expander graphs, which are enormous graphs that have good "connectivity" and "expansion" properties with the smallest possible number of edges. To do so, we limit ourselves with bounded degree graphs. In a very large bounded degree graph, edges are very sparse.

As mentioned earlier, expander graphs can be defined using many different ways: combinatorial/geometry, random walks, algebraically and so on. In this section, we revise the combinatorial and algebraic point of view to expanders. Combinatorially, expanders are sparse graphs with high connectivity. Algebraically, they are a sequence of graphs where their spectral gap is uniformly bounded away from zero. As we will see later in Section 3.5, all these "very distinct" definitions, that comes from various different areas of mathematics, are not surprisingly equivalent in a way or another, as the quote says "All roads lead to Rome!", which is expander in our case.

First, we will shall start by giving the definition of expansion ratio h(Γ) of a graph Γ. This quantity measures how quickly information can "expand" or flow through the graph or the network. Expander families, given in Definition 3.2.4, are certain sequences of bounded degree graphs so that the expansion ratio is uniformly bounded away from zero. Several examples are given to clarify the idea. Note that in Section 3.5 another equivalent algebraic definition of expanders is presented.

Expansion ratio and expander family Definition 3.2.1. Let Γ = (V, E, ξ Γ ) be a graph with |V | ≥ 2 and V ′ be a subset of V . The edge boundary of V ′ in Γ denoted by ∂V ′ (Γ) (or simply ∂V ′ when no ambiguity occurs) is defined as follows:

∂V ′ (Γ) = {α ∈ E; ξ Γ (α) ∈ V ′ ×V ′ }.
In other words, this is the set of edges emanating from the set V ′ to its complement. Definition 3.2.2. Let Γ = (V, E, ξ Γ ) be a graph, the rate of expansion or expansion ratio of Γ is defined as follows:

h(Γ) = min |∂V ′ | |V ′ | ; / 0 ̸ = V ′ ⊂ V and |V ′ | ≤ |V | 2 .
Example 10. Let C n be the cycle graph on n vertices.In order to compute its expansion ratio, note that the fraction

|∂V ′ | |V ′ | is minimum when |V ′ | is maximum and |∂V ′ | is minimum. That
occurs if the vertices of V ′ are "bunched" or "grouped" together; in other words, there is no vertices between V \V ′ and V ′ , and if V ′ is as large as possible, that is, if

|V ′ | = n 2 or |V ′ | = n -1 2
depending on the parity of n. Then,

h(C n ) =      4 n , if n is even, 4 n -1 , if n is odd.
Remarks.

1. The expansion ratio goes by many other names, for example, it is sometimes called the expansion constant, the isoperimetric constant, the edge expansion constant, the conductance, the Cheeger number, or the Cheeger constant. Even they all refer to the same definition and use the same symbol h(Γ), there is still no "common terminology" for it. C'est la mathématique! 2. Note that for a graph Γ and

V ′ ⊂ V (Γ) where |V ′ | ≤ V (Γ) 2 , we have h(Γ)|V ′ | ≤ |∂V ′ |.
Then, as h(Γ) increases, then the edge connectivity of the graph Γ will also increase, since every set of vertices with size less than half the size of V (Γ) will have more neighbors compared to its size. In other words, we are avoiding the "bottleneck situation" as much as possible, where a set of vertices have relatively to its size, few edges to its complement.

3. Let V ′ be a subset of the vertex set V (Γ), note that the set of edges from V ′ to its complement is the same one in the opposite direction, that is

∂V ′ = ∂ (Γ\V ′ ). Hence, in Definition 3.2.2,
there is no point of including the vertex sets

V ′ when |V ′ | ≥ |V (Γ)| 2 . Definition 3.2.3. For ε ∈ R * + , a graph Γ is said to be an ε-expander if ε ≤ h(Γ).
Definition 3.2.4. If a family of graphs {Γ i = (V i , E i , ξ i ), i ∈ N + } satisfies the following three conditions:

i. |V i | → ∞ as i → ∞,
ii. There exists r ∈ N + such that ∆(Γ i ) ≤ r for all i ∈ N + . That is {Γ i , i ∈ N + } is a sequence of bounded degree graphs,

iii. There exists ε ∈ R * + such that Γ i is an ε-expander for all i ∈ N + , then this family is called an expander family and an element of this family is an expander graph.

As we will see in Section 3.3, constructing an infinite family of expander graphs is in general extremely complicated task. The goal of the following examples is to clarify the idea without overwhelming the reader with complicated issues. For this reason, we restrict ourselves with two negative results, the family of cycles {C n , n ∈ N + } and the family of complete graph {K n , n ∈ N + }.

Example 11. By Example 10, we have

h(C n ) ≤ 4 n -1 , then h(C n ) → 0 as n → ∞. Therefore, the family of cycles {(C n ), n ∈ N + } is not expander family.
Example 12. Let K n be the complete simple graph on n vertices. Let V ′ be a subset of the vertices set of K n , or

V = V (K n ), then |∂V ′ | |V ′ | = (|V | -|V ′ |)|V ′ | |V ′ | = |V | -|V ′ |.
Thus,

h(K n ) =    n + 1 2 , if n is odd, n 2 , if n is even. Then h(K n ) → ∞ as n → ∞.
This is logical since every vertex is connected to every other vertex. However, {K n , n ∈ N + } is not expander family since ∆(K n ) → ∞ as n → ∞. That means, even though K n have very high connectivity that makes it a super/optimally fast as a communication network, it is still "super/optimally expensive" since its density is maximal. An expander family is formed of sparse well connected graphs, in other words it combines the two "favorable" aspects of a communications network in a paradoxical way: price and speed, or "sparse" and "high edge connectivity" in the language of graph theory.

Construction

The existence of expanders follows easily by random considerations. In fact, if we choose at random a sequence of d-regular graphs, it is almost certain to be an expander family (see [START_REF] Lubotzky | Expander graphs in pure and applied mathematics[END_REF]). Nevertheless, explicit construction of expanders, which is for several reasons very favorable and desirable for many applications, is a much more difficult task. The situation of expander graphs is similar to that of transcendental numbers. If we take at random a real number, it is almost certain to be a transcendental, yet there is no general framework to prove that this specific number is transcendental. Up-till now, Cayley graphs and Zig-zag product are the two main chief tools for constructing a family of expander graphs. The main advantage of using Cayley graph 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) (using Kazhdan constant and the second largest eigenvalue, see [START_REF] Hoory | Expander graphs and their applications[END_REF][START_REF] Lubotzky | Expander graphs in pure and applied mathematics[END_REF]). 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. For instance, it was proved that no Cayley graph family on the abelian groups or the dihedral group is an expander (see [START_REF] Hoory | Expander graphs and their applications[END_REF][START_REF] Lubotzky | Expander graphs in pure and applied mathematics[END_REF]).

In 1973, the first explicit construction of expander family of Cayley graphs was given by Margulis [START_REF] Margulis | Explicit constructions of expanders[END_REF]. Surprisingly, Cayley graphs remain for about three decades and despite the huge efforts the only principal method for constructing expanders. In 2002, Reingold et al (see [START_REF] Reingold | Entropy waves, the zig-zag graph product, and new constant-degree expanders[END_REF]) presents a straightforward combinatorial method for constructing an expander family the "zig-zag product". The zig-zag product of two graphs Γ and Γ ′ produce a larger graph whose second largest eigenvalue λ 2 is controlled by the spectrum of Γ and Γ ′ , and thus its expansion ratio (see Theorem 3.5.6). In fact, the expansion ratio of the above zig-zag product is slightly smaller than that of Γ ′ .

In this section, we exhibit some previous expander construction. One of the main purposes of this thesis is to study expanders and to approach the problem of their construction from various points of views. However we just want the reader to be aware of the huge effort and the difficulty of the old methods for constructing expanders, so that comparing them with the new technique for constructing expander presented in this thesis are easily distinguishable. Discussing these expander constructions in details is far beyond the scope of this thesis. Instead, we will point out to some references for each one of the following constructions. Furthermore, we will mainly focus on the positive answers for the above question, despite that there is a huge amount of research that deals with proving that a family of Cayley graphs on a certain group is not an expander (see for example [START_REF] Hoory | Expander graphs and their applications[END_REF][START_REF] Rogawski | Discrete Groups, Expanding Graphs and Invariant Measures[END_REF][START_REF] Rosenhouse | Isoperimetric numbers of cayley graphs arising from generalized dihedral groups[END_REF]).

1. In the early 1970's, Pinsker [START_REF] Pinsker | On the complexity of a concentrator[END_REF] was the first to prove expander existence in great abundance. More particularly, he essentially used a certain probabilistic argument to prove that for any d ≥ 3 there exists an expander family of d-regular graphs. Nonetheless, Pinsker's proof dealt with the existence and not with the construction of such family. Later in 1973, Margulis used some advanced algebraic techniques, mainly through Kazhdan constant, to give the first explicit construction of an expander family.

2. Although the first explicit expander family constructed by Margulis was given in terms of action of the group SL 2 (Z/Z p ), it is in fact derived from Cayley graphs on the group SL 3 (Z/Z p ), where the generating set S consists of all elementary matrices with 1's on the diagonal entries and exactly one ±1 at a non-diagonal entry. Since |S| = 12, then resulting family of Cayley graphs is 12-regular. Margulis then obtain the result using the theorem of Kazhdan and the fact that any quotient family of an expander family is also an expander (see Proposition 2.20 in [START_REF] Krebs | Expander Families and Cayley Graphs: A Beginner's Guide. EBSCO ebook academic collection[END_REF]).

3. Margulis did not provide any specific bounds on the expansion ratio of his graphs. In 1981, Gabber and Galil [START_REF] Gabber | Explicit constructions of linear-sized superconcentrators[END_REF], and later in 1987, Jimbo and Maruoka [START_REF] Jimbo | Expanders obtained from affine transformations[END_REF] used Fourier analysis to give an upper bound to a certain expander family they present. Note that since the "expansion quality" of the graph Γ is controlled by the lower bound of h(Γ), then we are more interested in the techniques for estimating such bound rather than the upper bound.

4. A similar result was proved by Lubotzky [START_REF] Rogawski | Discrete Groups, Expanding Graphs and Invariant Measures[END_REF] for the Cayley graphs on SL 2 (Z/pZ) where using certain properties (see Selberg's theorem in [START_REF] Lubotzky | Expander graphs in pure and applied mathematics[END_REF]) he was able to give a lower bound for the spectral gap for the presented family.

5. Surprisingly, for more than a quarter of century Cayley graph remains the exclusive main tool for constructing expander graphs. In the beginning of the twenty-first century, Reingold et al [START_REF] Reingold | Entropy waves, the zig-zag graph product, and new constant-degree expanders[END_REF] in a breakthrough article introduce the Zig-Zag product a combinatorial tool for constructing such graphs. The Zig-Zag product of Γ 1 and Γ 2 , where Γ 1 and Γ 1 are m, d-regular graphs on n, m vertices, respectively, is a d 2 -regular graph on mn vertices, the resulting graph has slightly smaller expansion ratio than that of Γ 1 and Γ 2 . In other words, the Zig-Zag product produces directly from two expanders a larger expander with a little bit weaker "expansion quality".

General speaking the Zig-Zag product of two graphs is not necessary a Cayley graph. Nonetheless, if the underlying groups and the generating sets satisfy specific conditions, then actually the Zig-Zag product of these two Cayley graphs is justly a Cayley graph.

As we have already mentioned, the Zig-Zag product of two expander is also an expander.

Combining the above two ideas the following question arises naturally, "Can we explicitly construct an expander family of Cayley graphs using the Zig-Zag product?"

Many articles deal with the above question and show that it is indeed possible. Meshulam et al [START_REF] Meshulam | Expanders from Symmetric Codes[END_REF], constructs a family of expanders with a nonconstant degree but the degree grows slowly. Another construction using the same technique is given by Rozenman et al [START_REF] Rozenman | A New Family of Cayley Expanders[END_REF], where they present a d-regular expander family of constant degree Cayley multigraphs.

6. Since the explicit construction of an expander family is a pretty hard task, many mathematicians have restricted themselves with the problem of finding which groups that can yield an expander family of Cayley graphs and which can not (see the question at the beginning of this section). The advantage of such approach is it at first divides the "big cake" problem into "small pieces" and this gives us the privilege to have some partial answers in specific cases and makes the task easier (yet it is still pretty hard in general!). In fact, the special underlying properties of certain groups, (like the abelian or dihedral groups see point 10 below, see also Corollary 3.5.4), can give us supplementary information about the properties of their corresponding Cayley graph. Kassabov [START_REF] Kassabov | Kazhdan Constants for SL n (Z)[END_REF], proves that the group SL n (Z/p m Z) where n > 2, m > 0 and p prime number can yield an expander family of Cayley graphs1 . Lubotzky [START_REF] Lubotzky | Expander graphs in pure and applied mathematics[END_REF] proves a similar result for the group SL 2 (Z/p m Z). Using some original combinatorial arguments Kassabov [START_REF] Kassabov | Symmetric groups and expander graphs[END_REF] proved that the alternating and symmetric groups A n and S n can also yield an expander family of Cayley graphs.

7. In a major breakthrough, Kassabov et al [START_REF] Kassabov | Finite simple groups as expanders[END_REF] proved that all the simple groups, except the Suzuki groups, can indeed yield an expander family of Cayley graphs. More precisely, they show that there exist integer d < 1000 and 0 < 10 -10 < ε ∈ R such that every simple nonabelian finite group G, which is not a Suzuki group, has a generating set S of cardinality d such that the Cayley graph Cay(G, S) is ε-expander.

8. Using group theory, algebraic graph theory, and combinatorial techniques, Bourgain and Gamburd [START_REF] Bourgain | Uniform expansion bounds for Cayley graphs of SL 2 (F p )[END_REF] construct certain expander family of Cayley graphs on the group SL 2 (Z/pZ) where p is a prime number. In [START_REF] Bourgain | Expansion and random walks in SL d (Z/p n Z): I[END_REF], a more comprehensive expander family on group SL 2 (Z/p n Z) is constructed. 9. In this briefing, we just focus on few positive answers to the question presented at the beginning of the section. It worth mentioning here that the majority of the approaches fails to attain the desired result for certain groups (see Example 14 and the remark after it).

Applications

From the different definitions of expanders and their constructions, it is easy for the reader to predicate that they possess a wide variety of applications in both pure and applied mathematics. In number theory, they are used to give a generalization of the affine sieve method. Many applications to geometry are presented in [START_REF] Lubotzky | Expander graphs in pure and applied mathematics[END_REF] to the hyperbolic 3-manifolds. In the previous section, the connection between application of group theory in the theory of expanders is clarified where we see that most constructed expander families are indeed Cayley graphs. Surprisingly, expanders also appear in the proof of many results in group theory. In [START_REF] Hoory | Expander graphs and their applications[END_REF], some of these proofs beside several other applications to combinatorial group theory are presented.

In this thesis, we primarily aim to approach the problem of constructing expanders from different combinatorial and algebraic angles. The study of its application is far beyond the scope of our study. Their applications have really expanded to several areas in mathematics and computer science! 2 Next, we will just point out to few of their applications to computer 2 Even Hoory et al, the authors of the prize winning survey "Expander graphs and their application" [START_REF] Hoory | Expander graphs and their applications[END_REF], state in its introduction: "Expansion is closely related to the convergence rates of Markov Chains, . . . The list of such interesting and fruitful connections goes on and on with so many applications we will not even be able to mention . . . In the past four decades, a great amount of research has been done on these topics, resulting in a wide-ranging body of knowledge. In this survey, we could not hope to cover even a fraction of it." science and random walks through quoting certain paragraphs from some references, so that the reader will be familiar with their importance and existence and also we take the opportunity here to clarify the important role that our technique that depends on G-graphs can later play. For furthermore information about this subject we highly encourage the reader to review the following two surveys and book ( [START_REF] Hoory | Expander graphs and their applications[END_REF][START_REF] Lubotzky | Expander graphs in pure and applied mathematics[END_REF][START_REF] Rogawski | Discrete Groups, Expanding Graphs and Invariant Measures[END_REF]).

Computer science

In the following, we quote a paragraph from the introduction of M. Klawe's article [START_REF] Klawe | Limitations on explicit constructions of expanding graphs[END_REF]. The reader can have a quick insightful gaze concerning the various applications of expanders to computer science as she describes few of their importance in constructing certain networks:

"The study of the complexity of graphs with special connectivity properties originated in switching theory, motivated by problems of designing networksable to connect many disjoint sets of users, while only using a small number of switches. An example of this type of graph is a superconcentrator, which is an acyclic directed graph with n inputs and n outputs such that given any pair of subsets A and B of the same size, of inputs and outputs respectively, there exists a set of disjoint paths joining the inputs in A to the outputs in B. Some other examples are concentrators, nonblocking connectors and generalized connectors (see [START_REF] Chung | On Concentrators, Superconcentrators, Generalizers, and Nonblocking Networks[END_REF][START_REF] Pippenger | Generalized Connectors[END_REF]). There is a large body of work searching for optimal constructions of these graphs ( [START_REF] Pinsker | On the complexity of a concentrator[END_REF][START_REF] Bassalygo | Complexity of an optimum nonblocking switching network without reconnections[END_REF][START_REF] Cantor | On non-blocking switching networks[END_REF][START_REF] Ofman | A universal automaton[END_REF][START_REF] Masson | Generalized multi-stage connection networks[END_REF][START_REF] Pippenger | Generalized Connectors[END_REF][START_REF] Pippenger | [END_REF]). So far all optimal explicit constructions depend on expanding graphs of some sort."

Random walks

In describing the connection between the two theories of random walks and expanders, we refer the reader to the following paragraph from the introduction of Chapter 3 of [START_REF] Hoory | Expander graphs and their applications[END_REF]. In the same chapter, the author gives a review on the application of expanders to random walks where he mostly focuses on the randomness-efficient error reduction procedure for randomized algorithms, and the strong hardness of approximation result for the maximum clique problem.

" A key property of the random walk on an expander graph is that it converges rapidly to its limit distribution. This fact has numerous important consequences at which we can only hint. In many theoretical and practical computational problems in science and engineering it is necessary to draw samples from some distribution F on a (usually finite but huge) set V . Such problems are often solved by so-called "Monte-Carlo" algorithms. One considers a graph G on vertex set V so that the limit distribution of the random walk on G is F. A clever choice of G can guarantee that (i) it is feasible to efficiently simulate this random walk and (ii) the distribution induced on V by the walk converges rapidly to F."

The magnificent three invariants

Generally speaking, it is not practical to compute the expansion ratio h(Γ) of a graph Γ. The reason that makes this task hard is that it requires counting E(V ′ ,V ′ ) over all vertex sets V ′

where

|V ′ | ≤ |V (Γ)| 2 vertices
, and the number of such vertex sets grows exponentially as |V (Γ)| increases. Thus, to prove that certain family {Γ i , i ∈ N} is an expander family some indirect methods are required to show that h(Γ i ) ≥ ε > 0 for all i ∈ N. To achieve this goal, mathematicians have been using some graph invariants that are generally easier to deal with than the expansion ratio h(Γ) [START_REF] Krebs | Expander Families and Cayley Graphs: A Beginner's Guide. EBSCO ebook academic collection[END_REF][START_REF] Rogawski | Discrete Groups, Expanding Graphs and Invariant Measures[END_REF]. In this section, we present three keys of such graph invariants: the diameter, the second largest eigenvalue, and the Kazhdan constant. Moreover, we briefly describe their benefits and their different relations with the expansion ratio.

Diameter of expander family

The corresponding relations between the diameter of a graph and its expansion ratio have been one of the main interests for the researchers that are willing to check if a certain family is an expander (see [START_REF] Krebs | Expander Families and Cayley Graphs: A Beginner's Guide. EBSCO ebook academic collection[END_REF][START_REF] Lubotzky | Expander graphs in pure and applied mathematics[END_REF]). When we think of graphs with "relatively high" connectivity like expanders, we expect them to have "relatively small" diameter. In this section, we exhibit the different properties and relations between these two graph invariants. The following proposition can be found in [START_REF] Krebs | Expander Families and Cayley Graphs: A Beginner's Guide. EBSCO ebook academic collection[END_REF].

Proposition 3.5.1.

[50] Let Γ be a d-regular graph, then

log d |V (Γ)| ≤ diam(Γ).
By the previous proposition we see that for a family of d-regular graphs {Γ i , i ∈ N} the diameter diam(Γ i ) grows at least logarithmically as function of |V (Γ i )|. That is, the logarithmic growth of the diameter is the best possible scenario. Remark. If a family of d-regular graphs {Γ i , i ∈ N} is an expander family, then h(Γ i ) + 1 ≥ ε + 1 > 1 for all i ∈ N. By Proposition 3.5.2, we deduce that the diameter of an expander family of d-regular graphs grows logarithmically as a function of the number of vertices, which is optimal in this direction. However, the inverse is not necessarily true. In [START_REF] Krebs | Expander Families and Cayley Graphs: A Beginner's Guide. EBSCO ebook academic collection[END_REF], the author presents examples where the families of graphs are not expander but have logarithmic diameter growth. Using this fact, the diameter has been one of the chief tools to prove that a certain family of graphs (mostly Cayley graphs) is not an expander.

Proposition 3.5.3. [START_REF] Krebs | Expander Families and Cayley Graphs: A Beginner's Guide. EBSCO ebook academic collection[END_REF] No family of Cayley graphs {Cay(G i , S i ), for all i ∈ N} on finite abelian groups, where |S i | = d for all i ∈ N, has a logarithmic diameter.

The following corollary follows directly from Proposition 3.5.2 and the previous proposition. Proof. Consider v ∈ V (Γ) and define B l (v) = {u ∈ V (Γ); d(v, u) ≤ l}. We show by induction that |B l (v)| ≤ 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)| ≤ (r -1)|B l-1 (v)| + |B l-1 (v)| = r|B l-1 (v)| ≤ rr l-1 = r l . If l = diam(Γ), then B l (v) = V (Γ) and therefore |V (Γ)| ≤ r diam(Γ) .

Cheeger inequalities Regular case

As we already mentioned, computing directly the expansion ratio is in general very hard task. Most expander constructions rely heavily on certain algebraic techniques to compute the spectrum of the graph family, as eigenvalues in many cases are easier to deal with than the expansion ratio. For this reason, Cheeger's inequality presented below could have the honor to be renamed as the "mother" or "the fundamental theorem" of all expander constructions. Theorem 3.5.6. [START_REF] Chung | Spectral Graph Theory[END_REF]Cheeger's inequality Let Γ be a d-regular graph, then

d -λ 2 2 ≤ h(Γ) ≤ (d + λ 2 )(d -λ 2 ).
Remarks.

1. Cheeger's inequality was first proved by Dodziuk [START_REF] Dodziuk | Difference equations, isoperimetric inequality and transience of certain random walks[END_REF], and then independently by Alon and Milman [2]. A more general version of the above theorem is needed since we are dealing with G-graphs which can be regular and irregular graphs. A similar result is presented below for the irregular case.

2. Note that the spectral gap d -λ 2 appears on both sides of Cheeger's inequality in Theorem 3.5.6. In other words, the smaller the second eigenvalue λ 2 is, the larger h(Γ) is, and the better the graph is as an "expander graph".

3. By Cheeger's inequality, we deduce that the combinatorial and algebraic definition of expanders presented in the previous section for a d-regular graph family are indeed equivalent. That is to say, a family of d-regular

graphs {Γ i , i ∈ N + } such that |Γ i | → ∞ as i → ∞ is an expander if and only if its corresponding spectral gap d -λ 2 (Γ i
) is uniformly bounded away from zero. Using the result presented in Theorem 3.5.8, a similar definition for the irregular case can also be given. i → 0 as i → ∞, and thus h(C i ) → 0 as i → ∞. Therefore, the spectral gap of the graph family {C i , i ∈ N + } is not uniformly bounded away from zero. This gives an alternative proof to Example 11 that the family of cycles is not expander.

Irregular case

The possible reason for the broad use of Cheeger's inequality (Theorem 3.5.6) is that most of the constructed expander families are indeed Cayley graphs which are always regular. One of our main ingredients for constructing expanders is the G-graph which could be regular or irregular (see Proposition 2.4.1). Obviously, in the irregular case, the above inequality would not be useful. Below we present a generalized version of Cheeger's inequality for the irregular case. Definition 3.5.7. Let Γ = (V, E, ξ Γ ) be a graph, the Cheeger constant υ Γ of Γ is defined as follows:

υ Γ = min X⊂V |∂ X| min ∑ x∈X d(x), ∑ y∈X d(y)
case of regular graph, is greater than or equal to certain positive constant ε. In other words, the sequence {µ |Γ i |-1 , i ∈ N + } is uniformly bounded away from 0.

Remark. From Cheeger inequalities presented in Subsection 3.5.2, it is clear that the two definitions of expander families, the algebraic and the combinatorial ones, are equivalent.

Kazhdan constant

In previous subsections, we have seen that expansion constant, the diameter, and the spectral gap of d-regular graph are closely related. Obviously, computing the spectral gap of d-regular graph Γ is still a hard task since usually this requires computing the spectrum of its adjacency matrix, or A(Γ), which is |V (Γ)| × |V (Γ)| matrix. This task becomes much harder as |V (Γ)| tends to infinity. One of the chief methods to overcome this problem -, which is in certain sense the only,-and to prove that certain family of Cayley graphs is an expander family is by using the Kazhdan constant, which is closely related to the spectral gap of a Cayley graph.

For each Cayley graph Cay(G, S) we associate a Kazhdan constant κ(G, S) defined in [START_REF] Krebs | Expander Families and Cayley Graphs: A Beginner's Guide. EBSCO ebook academic collection[END_REF][START_REF] Rogawski | Discrete Groups, Expanding Graphs and Invariant Measures[END_REF] . A family of Cayley graphs {Cay(G i , S i ), i ∈ N} such that |S i | = d for all i ∈ N is an expander family if and only if the corresponding Kazhdan constants, or {κ(G i , S i ), i ∈ N} are uniformly bounded away from zero, that is κ(G i , S i ) ≥ ε > 0 for all i ∈ N. Although, explicit computing Kazhdan constant is still a quite difficult task and it has been done only for rare cases of finite groups, there are some inequalities that relate it to other graph invariants, like the expansion ratio h(Γ) and the second eigenvalue λ 2 , and that provides some techniques for computing its lower bound [START_REF] Hoory | Expander graphs and their applications[END_REF][START_REF] Lubotzky | Expander graphs in pure and applied mathematics[END_REF].

Summary

Since it is quite difficult to compute the expansion ratio of the graph several other graph invariants are used either to prove that certain graph family is an expander family, typically by using the Kazhdan constant of certain Cayley graph or the second largest eigenvalue, or not by generally showing that the limit of the diameter of the graphs tends to zero . That is, each one of the above three graph invariants measures in a way or another the expansion quality of a Cayley graph. Note that these graph invariants repeat themselves throughout this thesis and in certain cases, some minor variations or equivalent invariant are used (see Theorems 3.5.6 and 3.5.8).

In Table 3.1, we list these three graph invariants, their notation, and the place where they are defined. In Table 3.2, we present the different relation between the three graph invariants.

Graph invariant Notation Definition

Expansion ratio h(Γ) Definition 3.2.2 Second largest eigenvalue λ 2 (Γ) Section 1.4 Diameter diam(Γ) Definition 1.2.3 Table 3.1 The three graph invariants.

λ 2 (Γ) or µ n-1 diam(Γ) h(Γ) or υ Γ d-λ 2 2 ≤ h(Γ) ≤ (d + λ 2 )(d -λ 2 ) 1 2 µ n-1 ≤ υ Γ ≤ √ 2µ n-1 diam(Γ) ≤ 2 log 1+ h(Γ) d log(|Γ|) λ 2 (Γ) - diam(Γ) ≤ ⌈log(|Γ| -1)\ log(d\|λ 2 (Γ)|)⌉ Table 3.2
The different relations between the three invariants.

Chapter 4 Expander G-graphs

Introduction

In this chapter, we present a new method for constructing G-graph expanders. Since G-graphs, unlike Cayley graphs, can be regular or irregular. This eventually leads to many infinite expander families of irregular graphs, which are to our knowledge where of the first ones. Moreover, as Tables 4.1, 4.2, and 4.3 describes, the construct families have many advantages over their predecessors the Cayley ones, for instance, they are in general sparser and easier to construct.

Our construction is based on a relation between some known expander families of Cayley graphs and certain expander families of G-graphs. This chapter is organized as follows. In Section 4.2, we give some necessary definitions and notations regarding the relation between the theories of G-graphs and Cayley graphs on the first hand and that of expanders on the second one. In Section 4.3, we present one of the main results of this chapter which is Theorem 4.3.3 that establishes a connection between some known expander families of Cayley graphs and certain expander families of G-graphs. Like the Cayley case, we prove that abelian groups can not yield an expander family of G-graphs. In the last two sections, we consider certain expander families of Cayley graphs and use them to construct several expander families of irregular graphs. Most important results of this chapter are presented in article [3].

Cay-expanders and G-expanders

In this section, we will present a virtual interpretation of the definition of expander for the G-graph and the Cayley graph cases. In other words, we combine the definitions/structural properties of Cayley and G-graphs, presented in Chapters 1 and 2, with those of an expander family. Some useful remarks/examples are given to clarify the idea. Definitions 4.2.1. Let {G i , i ∈ N + } be a family of finite groups. We say that {G i , i ∈ N + } is a G-expander family, if for every i ∈ N + there exists a generating subset S i of G i such that

{ Φ(G i , S i ), i ∈ N + } is an expander family. More precisely, {G i , i ∈ N + } is a G-expander family if the following 3 conditions are satisfied: i. |V ( Φ(G i , S i ))| = |G i | ∑ s∈S i 1 o(s) → ∞ as i → ∞. Since ∆( Φ(G i , S i )) ≤ r ∈ N + for all i ∈ N + , then this is equivalent to saying that |G i | → ∞ as i → ∞.
ii. There exists a positive integer r such that ∆( Φ(G i , S i )) ≤ r for all i ∈ N + which by Proposition 2.3.4 means that for every (s

)x ∈ V s we have d((s)x) = (|S i | -1)o(s) ≤ ∆( Φ(G i , S i )) ≤ r ∈ N + for all i ∈ N + .
This in turn means that there exists r 1 , r 2 ∈ N + such that 2 ≤ |S i | ≤ r 1 and o(s) ≤ r 2 for all s ∈ S i and for all i ∈ N + . (Note that 2 ≤ |S i | since otherwise, Φ(G i , S i ) will be a disconnected graph so that h( Φ(G i , S i )) = 0, and so it is clear that max{r 1 , r 2 } ≤ r).

iii. There exists an

ε ∈ R * + such that ε ≤ h( Φ(G i , S i )) for all i ∈ N + .
On the other hand, we say that {G i , i ∈ N + } is a ❈❛②-expander family, if for every i ∈ N + there exists a symmetric generating subset S i of G i with

|S i | = d such that {Cay(G i , S i ), i ∈ N + } is an expander family. More explicitly, {G i , i ∈ N + } is a ❈❛②-expander family if
the following 2 conditions are satisfied:

i. |V (Cay(G i , S i ))| = |G i | → ∞ as i → ∞,
ii. There exists an ε ∈ R * + such that ε ≤ h(Cay(G i , S i )) for all i ∈ N + .

Remark. Many similar terminologies are used for an ❈❛②-expander family of groups, for instance, some authors prefer to say a group family that "yields" an expander graph others "made into" or "leads to". The core idea here is the same, a family of groups that corresponds to a certain expander family of Cayley graphs. To make it easier for the reader to distinguish between the different possible outcomes, the two notations ❈❛②-expander and the G-expander are given. Although, it seems that there is a great connection between the two twins the Cayley graphs and the G-graphs (see Theorem 5.1.2), and that a group family is ❈❛②-expander if and only if it is G-expander (see Conjecture 5.1.3), this may not always stand. In other words, a group family is ❈❛②-expander and not G-expander could be found, and vice-versa. Proof. Let (s p )x, (s q )y ∈ V ( Φ(G, S)), where x, y ∈ G and 1 ≤ p, q ≤ |S| = k. Since G = ⟨S⟩ is an abelian group, then

x = s i 1 1 . . . s i p p . . . s i q q . . . s i k k y = s i 1 1 . . . s i p p . . . . . . s i k k s i q q y
, where 1 ≤ i l ≤ o(s l ) for all 1 ≤ l ≤ k. It is easy to see that (s p )x is adjacent to (s 1 )s i 2 2 . . . s i k k y which is in turn connected to (s 2 )s i 3 3 . . . s i k k y and so on up to (s k )s i q q y which is connected to (s q )y. Thus d((s p )x, (s q )y) ≤ |S|. Proof. Suppose that {G i , i ∈ N + } is a family of finite abelian groups and that { Φ(G i , S i ), i ∈ N + } is an expander family. Then there exists r ∈ N + such that |S i | ≤ r for all i ∈ N + . But then by the preceding lemma diam( Φ(G i , S i )) ≤ |S i | ≤ r ∈ N + , and that contradicts Proposition 3.5.5.

Cayley and G-graph expanders: Construction and comparison

In this subsection, we prove the main results of this chapter which allows to directly construct expander families of G-graphs from certain Cayley graphs ones. As consequence, some other results follow easily. Certain remarks/tables are added to compare the various "expansion qualities" of both families, the old and the new G-graph ones. Before we prove Theorem 4.3.3, we need first the following notation of the set S * .

Notation. Let G be a finite group and S ⊆ G. Denote S * = s∈S ⟨s⟩ \ {e} that is if S = {s 1 , . . . , s k }, then

S * = {s 1 , . . . , s o(s 1 )-1 1 , . . . , s k , . . . , s o(s k )-1 k }.
∈ N + . Then |V ( Φ(G n , S n ))| → ∞ as n → ∞ and ∆( Φ(G n , S n )) < r 2 for all n ∈ N + . Suppose that H ⊂ V ( Φ(G n , S n )) where 0 < |H| < |V ( Φ(G n , S n ))| 2
, and

H i = H ∩ V i for every 1 ≤ i ≤ |S n |. Then, H = i H i . Let W = i (s)x∈H i ⟨s⟩ x ⊂ G. Since |H| ≤ |V ( Φ(G n , S n ))| 2 , we have |W | ≤ |G| 2
. Now let

X i = {(s i )x ∈ H i | ⟨s i ⟩ x ⊂ W }, then |X i | ≤ |W |.
Denote by X and Y the following sets of vertices,

X = |S n | i=1 X i , and Y = H \ X.
If (s)x ∈ Y , there is an edge between (s)x and a vertex in

V ( Φ(G n , S n ))\H. Hence |∂ H| ≥ |Y |.
In Cay(G n , S * n ), we have |∂W | ≥ ε|W |. Let f : ∂W → ∂ H, {x, y} → ({(s i )x, (s j )y}, y), where x ∈ W , y / ∈ W , i and j are chosen so that xy -1 ∈ ⟨s i ⟩ and y / ∈ (s)x∈H j ⟨s⟩ x. (There may be several possible choices for i and j.)

If f (x, y) = f (x ′ , y ′ ), then xx ′ -1 ∈ ⟨s i ⟩ and y = y ′ . So for all α ∈ ∂ H, | f -1 (α)| ≤ O max (S n ).
Hence,

|∂ H| ≥ |∂W | O max (S n ) ≥ ε|W | O max (S n ) ≥ ε max i |X i | O max (S n ) ≥ ε|X| O max (S n )|S n | Using |∂ H| ≥ |Y | and |H| = |X| + |Y |, we obtain |∂ H| ≥ 1 2 min{ ε O max (S n )|S n | , 1}|H| ≥ 1 2 min{ ε r 2 , 1}|H|
The following two corollaries are direct consequences of the preceding theorem. Proof. By Theorem 4.3.3, { Φ(G i , S i ), i ∈ N + } is an expander family. By Definition 4.2.1, there exists r ∈ N + such that o(s j ) ≤ r, for every s j ∈ S i . Then | s j 1 ∩ s j 2 | ≤ r for all s j 1 ,

s j 2 ∈ S i . Thus h( Φ(G i , S i )) r ≤ h( Φ(G i , S i )).
Remarks.

Order

i ±1 ), hence 0 < ε ≤ h(Cay(G i , S i )) ≤ h(Cay(G i , S i ∪ x i ±1 )).
A direct consequence of the preceding proposition is the following.

Corollary 4.4.2. Let {Cay(G i , S i ), i ∈ N + } be an expander family. If there exists l ∈ N + such that |S * i | ≤ l for all i ∈ N + , then {Cay(G i , S * i ), i ∈ N + } is also an expander family.

The following theorem was proved in 2010 by Breuillard and Gamburd in [START_REF] Breuillard | Strong Uniform Expansion in SL(2, p)[END_REF].

Theorem 4.4.3. [24] There exists ε ∈ R * + and an infinite set of prime numbers P ′ such that for every p ∈ P ′ and every generating set {x, y} of SL(2, Z/pZ), the family Cay(SL(2, Z/pZ); {x ±1 , y ±1 }) is an ε-expander.

Let S 1 = 0 -1 1 0 , S 2 = 0 1 -1 0 and S 3 = 1 1 0 1 . It is well-known that SL(2, Z/pZ) = ⟨S 1 , S 3 ⟩ = ⟨S 2 , S 3 ⟩.
The order of S 1 , S 2 is 4, while the order of S 3 in Z/pZ is p. Thus SL(2, Z/pZ) is also generated by one of the following sets:

{S 1 , S 1 S 3 }, {S 1 , S 3 S 1 }, {S 2 , S 2 S 3 }, {S 2 , S 3 S 2 },
where

S 1 S 3 = 0 -1 1 1 , S 3 S 1 = 1 -1 1 0 , S 2 S 3 = 0 1 -1 -1 , and
S 3 S 2 = -1 1 -1 0 .
Note that the orders of S 1 S 3 , S 3 S 1 , S 2 S 3 , and S 3 S 2 are respectively 6, 6, 3 and 3. With the above notations, we have the following conclusion.

Some more expander families

In

Construction of new families of Cayley graphs from the old ones by edge rearrangement

In this subsection, we present a new method to construct a family Cayley graph from the old one by edge rearrangement, that is by switching the edges or the connections between the vertices of the graph in a certain manner that maintains almost the same expansion ratio and density of the graph and the degree of vertices. In particular, we prove that if the family of Cayley graphs {Cay(G i ; {s ±1 1 , s ±1 2 }), i ∈ N + } is an expander, then so is the family of Cayley graphs {Cay(G i ; {s ±1 1 , s 1 s 2 , s -1 2 s -1 1 }), i ∈ N + } (see Proposition 4.5.2). Before we present the proof of this result we need first few more notations.

, . . . , s ±1 k }. Let H ⊆ G, then |∂ H(Cay(G, S))| = 2 ∑ i|o(s i )>2 |N s i (H)| + ∑ i|o(s i )=2 |N s i (H)| = ∑ 1≤i≤k |N s ±1 i (H)|.
Proof. Let x, y ∈ H such that y = s i x for some s i ∈ S, then x = s -1 i y. Thus the number of edges in the subgraph H of G that corresponds to s i is equal to that of s

)| = |N s -1 1 (H) ∩ N s 2 (H)|. Thus 2|N s 1 (H)| + 2|N s 2 (H)(H 1 )| -2|N s -1 1 (H) ∩ N s 2 (H)| ≤ 2|∂ ′′ H| -|∂ ′ H|.
Noticing that

|N s -1 1 (H) ∩ N s 2 (H)| ≤ |N s -1 1 (H)| = |N s 1 (H)|, then 2|N s 2 (H)(H 1 )| ≤ 2|∂ ′′ H| -|∂ ′ H|.
Finally, we obtain

0 < ε ≤ |∂ ′ H| 2|H| ≤ |∂ ′′ H| |H| .
As a consequence of the previous theorem and Proposition 4.5. Thus, we conclude the following theorem. Remarks.

1. Using Corollary 2.3.2, it is easy to check that the first expander family given in Theorem 4.5.6 is formed of simple graphs, while the second one is not. By Proposition 2.4.1, we also deduce that the graphs of both families are semiregular, that is, the above two expander families are irregular.

2. Each {Cay(G i , S * i ), i ∈ N + } expander family enables us to construct several expander families of G-graphs {Cay(G i , S i ), i ∈ N + } depending on the choice of the set S i from the larger set S * i , some of these families can be isomorphic to each other. The expander family Φ(PSL(2, Z/pZ); {S 2 , S 2 S 3 }), p ∈ P is isomorphic to the following expander families: i. Φ(PSL(2, Z/pZ); {S 2 , S - 4. Note that the degree of the vertices of Φ(G; L) are less than those of Cay(G, L ±1 ) and Cay(G, L * ). Also note that Cay(G,W * ) and Φ(G;W ) have the same number of edges, while the size of both graphs are equal. In other words, the infinite expander family of G-graphs Φ(G; L) is sparser than the original infinite expander family of Cayley graphs Cay(G, L ±1 ), which is a 4-regular graph, and also sparser than Cay(G, L * ), which is a 5-regular graph. The same remark is applied to the infinite expander family of G-graphs Φ(G;W ) and the Cayley graph one Cay(G,W * ). Lemma 4.5.7. Let P be the set of all prime numbers, then {PSL(2, Z/pZ), p ∈ P} is a G-expander family.

We close this section by the following corollary which is obtained by using Theorem 4.5.6 and Corollary 4.3.5.

Corollary 4.5.8. Let P be the set of all prime numbers, then the following family of G-graphs is an expander family:

Φ(PSL(2, Z/pZ); {S 2 , S 2
2 , S 2 S 3 }), p ∈ P .

Some observations

In few words, up-till now constructing expander families is not an easy task. Most constructions use deep algebraic and combinatorial techniques. One of the chief tools to attain this goal is by using Cayley graphs. Concerning this, a huge amount of research in the last few decades has been devoted to investigate which family of Cayley graphs is an expander family and which are not. Many partial results were obtained in which many of them are unfortunately negative [START_REF] Hoory | Expander graphs and their applications[END_REF][START_REF] Rosenhouse | Isoperimetric numbers of cayley graphs arising from generalized dihedral groups[END_REF]. In this chapter, a new straightforward method for approaching this problem is presented. This technique is based on the "twin brother" of Cayley graphs the G-graphs and its special structural properties (see the proof of Theorem 4.3.3). The principal features of this technique can be summarized in the following points:

1. As seen in Theorem 4.5.6, our construction is simpler than most known techniques for constructing expander families since it uses straightforward method for constructing expander G-graphs from the Cayley ones (for more details see book [START_REF] Krebs | Expander Families and Cayley Graphs: A Beginner's Guide. EBSCO ebook academic collection[END_REF] and survey [START_REF] Lubotzky | Expander graphs in pure and applied mathematics[END_REF], where the authors review some common methods for constructing expanders like the Cayley graph and the Zig-Zag product).

2. As explained earlier, unlike Cayley graphs, G-graphs enable us not only to construct expander families of d-regular graphs, but also regular and irregular ones (see the remark after Corollary 4.3.5).

Chapter 5

Spectra of Cayley graphs and G-graphs

The graphs defined from groups, like Cayley graphs, have been deeply studied for various reasons. In particular, these graphs are considered either to be used as an effective tool to approach specific problems in graph theory like constructing integral, expander, and Ramanujan graphs, or for their own interest, like computing the spectrum, the diameter, or to study the Hamiltonicity of certain Cayley graphs of specific groups (see e.g. [START_REF] Krebs | Expander Families and Cayley Graphs: A Beginner's Guide. EBSCO ebook academic collection[END_REF][START_REF] Witte | A survey: Hamiltonian cycles in Cayley graphs[END_REF]). In this chapter, we establish a relation between Cayley graphs and G-graphs that generalizes the one presented in [START_REF] Bretto | Cayley graphs and G-graphs: Some applications[END_REF]. This gives us the ability to approach certain open problems in the theory of Cayley graphs [START_REF] Badaoui | On a relationship between Cayley graphs and G-graphs and some applications[END_REF]4]. For instance, in many cases, and unlike many families of Cayley graphs, evaluating the spectra of the corresponding G-graphs ones is a trivial task, and vice-versa. Using this fact and certain results in the theory of spectral hypergraph, we present a new method to compute the eigenvalues of certain Cayley graphs and G-graphs. This leads us to present new classes of integral and strongly regular Cayley graphs in Sections 5.4 and 5.6. Several other results on the expander and Ramanujan graphs are given in Section 5.7.

The main contributions of this chapter are proved in article [4].

A connection between Cayley graphs and G-graphs

In this section, a relation is established between certain classes of Cayley graphs and the G-graphs ones. Then, a link is presented between the spectrum of the two graphs (see Section 5.2). This leads to a wide variety of results concerning several extensively studied problems in the theory of Cayley graphs and many others. For instance, new infinite classes of strongly regular Cayley graphs, of integral Cayley graphs, etc (see Sections 5.4 and 5.6). Before we present the proof of one of the main results of this chapter, we need the following notation.

Certainly, there is a connection between the spectrum of the graph Γ and the spectrum of its line graphs Γ l . For instance, see Theorem 5.2.4 where we present a direct relation between their spectrum for certain case. Concerning line graphs in our context, is the following.

Relation between the spectra of G-graphs and Cayley graphs

In this section, we first recall some well-known results from algebraic graph theory related to the relation between the spectrum of a graph and its line graph (see Corollary 5.2.3 and Theorem 5.2.4). Then, generalization of these results is presented to the hypergraph case. Moreover, a relation between the spectra of certain Cayley graphs and the G-graph ones is introduced in Theorem 5.2.8. This relation will allow us in Sections 5.3, 5.4, and 5.6 to compute the spectra of certain families of Cayley graphs and to present new families of integral and strongly regular graphs. We draw the attention of the reader that the given generalizations to the hypergraph case are the key that enable us to prove Theorem 5.2.8.

Before we start we need to recall some basic facts such as the adjacency matrix and the spectrum of a hypergraph which can be thought as a simple generalization to their corresponding ones in the graph case. Definition 5.2.1. Let H be a hypergraph with the vertex set {v i , 1 ≤ i ≤ n} and the hyperedge set {e j , 1 ≤ j ≤ m}. In this article, we define the adjacency matrix of hypergraph H, denoted by A(H), in a similar way to that of the graph case. More precisely, A(H) is the n × n matrix whose (i, j)-entry is the number of hyperedges that contain both v i and v j . The incidence matrix, the characteristic polynomial, and the spectrum of a hypergraph H are defined in an analogical way.

Remark. It should be noted here that there are other ways to generalize the notion of the adjacency matrix of a graph to the hypergraph case (see e.g. [START_REF] Cooper | Spectra of uniform hypergraphs[END_REF][START_REF] Qi | Eigenvalues of a real supersymmetric tensor[END_REF]).

As a direct consequence of Theorem 5.1.2 we have the following result.

Proof. Let M be the incidence matrix of H. Note that H has ra t edges, then M is a × ra t matrix. Let λ 1 = r, λ 2 , . . . , λ l be the eigenvalues of H. Suppose that t ≤ r, then obviously a ≤ ra t . So that the order of M T M is greater than or equal to the order of MM T and in this case the eigenvalues of M T M are the eigenvalues of MM T in addition to 0 with multiplicity ra t a. From Proposition 1.4.4 and Lemma 5.2.5, we know that the eigenvalues of MM T are 2r, λ 2 + r . . . , λ a + r, then the eigenvalues of M T M are 2r, λ 2 + r, . . . , λ a + r and 0 with multiplicity ra t a. Therefore, the eigenvalues of H l are 2r -t, λ Remark. Beside the group S n , the alternating group A n is also a good candidate for applying the preceding theorem. As it is well-known that A n is generated by the 3-cycles (123), (124), ..., (12n) for n ≥ 3.

Applications 1: On the spectra of some Cayley and G-graphs families Generally speaking, computing the spectra of an infinite family of Cayley graphs of nonabelian groups is a hard task. Nonetheless, in certain situations and due to the special forms and properties of the corresponding G-graphs ones, evaluating their spectra is an attainable goal, and vice-versa. Equipped with the presented results in Theorem 5.2.8, we choose in this section to investigate this particular problems from a new perspective.

Spectrum of an infinite Cayley family

In this subsection, G-graphs are used to calculate the spectrum of an infinite 6-regular Cayley graph family on the dicyclic group {Dic 8i , i ∈ N + }.

{4 cos 2πi 4m + 2/i = 1, . . . , 4m} {-2[4m]}.
Proof. The vertices of level V s and V rs of the G-graph Φ(G, S) are respectively:

V s = {u 0 = (e, s, s 2 , s 3 ), u 1 = (r, sr, s 2 r, s 3 r), . . . , u 2m-1 = (r 2m-1 , sr 2m-1 , s 2 r 2m-1 , s 3 r 2m-1 )},

V rs = {v 0 = (e, sr, s 2 , s 3 r), v 1 = (r, sr 2 , s 2 r, s 3 r 2 ), . . . , v 2m-1 = (r 2m-1 , s, s 2 r 2m-1 , s 3 )}. Note that each vertex u i ∈ V s is connected by double edges to each v i and v i-1 ∈ V rs for every i ∈ {1, . . . , i} and u 0 is connected by double edges to v 0 and v 2m-1 (see Figure 5

Spectrum of an infinite G-graph family

In this subsection, Cayley graphs are used to compute the spectra of an infinite 4-regular G-graph family on the dihedral groups {D 2i , i ∈ N + }.

Proposition 5.3.2. Let G = D 2n and S = {s, sr, rs} where n is an even integer. Then the eigenvalues of Φ(G, S) are

{2 cos 2πi n + 1, 2 cos 2πi n -1/i = 1, . . . , n} {-2[ 3n 2
n]}.

Proof. As the order of vertices s, sr, and rs is 2, then S = S * = {s, sr, rs}. Now let V 1 = {e, sr, r 2 , . . . , sr n-1 } and V 2 = {s, r, sr 2 , . . . , r n-1 } be the vertices of Cay(D 2n , S). Note that each vertex u ∈ V 1 is connected to a single vertex su ∈ V 2 and that the vertices of V 1 and V 2 form each a cycle of length n (see Figure 5.

Applications 2 and more: New classes of integral Cayley graphs

An integral graph is a graph whose spectrum consists entirely of integers. For many reasons constructing integral graphs is not an easy task, for instance out of 164,059,830,476 connected graphs on 12 vertices, there exist exactly 325 integral graphs [START_REF] Balińska | A Survey on Integral Graphs. Publikacije Elektrotehničkog fakulteta[END_REF]. Recently, Cayley graphs have been efficiently used to construct an infinite family of integral graphs (see e.g. [1] and Constructing new classes of integral graphs using the generalized replacement product of graphs Generally speaking, graph products like the Cartesian, the lexicographic, and the tensor products are important tools to construct bigger graphs while preserving certain properties of the original graphs, they also play an important role in designing and analysing networks (see e.g. [START_REF] Xu | Topological structure and analysis of interconnection networks[END_REF]). The problem of constructing infinite classes of integral graphs has attracted the attention of many researchers (see e.g. [START_REF] Indulal | Some New Integral Graphs[END_REF][START_REF] Wang | Constructing Fifteen Infinite Classes of Nonregular Bipartite Integral Graphs[END_REF][START_REF] Wang | Integral complete multipartite graphs[END_REF]). In the literature, most of these classes are constructed by applying either the complete graph K n or the complete bipartite graph K n,n to produce infinite classes of integral graphs (see e.g. [START_REF] Indulal | Some New Integral Graphs[END_REF][START_REF] Mohammadian | Some constructions of integral graphs[END_REF][START_REF] Wang | Integral complete multipartite graphs[END_REF]). Our aim in this subsection is to construct infinite families of integral graphs starting with an arbitrary integral graph. First, a new graph product the generalized replacement product, is defined. Then, different properties of this product are studied like its spectrum.

For j = 1, 2, ..., k, let A j be any n j × n j matrix with corresponding eigenvalues λ 1 j , λ 2 j , . . . , λ n j j . For each j = 1, 2, ..., k, let u j be the eigenvector of A j corresponding to the eigenvalue λ 1 j with u j = 1. Also, for p = 1, 2, ..., k and q = 1, 2, ..., k let ρ pq be arbitrary constants. In addition, define the following two matrices:

B =            A 1 + ρ 11 u 1 u T 1 ρ 12 u 1 u T 2 . . . ρ 1k u 1 u T k ρ 21 u 2 u T 1 A 2 + ρ 22 u 2 u T 2 . . . ρ 2k u 2 u T k ρ 31 u 3 u T 1 ρ 32 u 3 u T 2 . . . . . . . . . . . . . . . . . . ρ (k-1)1 u k-1 u T 1 . . . . . . ρ (k-1)k u k-1 u T k ρ k1 u k u T 1 . . . ρ k(k-1) u k u T k-1 A k + ρ kk u k u T k            (
ρ (k-1)1 . . . λ 1k-1 + ρ k-1k-1 ρ (k-1)k ρ k1 . . . ρ k(k-1) λ 1k + ρ kk            (5.
2)

The following result can be found in [START_REF] Mourad | Generalization of some results concerning eigenvalues of a certain class of matrices and some applications[END_REF].

Theorem 5.4.7.

[61] For j = 1, 2, ..., k, let A j be n j × n j matrices with corresponding eigenvalues λ 1 j , λ 2 j , ..., λ n j j counted with their multiplicities. Suppose that for each j = 1, 2, ..., k, the vector u j is the eigenvector of A j corresponding to the eigenvalue λ 1 j with u j = 1. Then, for any ρ pq where 1 ≤ p, q ≤ k, the matrix B in (5. where γ 1 , γ 2 , ..., γ k are the eigenvalues of the matrix B in (5.2).

Motivated by the preceding result, we have the following definition.

Definition 5.4.8. Let Γ, Γ 1 , . . . , Γ n be n + 1 multigraphs where V (Γ) = 1≤i≤n {a i }. The generalized replacement product Γ △ (Γ 1 , . . . , Γ n ) is obtained by replacing each vertex a i of Γ by a copy of Γ i for all 1 ≤ i ≤ n, where the number of edges between each vertex of Γ i and each vertex of Γ j is equal to the number of edges between vertices a i and a j in Γ for all 1 ≤ i, j ≤ n.

If Γ 1 ≃ Γ 2 ≃ . . . ≃ Γ n , then Γ △ (Γ 1 , . . . , Γ n ) is denoted by Γ △ Γ 1 .
The generalized replacement product of two multigraphs is illustrated in Figure 5.8.

As a result, we have the following.

Fig. 5.9 The integral graph K 2,2 △ K 2 with spectrum (5, 1, 1, -1, -1, -1, -1, -3).

•

σ ( Φ(G, S)) = {4} {0[3]} {-2[2]} • σ ( Φ(S 3 , S)) = {4} {1[4]} {-2[4]} • σ ( Φ(A 4 , S)) = {3} {1[3]} {-1[3]} {-3}. Thus {K n △ Φ(G, S)}, {K n △ Φ(S 3 , S)} and {K n △ Φ(A 4 , S)} constitute explicit examples of integral graphs.
Of course many other constructions can be done similarly.

Spectral properties of certain Cayley graphs and G-graphs

In this section, we use the structural properties of G-graphs presented in Chapter 2 to evaluate certain eigenvalues of all the d-regular G-graphs Φ(G, S). This in turn, leads us to compute some eigenvalues of all the infinite classes of the Cayley graphs Cay(G, S * ).

Definition 5.5.1. Consider two sequences of real numbers: θ n ≤ ... ≤ θ 1 , and η m ≤ ... ≤ η 1 with m < n. The second sequence is said to interlace the first one whenever θ n-m+i ≤ η i ≤ θ i , f or i = 1, ..., m. where in A i, j denotes the block submatrix of A formed by the rows of X i and the columns of X j . Let b i, j denote the average row sum of A i, j . Then the matrix B = (b i, j ) 1≤i, j≤m is called the quotient matrix of A according to the partition {X 1 , ..., X m }. If the row sum are equal for each block A i, j where 1 ≤ i, j ≤ m, then the partition {X 1 , ..., X m } is called equitable.

Remark. If Γ is a graph with vertex set V (Γ). Then the partition {V 1 , . . . ,V t } of V (Γ) is equitable if and only if any two vertices in V i have the same degree in V j , ∀i, j ∈ {1, . . . , k}.

The following proposition follows directly from the previous remark and the definition of G-graph (Definition 2.1.2). Recall that the Φ(G, S) is the G-graph Φ(G, S) with loops. Now by the same analogy followed in the proof of the previous theorem, we can compute the following eigenvalues of Φ(G, S). As a direct consequence of Theorem 5.2.8 and the previous theorem, we have the following result.

Applications 3: New classes of strongly regular Cayley graphs

In this section, we present a necessary and sufficient condition for certain Cayley graphs and G-graphs to be strongly regular graphs. This leads us to introduce new classes of strongly regular Cayley graphs. First, we recall some basic properties of strongly regular graphs. Definition 5.6.1. [START_REF] Bapat | Graphs and Matrices[END_REF] A graph Γ is strongly regular graph, if it is regular, and there are two nonnegative integers a and b such that for every pair v 1 , v 2 of vertices the number of common neighbors of v 1 and v 2 is a if v 1 and v 2 are adjacent; and b if v 1 and v 2 are not adjacent.

Theorem 5.6.2. A connected graph Γ is a strongly regular if and only if it is regular and it has at most 3 different eigenvalues. Remark.

Chapter 6 Conclusion and future research directions

As the reader has seen, there are considerable obstacles to construct an expander family.

The most common way is by using Cayley graph and its corresponding Kazhdan constant, the reasons/benefits that stand behind such a choice is explained in Chapter 3 and Section 1.5. Nonetheless, the most obvious attempts in this direction do not work, for instance, the Cayley graph on an abelian group and the dihedral group. The problem of finding sequence of groups that corresponds to an expander family of Cayley graphs has been considered by many authors. A huge amount of research with mostly negative results has been published in the last few decades [START_REF] Hoory | Expander graphs and their applications[END_REF][START_REF] Rosenhouse | Isoperimetric numbers of cayley graphs arising from generalized dihedral groups[END_REF], and references therein. This thesis provides different algebraic and combinatorial techniques to approach this particular problem and other closely related problems. In the second chapter, we continue the previous studies regarding the structural properties of G-graphs, this gives us a starting point to investigate their different expansion properties/qualities. The fourth chapter is devoted to study the problem of constructing expander families of Cayley and G-graphs from a combinatorial point of view. As a result, several new families of such graphs are presented. In the fifth chapter, we reveal key aspects from the theory of spectral hypergraph. These properties pave the way to approach the core problem of this research from an algebraic point of view, and then to present several results on a closely related problem.

In this chapter, the main contributions to the different posed problems in each chapter are presented. Also, we discuss the possible horizons for future researches, their road-maps starting from what already achieved, and point out to the possible predictable results. All this flow emphasizes the fact that these new graphs defined from groups, that are G-graphs, will continue to play a key role in the future constructions of expander families.

Main contributions

The main contributions of this thesis are the following:

1. The identification of various approaches for constructing infinite families of expander G-graphs. Mainly by using either deep combinatorial methods (see Theorem 4.3.3) 4. Many new results concerning the structural properties of G-graphs Φ(G, S) and Φ(G, S) are revealed; most importantly, those regarding the principal cliques, the regularity of G-graphs, and some of their graph invariants like the diameter (see Proposition 2.4.1, Theorem 2.4.5, and Lemma 4.3.1). For instance, in Chapter 2 the number of emitted edges from each the principal clique of Φ(G, S) is proved to be constant and directly related to whether the graph is simple or not.

5. The construction of 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.

6. The identification of a new method for generating an infinite regular family of Cayley graph 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). ii. The construction of several new infinite classes of integral Cayley graphs either by using G-graphs or by using the generalized replacement product.

iii. The computation of certain eigenvalues of the Cayley graph Cay(G, S * ) and the G-graphs Φ(G, S) and Φ(G, S).

iv. A necessary and a sufficient condition for the strong regularity of certain Cayley and G-graphs is presented; this condition is used to present new classes of these graphs.

Open problems and future research

The adopted methodologies in this quest provide a standing ground to investigate several closely related threads. First, in a similar way to the work presented in Chapter 2, one can further investigate certain G-graph invariants and structural properties, such as its diameter, connectivity, regularity, density, etc. In this thesis, many aspects/bounds of these invariants when needed are studied and revealed (see for example Lemma 4.3.1). As the levels of a G-graph already show(see Proposition 2.4.1), we predicate that the number of emanating edges from any principal clique E x would give an insightful look at specific key properties of G-graphs. In particular, those regarding not only its simplicity (see Corollary 2.4.7), but also its regularity, connectivity, and expansion ratio. The second one of these threads is investigating the possibility of constructing expander families of G-graphs using similar techniques to those of the Cayley ones. In particular, a new Kazhdan constant definition κ ′ (G, S), could be presented for any G-graph Φ(G, S). This could lead to similar results to the Cayley graph case. That is to say, a family of G-graphs {Φ(G i , S i ), i ∈ N} is an expander family if and only if the corresponding Kazhdan constants κ ′ (G i , S i ) are uniformly bounded away from zero (for more information see Subsection 3.5.4).

In Chapter 4, we have seen that each {Cay(G i , S * i ), i ∈ N + } expander family enables us to construct several expander families of G-graphs depending on the choice of the generating set S i from S * i . These families could have different expansion ratio(s), even though, they are all are uniformly bounded away from zero by the same constant (see the proof of Theorem 4.3.3). Since the "expansion quality" of a graph is determined by its corresponding expansion ratio, it would be interesting to investigate which one of these infinite families of G-graphs has the optimal (maximal or minimal) expansion ratio.

Up till now, the amount of research in the theory of spectral hypergraph is still pretty small. It would be interesting to investigate the different aspects of this theory and its relation to certain invariants. In particular, this could lead to generalizing Theorem 5.2.7 to the irregular, or not uniform, hypergraph case. As a result, Theorem 5.2.8 can be improved to the case where the order of the elements of the generating set S are not all equal. Note that using Theorem 5.2.4 and the algebraic definition of expanders presented in Chapter 3, it is easy for the reader to see that the line graph of an expander graph is also expander. It would be interesting to study the credibility of this statement in the hypergraph case. That is to say, if the line graph of an expander hypergraph is also expander or not. Consequently, if the last statement holds, then using Theorem 5.1.2, Conjecture 5.1.3 which generalizes Theorem 4.3.3 will be proved. Additional to these research subjects that rise directly from this study, one can investigate many open problems/invariants/structural properties on/of Cayley graphs that could be easier to deal with them using G-graphs, and vice-versa.

Fig. 1

 1 Fig. 1 Les G-graphs Φ(Z/16Z, {1, 4}) et Φ(Z/16Z, {1, 8}).

2 s 3 r 2 r 2 s 2 r 2 s 2 r 3 r 3 sr 3 s 3 r 3 Fig. 2

 22232 Fig. 2 Le graphe de Cayley Cay(Dic 16 ; {s, s 2 , s 2 , s 3 , sr, s 3 r}).

Fig. 4

 4 Fig. 4 Le graphe intégral de Cayley Cay(Z 3 × Z 3 , S * ).

2 .

 2 The infinite path; G = Z and S = {-1, 1}.

3 .

 3 The cycle C n ; G = Z/nZ and S = {-1, 1}; or G = D 2n and S = {s, sr}. Moreover, the circulant graphs are exactly the Cayley graphs of the finite cyclic groups.

Fig. 1 . 2

 12 Fig. 1.2 The Cayley graphs Cay(Z/4Z, {1, 2, 3}) and Cay(Z/8Z, {1, 4, 7}).

Fig. 1 . 3

 13 Fig. 1.3 The Cartesian product of the cycle C 3 and P 2 .

Fig. 1 . 4

 14 Fig. 1.4 The dual and the 2-section graphs of a hypergraph H.

Example 3 .Fig. 1 . 5

 315 Fig. 1.5 The graph Γ.

  Proposition 1.5.1. [50] Let G be a finite group and S a symmetric subset of G. Then, 1. The Cayley graph Cay(G, S) is |S|-regular.

Fig. 1 . 6

 16 Fig. 1.6 The Petersen graph is vertex transitive and not a Cayley graph.

Fig. 1 .

 1 Fig. 1.7 The Cayley graph Cay(Z/7Z, {±2, ±1}) is not edge-transitive.

  of x ∈ G, denoted by C x , is the subgraph of Φ(G, S) induced by the set of vertices which contain x. In Φ(G, S) there are |G| principal cliques; each contains |S| vertices. Remark. Note that each G-graph Φ(G, S) contains |G| principal cliques and |S| levels each corresponds to an element of G and S, respectively. Note also that the principal clique C x of Φ(G, S) contains |S| vertices one from each level, in which all share at least one element x ∈ G. Then the complete graph K |S| is a spanning subgraph of the induced subgraph with vertex set V (C x ) of Φ(G, S).

Fig. 2 . 1

 21 Fig. 2.1 The G-graph Φ(Z/16Z, {1, 4, 8}).

Figure 2 .

 2 Figure 2.1 shows the simple G-graph Φ(Z/16Z, {1, 4, 8}), while Figures 2.2 shows the Ggraphs Φ(Z/16Z, {1, 4}) and Φ(Z/16Z, {1, 8}), respectively. Note that since |G| = 16, then there are 16 principal cliques in Φ(Z/16Z, {1, 4, 8}) each of size |S| = 3. For instance, the principal cliques C 0 and C 1 are the induced subgraphs of Φ(Z/16Z, {1, 4, 8}) with vertex set {(0, 1, 2, . . . , 15), (0, 4, 8, 12), (0, 8)} and {(0, 1, 2, . . . , 15), (1, 5, 9, 13), (1, 9)}, respectively.

Fig. 2 . 2

 22 Fig. 2.2 The G-graphs Φ(Z/16Z, {1, 4}) and Φ(Z/16Z, {1, 8}).

Fig. 2 . 3

 23 Fig. 2.3 The star S 8 and the bipartite K 2,3 graphs.

1 . 5 .

 15 The Cycles of even length C 2i where i ∈ N + . The group G = D 2n and S constitutes of two symmetries elements s and sr. 2. The octahedral graph. The group G = Z/2Z × Z/2Z and S = {(1, 0), (0, 1), (1, 1)}. 3. The cuboctahedral graph. The group G = Z/2Z × Z/2Z × Z/2Z and S = {(1, 0, 0), (0, 1, 0), (0, 0, 1)} 4. The square, G is the Klein's group, G = {e, a, b, ab} and S = {a, b}. The cube, G = A 4 and S = {(1, 2, 3), (1, 3, 4)}. 6. The Heawood graph G = a, b|a 7 = b 3 = e, ab = baa and S = {b, ba}. 7. The Pappus graph G = a, b, c|a 3 = b 3 = c 3 = e, ab = ba, ac = ca, bc = cba and S = {b, c}.

Fig. 2 . 4

 24 Fig. 2.4 The Ljubljana and the Gray graphs.

Example 9 .

 9 Let Γ = (V, E, ξ Γ ) be the graph given in Figure 3.1 and let V ′ be the set of the eight marked vertices. The edge boundary of V ′ consists of the sixteen edges edges, then, |V ′ | = 8 and |∂V ′ | = 16. Note that reversing the roles of the eight marked vertices and the black vertices does not change the edge boundary, in other words, ∂V ′ = ∂ (V \V ′ ) (see also the third remark after Example 10).

Fig. 3 . 1

 31 Fig. 3.1 The edge boundary ∂V ′ .

Proposition 3 . 5 . 2 .

 352 [START_REF] Krebs | Expander Families and Cayley Graphs: A Beginner's Guide. EBSCO ebook academic collection[END_REF] Let Γ be a connected d-regular graph, then diam(

Corollary 3 . 5 . 4 .

 354 No family of Cayley graphs {Cay(G i , S i ), for all i ∈ N} on finite abelian groups, where |S i | = d for all i ∈ N, is an expander family. In Proposition 3.5.5, we give a simple generalization of Proposition 3.5.1 to the bounded degree graph case. In Chapter 4, we shall use this proposition to prove a similar result to Corollary 3.5.4 for the G-graph case (see Corollary 4.3.2). Proposition 3.5.5. Let Γ be a connected graph such that ∆(Γ) ≤ r ∈ N + . Then log r |V (Γ)| ≤ diam(Γ).

Example 13 .

 13 By Theorem 1.4.1, we have λ 2 (C i ) = 2 cos 2π i . Hence its corresponding spectral gap 2 -2 cos 2π

Lemma 4 . 3 . 1 .

 431 Let G be an abelian group generated by S = {s 1 , . . . , s k } and let Φ(G, S) be the corresponding G-graph, then diam( Φ(G, S)) ≤ |S|.

Corollary 4 . 3 . 2 .

 432 No family of abelian groups is a G-expander.

Theorem 4 . 3 . 3 .

 433 If {Cay(G n , S * n ), n ∈ N + } is an expander family, then { Φ(G n , S n ), n ∈ N + } is also an expander family.Proof. Since Cay(G n , S * n ) is an expander family, then |G n | → ∞ as n → ∞ and there is an r ∈ N + such that |S * n | ≤ r for all n ∈ N + . Hence |S n | ≤ r and O max (S n ) ≤ r for every n

Corollary 4 . 3 . 4 .Corollary 4 . 3 . 5 .

 434435 If {G n , n ∈ N + } ❈❛②-expander family, then it is also G-expander family. If {Cay(G i , S * i ), i ∈ N + } is an expander family, then { Φ(G i , S i ), i ∈ N + }is also an expander family.

  Degree |S * |-regular graph d(u) = o(s)(|S| -1)for all u ∈ V s and s ∈

Notation.

  Let Cay(G, S) be a Cayley graph and let H ′ ⊆ H ⊆ G. Let s ∈ S, we denote by N s (H) and N s (H)(H ′ ) the set of vertices of Cay(G, S) that are defined in the following way:i. N s (H) = sH ∩ H, ii. N s (H)(H ′ ) = sH ′ ∩ H.Next, we start by the following simple lemma.

Lemma 4 . 5 . 1 .

 451 Let Cay(G, S) be a Cayley graph, where S = {s ±1 1

Theorem 4 . 5 . 6 .

 456 Let P be the set of all prime numbers. Then the following G-graphs families are expanders:1. Φ(PSL(2, Z/pZ); {S 2 , S 2 S 3 }), p ∈ P .2. Φ(PSL(2, Z/pZ); {S 2 , S 2 2 , S 2 S 3 }), p ∈ P .

Lemma 5 . 1 . 5 .

 515 Let Γ be a d-regular graph, then (Γ l ) l = Γ if and only if d = 2.Proof. The proof is clear for the sufficient condition. Now suppose that(Γ l ) l = Γ, then (Γ l ) l is also a d-regular graph. Note that d(Γ l ) = 2d -2 and that d(Γ l ) = 2(2d -2) -2 = 4d -6 so that 4d -6 = d or d = 2.From Proposition 2.3.4, Corollary 5.1.4, and Lemma 5.1.5, we conclude the following.Corollary 5.1.6. Let G be a group and let S be a non-empty subset of G. Then it holds that Φ(G, S) l = Cay(G, S) if and only if |S| = 2 and o(s) = 2 for all s ∈ S.

Theorem 5 . 2 . 8 .

 528 Let Φ(G, S) be a d-regular G-graph, where |G| = n, |S| = k, and o(s) = O for all s ∈ S. If O ≤ k, then P( Φ(G, S), λ ) = (λ + O) n( k O -1) P(Cay(G, S * ), λ + Ok). If k ≤ O, then P(Cay(G, S * ), λ ) = (λ + k) n(1-k O ) P( Φ(G, S), λ + k -O).

Proposition 5 . 3 . 1 .

 531 Let G = Dic 8m and S = {s, sr}. Then the eigenvalues of Cay(G, S * ) = Cay(Dic 8m , {s, s 2 , s 2 , s 3 , sr, s 3 r}) are:

Fig. 5 . 1

 51 Fig. 5.1 The G-graph Φ(Dic 8m , {s, sr}).

  .1). Then, A( Φ(Dic 8m , S)) = 2A(C 4m ). Using Theorem 1.4.1 we have σ ( Φ(Dic 8m , S)) = {4 cos 2πi 4m /i = 1, . . . , 4m}, and as k = 2 and O = 4, then by Theorem 5.2.8 the proof is complete. As an illustration, the Cayley graphs Cay(Dic 8i ; {s, s 2 , s 2 , s 3 , sr, s 3 r}) for i = 1 and 2 are shown in Figures 5.2and 5.3, respectively (here the bold thick links correspond to double edges).

Fig. 5 . 2

 52 Fig. 5.2 The Cayley graphs Cay(Dic 8 ; {s, s 2 , s 2 , s 3 , sr, s 3 r}).

2 s 3 r 2 r 2 s 2 r 2 s 2 r 3 r 3 sr 3 s 3 r 3 Fig. 5 . 3

 222353 Fig. 5.3 The Cayley graphs Cay(Dic 16 ; {s, s 2 , s 2 , s 3 , sr, s 3 r}).

Fig. 5 . 5

 55 Fig. 5.4 The Cayley graph Cay(D 2n , {s, sr, rs}).

Fig. 5 . 7 Corollary 5 . 4 . 6 .

 57546 Fig. 5.7 The Cayley graph Cay(Z 3 × Z 3 , S * ).

Definition 5 . 5 . 2 .

 552 Suppose A is a symmetric real matrix whose rows and columns are indexed by X = {1, ..., n}. Let {X 1 , ..., X m } be a partition of X. Let A be partitioned according to {X 1 , ..., X m }, that is,

Proposition 5 . 5 . 3 .Theorem 5 . 5 . 5 .

 553555 Let Φ(G, S) be a G-graph such that |S| = k. Then the levels of Φ(G, S), or {V 1 , . . . ,V k }, form an equitable partition of the vertices of V ( Φ(G, S)). Theorem 5.5.4. [26] Let B be the quotient matrix of A with respect to a partition. Then the eigenvalues of B interlace the eigenvalues of A. If the partition is equitable then any eigenvalue of B is an eigenvalue of A. Now we will use Theorem 5.5.4 and Proposition 5.5.3 to obtain the following result. Let Φ(G, S) be a d-regular G-graph, such that |G| = n and |S| = k. Then (k -1)O and -O are eigenvalues of Φ(G, S) with multiplicities greater than or equal to 1 and k -1, respectively. Proof. Let B be the quotient matrix of Φ(G, S) with respect to the levels {V 1 , . . . ,V k } of Φ(G, S), then (J k -I K ), since J k and I K commutes, then by Proposition 1.4.4 the eigenvalues of B are (k -1)O and -O with multiplicities 1 and (k -1), respectively. By Proposition 5.5.3, we know that the levels of Φ(G, S), or {V 1 , . . . ,V k }, form an equitable partition of V ( Φ(G, S)), then by Theorem 5.5.4, (k -1)O and -O are also eigenvalues of Φ(G, S) with multiplicities greater than or equal to 1 and k -1, respectively.

Proposition 5 . 5 . 6 .

 556 Let Φ(G, S) be d-regular G-graph, such that |G| = n and |S| = k. Then (k + 1)O and k+1 1-k O are eigenvalues of Φ(G, S) with multiplicities greater than or equal to 1 and k -1, respectively.

Theorem 5 . 5 . 7 .

 557 Let G be a group and S ⊂ G such that o(s) = o(s ′ ) for all s, s ′ ∈ S. Then k(O -1) and -k are eigenvalues of the Cayley graph Cay(G, S * ) with multiplicities greater than or equal to 1 and k -1, respectively.

Theorem 5 . 6 . 3 .Theorem 5 . 6 . 4 .Theorem 5 . 6 . 7 .

 563564567 Let Φ(G, S) be a simple G-graph, such that |G| = n, |S| = k, and o(s) = O for all s ∈ S. Then Φ(G, S) is a strongly regular if and only if n = O 2 . Proof. By Proposition 2.3.4, we deduce that Φ(G, S) is a d-regular where d = (k -1)O.Now since each level V s has n O vertices and every vertex u / ∈ V s is connected to at most O vertices of V s , then O ≤ n O or O 2 ≤ n. Thus it is sufficient to prove that Φ(G, S) is not strongly regular if and only if O 2 < n. If O 2 < n then O < n O , in this case, it is easy to see that 4 < diam( Φ(G, S)). Then by Proposition 1.4.5, Φ(G, S) has at least 5 distinct eigenvalues. Now by Theorem 5.6.2, we deduce that Φ(G, S) is not a strongly regular graph. If n = O 2 , then n O = O and thus every vertex u ∈ V s , s ∈ S is connected to all vertices of v / ∈ V s . Hence Φ(G, S) is the complete k-partite graph, which is a strongly regular graph. Let Cay(G, S * ) be a Cayley graph such that o(s) = o(s ′ ) for all s, s ′ ∈ S. Then, Cay(G, S * ) is strongly regular if and only if n = O 2 . Proof. From Theorems 5.2.8 and 5.6.2 we know that the Cayley graph Cay(G, S * ) is strongly regular if and only if the G-graph Φ(G, S) is strongly regular. Now by the previous theorem we have the result.Let G = Z/nZ × Z/nZ and S = {(1, 0), (0, 1), (1, 1)}. Now since o(s) = n 2 for all s ∈ S, then the families presented in Theorems 5.4.4 and 5.4.5 are also strongly regular families. Corollary 5.6.5. Let G = Z/nZ × Z/nZ, then the following families of Cayley graphs are strongly regular, {Cay(Z/nZ × Z/nZ, S * ), where S = {(1, 0), (0, 1)} and n ∈ N + }, {Cay(Z/nZ × Z/nZ, S * ), where S = {(1, 0), (0, 1), (1, 1)} and n ∈ N + }. Using Theorem 5.6.4 we obtain the following results. Theorem 5.6.6. Let G = Z/nZ×Z/nZ and S = {(a 1 , b 1 ), . . . , (a k , b k )} where min{gcd(a i , n), gcd(b i , n)} = 1, for every 1 ≤ i ≤ k. Then the following family of Cayley graphs is strongly regular, {Cay(Z/nZ × Z/nZ, S * ), n ∈ N + }. Let G = Z/nZ × . . . Z/nZ (a-times) and S = {g 1 , ..., g a }, where i'th element of g i = (0, ..., 0, 1, 0, ..., 0) is 1 and the rest is 0's for all 1 ≤ i ≤ a. Then the following family of Cayley graphs is strongly regular, {Cay(Z/nZ × Z/nZ × . . . Z/nZ, S * ), n ∈ N + }.

7 . 8 .

 78 Several results concerning spectrum of a hypergraph, its line graph, and the different relations between them are revealed. These results generalize certain well-known theorems in algebraic graph theory (see e.g. Theorem 5.2.4 and Theorem 5.2.7). The revealing of the different isomorphic relations between the Cayley graph Cay(G, S * ) and the G-graph Φ(G, S). These relations with several other results in Chapter 5, lead to a wide variety of results concerning extensively studied problems in the theory of Cayley and G-graphs, such as: i. The identification of a new method for computing the spectra of Cayley and G-graph.

  Useful definitions from hypergraph theory . . . . . . . . . . . . . . . . . . 1.3.1 Some general definitions . . . . . . . . . . . . . . . . . . . . . . . 1.3.2 Remarkable classes of graphs . . . . . . . . . . . . . . . . . . . . 1.4 Useful definitions from algebraic graph theory . . . . . . . . . . . . . . . . 1.4.1 Some general definitions . . . . . . . . . . . . . . . . . . . . . . . 1.4.2 Few useful results . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5 Cayley graphs: properties and limitations . . . . . . . . . . . . . . . . . . 2 G-graphs: A new representation of groups 2.1 Definitions, some notations and more . . . . . . . . . . . . . . . . . . . . 2.2 Particular examples and some applications . . . . . . . . . . . . . . . . . .

	Table of contents
	List of figures	xi
	List of tables	xiii
	1 Preliminaries
	1.

1 Useful definitions from group theory . . . . . . . . . . . . . . . . . . . . . 1.1.1 Some general definitions . . . . . . . . . . . . . . . . . . . . . . . 1.1.2 Generating set of a group . . . . . . . . . . . . . . . . . . . . . . 1.1.3 Action of a group . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.4 Isomorphism of groups . . . . . . . . . . . . . . . . . . . . . . . . 1.1.5 Group presentation . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Useful definitions from graph theory . . . . . . . . . . . . . . . . . . . . . 1.2.1 Some general definitions . . . . . . . . . . . . . . . . . . . . . . . 1.2.2 Some useful graph invariants . . . . . . . . . . . . . . . . . . . . . 1.2.3 Symmetric and semi-symmetric graphs . . . . . . . . . . . . . . . 1.2.4 Remarkable classes of graphs/operations . . . . . . . . . . . . . . 1.3 2.2.1 Particular examples . . . . . . . . . . . . . . . . . . . . . . . . . .

  starting from what already achieved, and point out some of the possible expected results. d'expansion. L'efficacité de nos techniques est illustrée en présentant de nouvelles familles infinies de Cayley d'expansion et grâce aux G-graphes nous mettons en lumière de nouvelles familles infinies d'expansion et notamment, a notre connaissance la première famille infinie d'expansion non réguliers. Nous avons également, dans ce travail calculé les spectres de certains graphes de Cayley et de G-graphes. Cela nous a donné de nouveaux résultats sur les intégral graphes de Cayley et sur leF forte régularité de certains graphes.

	Le concept général et quelques applications

D'une manière générale, la qualité d'un réseau de communication représenté par un graphe est mesurée par trois paramètres. Le premier est son coût ou la densité (en nombre d'arêtes) du graphe. Le deuxième est la fiabilité et le dernier est la rapidité représentée en théorie des graphes par la connectivité et le diamètre. En d'autres termes, plus la connectivité est élevée et plus le diamètre d'un graphe est petit, plus le réseau sera fiable et rapide c'est à dire que l'information se propagera rapidement. Les deux derniers invariants de graphes peuvent être combinés en une seule quantité, le taux d'expansion, qui mesure littéralement le degré d'expansion ou la «qualité d'expansion», et indirectement la connectivité du graphe.

Table 1

 1 L'existence des graphes d'expansion et reliée à des notions aléatoires. En fait, si nous choisissons au hasard une suite de graphes d-régulaires, elle est presque certaine d'être une famille d'expansion (voir[START_REF] Lubotzky | Expander graphs in pure and applied mathematics[END_REF]). Néanmoins, la construction explicite de graphes d'expansion, qui est pour plusieurs raisons très favorable et importante pour de nombreuses applications, est une tâche beaucoup plus difficile. La situation est comme celle des nombres transcendantaux. Si Pour atteindre cet objectif, les mathématiciens ont utilisé des invariants de graphes qui sont généralement plus faciles à gérer que le taux d'expansion h(Γ)[START_REF] Krebs | Expander Families and Cayley Graphs: A Beginner's Guide. EBSCO ebook academic collection[END_REF][START_REF] Rogawski | Discrete Groups, Expanding Graphs and Invariant Measures[END_REF]. Typiquement en utilisant la constante de Kazhdan de certains graphes de Cayley ou la deuxième plus grande valeur propre, ou non en montrant généralement que la Dans les tableaux suivants, nous listons ces trois invariants, leur notation, l'endroit où ils sont définis, et la relation entre eux. Les trois invariants d'un graphe.

	Invariant	Notation Définition
	Taux d'expansion	h(Γ)	Définition 3.2.2
	Deuxième plus grande	λ 2 (Γ)	Section 1.4
	valeur propre
	Diamètre	diam(Γ) Définition 1.2.3

l'on choisit un nombre réel au hasard, il est presque certain d'être transcendantal. Cependant, il n'est nullement facile de prouver qu'un nombre particulier est transcendantal. Jusqu'à présent, le graphe de Cayley et le produit Zig-Zag sont les deux principaux outils pour construire une famille d'expansion. Le principal avantage d'utiliser le graphe de Cayley est nous permettre, en fixant la taille de la partie génératrice d'un groupe, de construire une grande famille de graphes creux d'une manière efficace et concise. De plus, les propriétés sous-jacentes d'un groupe G et de sa partie génératrice S peuvent nous donner de l'information sur les propriétés d'expansion de son graphe de Cayley Cay(G, S) (voir [42, 52]). À cet égard, un nombre considérable de recherches ont été consacrées à la question suivante au cours des dernières décennies: Quelle séquence de groupes correspond à une famille d'expansion de Cayley ? La raison de cette approche est qu'il n'est pas pratique de calculer le taux d'expansion h(Γ) d'un graphe Γ, car cela nécessite de compter E(V ′ ,V ′ ) sur tous les ensembles de sommets V ′ où |V ′ | ≤ |V (Γ)| 2 . Noter que |E(V ′ ,V ′ )| est le nombre d'arêtes entre V ′ et le reste du graphe. Clairement, le nombre de tels ensembles de sommets augmente de façon exponentielle lorsque |V (Γ)| tend à l'infini. Ainsi, pour prouver que certaines familles {Γ i , i ∈ N} est une famille d'expansion, des méthodes indirectes sont nécessaires pour montrer que h(Γ i ) ≥ ε > 0 pour tout i ∈ N. limite du diamètre des graphes tend à zéro. C'est-à-dire que chacun des trois invariants de graphe ci-dessus mesure d'une manière ou d'une autre la qualité d'expansion d'un graphe de List of tables xxi Cayley.

  Comme nous l'avons vu, la construction de familles d'expansion n'est pas une tâche facile. Cette thèse fournit différentes techniques algébriques et combinatoires pour aborder ce problème particulier. Nous étudions également d'autres problèmes qui sont étroitement liés aux graphes d'expansion en utilisant les G-graphes. La raison de notre choix est d'abord un lien notable entre la classe des graphes de Cayley et les G-graphes. Cette relation est utilisée de manière significative pour obtenir de nombreux nouveaux résultats. Une autre raison est la forme générale des G-graphes, qui subodore que les G-graphes, doivent avoir dans de nombreux cas des propriétés de connectivité relativement élevées. Plus précisément, chaque ensemble maximum indépendant ou stable des G-graphes (qui est un niveau du graphe ) et chaque plus grand sous-graphe induit complet (qui est une clique principale du graphe G) ont un et un seul sommet en commun.

G-graphes sur les groupes abéliens, sont comme Cayley, ne peuvent jamais conduire à une famille d'expansion Si nous considérons une famille de groupes finis, les graphes de Cayley et les G-graphes nous permettre de construire de manière efficace et concise de grandes classes de graphes réguliers et creux (en limitant la taille de la partie génératrice du groupe). Ces deux "qualités", en plus de sa "quantité d'expansion", sont les caractéristiques les plus importantes dans la définition de graphe d'expansion. Quand on veut construire des graphes d'expansion via les graphes de Cayley, on regarde d'abord le cas le plus simple, les groupes cycliques, ou un peu plus général, les groupes abéliens, qui sont, par le théorème fondamental un produit direct des groupes cycliques. Malheureusement, il a été prouvé [53] qu'aucune famille de graphes de Cayley sur ces groupes ne donne une famille de graphes d'expansion. Cela est également le cas, comme nous le verrons pour les G-graphes Cayley et G-graphe expansion : Construction et comparaison Dans notre travail nous avons montrer que : Soit G un groupe fini et S ⊆ G. Notons S * = s∈S ⟨s⟩ \ {e} c'est à dire si S = {s 1 , . . . , s k }, List of tables xxv alors S * = {s 1 , . . . , s o(s 1 )-1 1 , . . . , s k , . . . , s o(s k )-1 k

Table 3

 3 Certains invariants de graphe de Cay(G, S

* ) et Φ(G, S). Nous avons |S * | = ∑ s∈S o(s) -|S|, donc tout sommet du niveau V s de Φ(G, S) a un degrés o(s)(|S| -1) avec |V s | = |G| o(s) . Ainsi, le degré de la plupart des sommets de Φ(G, S) est inférieur à |S * |. En d'autres termes, cela signifie que les G-graphes nous permettent de construire des graphes plus "clairsemés" que les graphes de Cayley Cay(G, S * ), et dans certains cas plus "clairsemés" que Cay(G, S), avec éventuellement des taux d'expansion plus petits. Premier résultat : famille infinie de G-graphes expansion sur le groupe linéaire spécial SL(2, Z/pZ) et sur le groupe projectif spécial linéaire PSL(2, Z/ pZ) En utilisant les résultats ci-dessus, une nouvelle famille infinie d'expansion G-graphes sur le groupe linéaire spécial SL(2, Z/pZ) et le groupe projectif spécial linéaire PSL(2, Z/pZ) sont construits. Ces familles sont pour la plupart formées des graphes irréguliers, en particulier semi-réguliers, qui sont à notre connaissance les premiers construits.

  Soit G le groupe projectif spécial linéaire, c'est G = PSL(2, Z/pZ). Dans les tableaux 4.2 et 4.3, nous comparons le nombre de sommets, le degré et le nombre d'arêtes des deux familles infinies des graphes de Cayley {Cay(

	1 0 1	, et soit P l'ensemble des nom-

bres premiers. Alors, les familles suivantes sont d'expansion : 1. Φ(PSL(2, Z/pZ); {S 2 , S 2 S 3 }), p ∈ P . List of tables xxvii 2. Φ(PSL(2, Z/pZ); {S 2 , S 2 2 , S 2 S 3 }), p ∈ P . 3. {Cay(PSL(2, Z/pZ); {S ±1 2 , S 2 S 3 , S -1 3 S -1 2 }), p ∈ P}. 4. Φ(PSL(2, Z/pZ); {S 2 , S 2 S 3 }), p ∈ P . 5. Φ(PSL(2, Z/pZ); {S 2 , S 2 2 , S 2 S 3 }), p ∈ P .

Table 4

 4

	xxviii

Quelques invariants de graphes de Cay(G, L * ) et Φ(G, L).

Table 5

 5

Quelques invariants de graphes de Cay(G,W * ) et Φ(G,W ). Nous avons le même résultat pour les familles suivantes, 1. { Φ(SL(2, Z/pZ); B i ), p ∈ P b i } pour tous 1 ≤ i ≤ 4, où P b i est un ensemble de nombres premiers et B

  Les plus importants sont ceux concernant les cliques principales, la régularité de G-graphes, et certains de leurs invariants de graphique comme le diamètre (voir Proposition 2.4.1, Théorème 2.4.5, et Lemme 4.3.1). Par exemple, dans le Chapitre 2, le nombre d'arêtes émises de chaque clique principale de Φ(G, S) est montré constant. Cela conduit à une nouvelle méthode pour vérifier si le G-graphe Φ(G, S) est simple. Plus précisément, il suffit de compter le nombre d'arêtes émises de n'importe quel clique principale C x où x ∈ G au lieu de calculer⟨s⟩ ∩ ⟨s

Cayley à partir d'un autre en commutant des arêtes spécifiques est présentée. Cela conduit à une nouvelle famille infinie d'expansion de graphes de Cayley sur le groupe projectif spécial linéaire PSL(2, Z/pZ).

Grâce à ce processus beaucoup de nouveaux résultats sont prouvés, principalement à propos des propriétés structurelles des G-graphes Φ(G, S) et Φ(G, S). ′ ⟩ pour tous

s ̸ = s ′ ∈ S.

Une connexion entre les graphes de Cayley et les G-graphes

Initialement, les graphes de Cayley ont été étudiés pour plusieurs raisons. En particulier, ces graphes sont considérés soit comme un outil efficace pour aborder des problèmes spécifiques dans la théorie des graphes comme la construction de graphes intégrale, expandeur et Ramanujan, ou pour leur propre intérêt, comme le calcul du spectre, le diamètre, l'Hamiltonicité des graphes de Cayley est également beaucoup étudiée (voir par exemple

[START_REF] Krebs | Expander Families and Cayley Graphs: A Beginner's Guide. EBSCO ebook academic collection[END_REF][START_REF] Witte | A survey: Hamiltonian cycles in Cayley graphs[END_REF]

).

Dans le chapitre 5, nous établissons une relation entre les graphes de Cayley et les G-graphes qui généralise celle présentée dans

[START_REF] Bretto | Cayley graphs and G-graphs: Some applications[END_REF]

. Cela nous donne la possibilité d'aborder certains problèmes ouverts dans la théorie des graphes de Cayley

[4,[START_REF] Badaoui | On a relationship between Cayley graphs and G-graphs and some applications[END_REF]

. Par exemple, dans de nombreux cas, et contrairement à de nombreuses familles de graphes de Cayley, l'évaluation des spectres des G-graphes correspondants est une tâche triviale, et vice-versa.

En utilisant ce fait et certains résultats dans la théorie spectrale des l'hypergraphes, nous présentons une nouvelle méthode pour calculer les valeurs propres de certains graphes de Cayley et des G-graphes. Une relation est prouvée entre certaines classes de graphes Cayley et les G-graphes. Soit Φ(G, S) un G-graphe, l'hypergraphe des cliques principales H(G, S) de Φ(G, S) est l'hypergraphe qui a le même ensemble de sommets que celui de Φ(G, S), t son ensemble d'hyper-arêtes est l'ensemble des cliques principales. Soit G un groupe, S un sous-ensemble non vide de G, et H = H(G, S) son hypergraphe des cliques principales, alors, 1. Φ(G, S) ≃ [H] 2 . 2. Cay(G, S * ) ≃ [H * ] 2 . 3. Cay(G, S * ) ≃ H l . 4. Φ(G, S) ≃ (H * ) l . Relation entre les spectres des graphes de Cayley et les G-graphes Soit H un t-uniforme r-régulier hypergraphe avec a sommet. a. Si t ≤ r, alors

  Une famille de graphe d-régulier{Γ i , i ∈ N + } est une famille d'expansion si λ 1 (Γ i ) - λ 2 (Γ i ) de n'importe quel graphe Γ i est supérieur ou égal à certains ε ∈ R + . • Soit G un groupe et S ⊂ G où o(s) = o(s ′ )pour tous s, s ′ ∈ S. Alors la famille des graphes de Cayley {Cay(G, S * ), i ∈ N + } est une famille d'expansion si et seulement si la famille de G-graphes { Φ(G, S), i ∈ N + } est une famille d'expansion. ) un graphe de Cayley, où |S| = k et o(s) = o(s ′ ) pour tous s, s ′ ∈ S. Si

	List of tables	xxxvii
	cette partie, nous traitons principalement de nouvelles approches pour calculer les spectres des graphes de Cayley. • Soit Cay(G, S Cay(G, S * ) est un graphe de Ramanujan alors
	À partir de la Section 3.2, nous obtenons la définition algébrique restreinte suivante des graphes d'expansion pour le cas du graphe régulier. k ≤ 4(O -1) -4 k < 4(O -1).
	Conclusion
	Comme nous l'avons vu, il existe des problèmes considérables à la construction d'une Comme nous l'avons vu précédemment, plusieurs nouvelles familles d'expansion sont famille d'expansion. La façon la plus courante est d'utiliser les graphes de Cayley et la construites sur le groupe linéaire spécial SL(2, Z/pZ)" et sur le groupe projectif spécial constante de Kazhdan correspondante, les raisons/avantages qui se cachent derrière un tel linéaire PSL(2, Z/pZ). Dans le résultat suivant, nous montrons que la condition suffisante choix sont expliqués dans le chapitre 3 et en section 1.5. Néanmoins, les techniques les plus dans le Théorème 4.3.3 est également satisfaite pour le cas régulier de G-graphes. évidentes dans cette direction ne fonctionnent pas, par exemple, le graphe de Cayley sur un 2, nous présentons un nouveau produit de graphes similaire à groupe abélien et le groupe de dièdral. Le problème de trouver une séquence de groupes qui celui du produit cartésien, que nous appelons le produit de remplacement généralisé. Les correspond à une famille d'expansion de graphes de Cayley a été considéré par de nombreux différentes propriétés de ce produit sont étudiées. Plusieurs nouvelles classes infinies de auteurs. Une grande quantité de recherches avec des résultats essentiellement négatifs a été graphes Cayley intégraux et d'autres sont construites en utilisant les G-graphes ou le produit publiée au cours des dernières décennies [42, 71]. de remplacement généralisé de deux graphes intégraux Γ △ Γ ′ . Par exemple les familles des Le graphe de Ramanujan Cette thèse donne différentes techniques algébriques et combinatoires pour aborder ce graphes de Cayley {Cay(G, S * Un graphe de Ramanujan est un graphe régulier dont le trou spectral (ou spectral gap) est problème particulier ainsi que d'autres problèmes liés. Dans le deuxième chapitre, nous 1 ), n ∈ N + } aussi grand que possible. Plus spécifiquement, un graphe d-régulier Γ avec n vertices est un continuons les études précédentes concernant les propriétés structurelles des G-graphes, ceci
	et sont des intégraux, où G = Z/nZ × Z/nZ, S 1 = {(1, 0), (0, 1)}, et S 2 = {(1, 0), (0, 1), (1, 1)}. {Cay(G, S * 2 ), n ∈ N + } Le même résultat est prouvé pour les familles suivantes. 1. {Cay(G, S * 1 ) △ Cay(G, S * 2 )/n, m ∈ N + }, 2. {Cay(G, S * 2 ) △ Cay(G, S * 1 )/n, m ∈ N + }, Ramanujan si max{λ 2 , |λ n |} ≤ 2 nous donne un point de départ pour étudier leurs propriétés/qualités d'expansion. Le qua-√ trième chapitre est consacré à l'étude du problème de la construction de familles d'expansion d -1. de Cayley et de G-graphes d'un point de vue combinatoire. De là, plusieurs nouvelles Une famille de degrés bornés de ces graphes est forme clairement grâce au Theorem 3.5.6 des familles de tels graphes sont présentées. excellents graphe d'expansion. Des exemples simples de graphes de Ramanujan incluent le Dans le cinquième chapitre, nous montrons des aspects clés de la théorie des hypergraphe graphe complet K n , le graphe bipartite complet K n,n et le graphe de Petersen. Quelques con-spectraux. Dans le dernier chapitre, les principales contributions aux différents problèmes ditions suffisantes pour que certains graphes de Cayley Ramanujan et G-graphes Ramanujan posés dans chaque chapitre sont présentées. En outre, nous discutons des recherches futures, sont données. à partir de ce qui a déjà été réalisé, et soulignons les résultats prévisibles possibles. Tout
	3. {Cay(G, S * 1 ) △ Cay(G, S * 1 )/n, m ∈ N + }, 4. {Cay(G, S * 2 ) △ Cay(G, S * cela démontre le fait que ces nouveaux graphes définis à partir de groupes, que sont G-• Soit G un groupe et S ⊂ G où o(s) = |S| pour tous s ∈ S. Alors le graphe de Cayley Cay(G, S * ) est un graphe de Ramanujan si et seulement si Φ(G, S) est aussi un graphe graphes, continueront à jouer un rôle clé dans les constructions futures de nouvelles familles 2 )/n, m ∈ N + }. de Ramanujan. d'expansion.
	Rappelons que K n , K n,n sont respectivement le graphe complet et le graphe bipartite complet. Nous avons le même résultat pour les familles suivantes, 1. {Cay(Z/nZ × Z/nZ, S * 1 ) △ K m /n, m ∈ N + }, • Soit Φ(G, S) un d-régulier G-graphe, où |G| = n et |S| = k. Si Φ(G, S) est un graphe de Ramanujan alors O ≤ 4(k -1) -4 O < 4(k -1).

• *

  The difference of B in A, denoted by A \ B, is the set of elements in A but not in B. That is, A \ B = {x/x ∈ A and x / ∈ B}. The complement of set A is the set of all elements that are not in A, that is, A = U \ A. Let S * = s∈S ⟨s⟩ \ {e}, that is if S = {s 1 , . . . , s k }, then S * = {s 1 , . . . , s

	o(s 1 )-1 1	, . . . , s k , . . . , s	o(s k )-1 k	}.

  Proposition 2.4.2. Let Φ(G, S) be a G-graph with S = {s 1 , . . . , s k }. Proposition 2.4.3. Let Φ(G, S) be a G-graph with S = {s 1 , ..., s k }. Then the number of edges inside any principal clique of Φ(G, S) is given by

	5 and Corollary 2.4.7 below). First, we start by the following two propositions which follow from the definition of G-graphs. Proposition 2.4.1. Let Φ(G, S) be a G-graph with S = {s 1 , . . . , s k }. Then the following are equivalent: i. Φ(G, S) is d-regular graph, ii. o(s d((s)x) k -1 , thus |V s | = |G| o(s) = |G|(k -1) d((s)x) , then o(s Then the following are equivalent: i. Φ(G, S) is d-regular graph, ii. o(s i ) = d k + 1 for all i ∈ {1, . . . , k}, 2 ∑ s i ∈S ∑ s j ∈S\{s i } | ⟨s i ⟩ ∩ s j |. Proof. The number of edges inside C x is 1 2 ∑ s i ∈S ∑ s j ∈S\{s i } | ⟨s i ⟩ x ∩ s j x|, iii. |V s 1 since {(s

i ) = d k -1 for all i ∈ {1, . . . , k}, iii. |V s i | = |V s j | for all i, j ∈ {1, . . . , k}.

Proof. Let (s)x ∈ V s , where s ∈ S. From Proposition 2.3.4, we have

d((s)x) = o(s)(k -1) or o(s) = i ) = o(s j ) if and only if |V s i | = |V s j | for all i, j ∈ {1, . . . , k}.

By Proposition 2.3.5, and using the same technique followed in the previous proposition, we obtain the following result for the G-graph Φ(G, S). i | = |V s j | for all i, j ∈ {1, . . . , k}.

Notation. When Φ(G, S) is a regular graph, we use the notation O instead of o(s) for any s ∈ S. i )x, (s j )x} is multi-edge of multiplicity p where p = ⟨s i ⟩ x ∩ s j x, then by Lemma 2.3.1 we have the result.

  and by Proposition 2.4.3 we have the first equality. Now if Φ(G, S) is a simple graph, by Corollary 2.3.2 we have | ⟨s i ⟩ ∩ s j | = 1. If Φ(G, S) is a regular graph, then by Proposition 2.4.1 we have o(s i ) = O for all i ∈ {1, . . . , k}. The first equality follows directly from Theorem 2.4.5. For the second inequality, note that the number E x of emanating edges from the principal clique C x is maximum when

	Corollary 2.4.6. Let Φ(G, S) be a G-graph with S = {s 1 , . . . , s k }, then s i ∈S ∑ s j ∈S\{s i } | ⟨s i ⟩ ∩ s j | is minimum. By Corollary 2.3.2, we directly have the result. Corollary 2.4.7. Let Φ(G, S) be a G-graph with S = {s 1 , . . . , s k }. Then Φ(G, S) is a simple graph if and only if E x = (k -1)( k ∑ i=1 o(s i ) -k) where x ∈ G. Proof. The sufficient condition follows directly from Theorem 2.4.5. Now if E x = (k -1. E ∑ 1)(

x = E y for all x, y ∈ G. That is the number of emanating edges from any two principal cliques in a G-graph Φ(G, S) are equal,

2. E x ≤ (k -1)(∑ k i=1 o(s i )k) for all x ∈ G. Proof. k ∑ i=1

o(s i )k), then again by Theorem 2.4.5 we have

Table 4 .

 4 1 Some graph invariants of Cay(G, S * ) and Φ(G, S). | (see also the remark after Theorem 4.5.6). In other words, this means that G-graphs enable us to construct sparser graphs than Cayley graphs Cay(G, S * ), and in some cases sparser than Cay(G, S), with possibly smaller expansion ratios (see the proof of Theorem 4.3.3).In this section, we use Theorem 4.3.3 to construct several infinite families of expander Ggraphs on the special linear group SL(2, Z/pZ). But first, we need the following proposition.Proposition 4.4.1. Let x i ∈ G i \ S i . If {Cay(G i , S i ), i ∈ N + } is an expander family, then {Cay(G i , S i ∪ x i ±1), i ∈ N + } is also an expander family.Proof. Since {Cay(G i , S i ), i ∈ N + } is an expander family, then there exists r ∈ N + such that |S i | ≤ r, for all i ∈ N + . Thus |S i ∪ x i ±1 | ≤ r + 2 for all i ∈ N + , so the second condition of Definition 3.2.4 is satisfied. Note that Cay(G i , S i ) is a spanning subgraph of Cay(G i , S i ∪x

	Note that |S * | = ∑ s∈S	o(s) -|S|, while every vertex in level V s of Φ(G, S) has degree
	o(s)(|S| -1) with |V s | = |S	|G| o(s)	. Thus, the degree of most vertices of Φ(G, S) is smaller than

*

  this section, we first present a new method to construct Cayley family {Cay(PSL(2, Z/pZ), S}); p ∈ P} by switching some edges in a specific way that preserves "expansion quality" and the density of the graph. This leads to a new infinite family of Cayley graphs in Subsection 4.5.2 (seeCorollary 4.5.4). Combining the presented results with Theorem 4.3.3 several other infinite families of expander G-graphs are presented on the projective special linear group PSL(2, Z/pZ).

  Example 15. Let (Z/nZ, +, 0) with n ≥ 10 and S = {±1, ±2}. Then Cay(Z/nZ, S) is a 4-regular graph on n vertices. Let H be a subgraph of Cay(Z/nZ, S) such that V (H) = From the definition of H 1 , we have |N s 1 s 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

	It is easy to see that: |∂ H(Cay(G, S))| = ∑ 1≤i≤k	|N s ±1 i	-1 i and |N s i (H)| = |N s -1 i (H)| and the proof is complete.	(H)|.

  2, we have the following two corollaries. Corollary 4.5.5. Let P be the set of all prime numbers, then {PSL(2, Z/pZ), p ∈ P} is a ❈❛②-expander family. Remark. The order of S 2 and S 2 S 3 are 4 and 3 respectively. Let L = {S 2 , S 2 S 3 } and W = {S 2 , S 2 2 , S 2 S 3 }, then we see that max{|L * |, |W * |} ≤ 7. Using Corollaries 4.4.2 and 4.5.4, we deduce that Cay(PSL(2, Z/pZ); L * }), p ∈ P and Cay(PSL(2, Z/pZ); W * }), p ∈ P are all expander families. Now by Theorem 4.3.3, we are able to directly construct several expander families of G-graphs.

	Corollary 4.5.4. Let P be the set of all prime numbers, then
	{Cay(PSL(2, Z/pZ); {S ±1 2 , S 2 S 3 , S -1 3 S -1 2 }), p ∈ P}
	is an expander family.

Table 4 .

 4 Let G be the projective special linear group, that is G = PSL(2, Z/pZ). In Tables 4.2 and 4.3, we compare the order, the degree, and the size of the two infinite expander families of Cayley graphs {Cay(G, L * ), i ∈ P} and {Cay(G,W * ), i ∈ P} with their corresponding G-graphs ones that are given in Theorem 4.5.6 by { Φ(G; L), i ∈ P} and { Φ(G;W ), i ∈ N + }. 2 Some graph invariants of Cay(G, L * ) and Φ(G, L).

	1 3 S -1 2 }), p ∈ P ,
	ii. Φ(PSL(2, Z/pZ); {S -1 2 , S 2 S 3 }), p ∈ P ,
	iii. Φ(PSL(2, Z/pZ); {S -1 2 , S -1 3 S -1 2 }), p ∈ P .

Table 4 .

 4 3 Some graph invariants of Cay(G,W * ) and Φ(G,W ).

  2 + r -t, . . . , λ a + r -t and -t with multiplicity rl t l, and thus the proof of the first part is complete. The second part is done similarly. Note that Theorem 5.2.4, where H is a 2-uniform hypergraph, follows Case1 of Theorem 5.2.7. The next Theorem is a direct result of Theorems 5.2.7 and 5.1.2.

  1) has eigenvalues λ 21 , λ 31 , ..., λ n 1 1 , λ 22 , λ 32 , ..., λ n 2 2 , ..., λ 2k , λ 3k , ..., λ n k k , γ 1 , γ 2 , ..., γ k

  or certain algebraic techniques (see Theorem 5.2.8). 2. Similar to the famous result on the Cayley graph, the G-graphs of an abelian group are shown that they can never yield a family of expander graphs (see Corollary 4.3.2). 3. In Chapter 4, a new method for constructing infinite families of expander G-graphs from the Cayley ones is presented. This technique enables us not only to construct expander families of d-regular graphs, but also regular and irregular ones in which the generated expander graphs are generally sparser than those of the original ones. (see e.g. the remarks after Corollary 4.3.5 and Table 4.1)

As we will see in Chapter 3, the degree of expansion goes by at least 8 different names (see the remark afterExample 10). In this study, we often refer to this concept by expansion ratio. The different names that it possess indicates its importance and ubiquitously.

This definition is due to[START_REF] Bretto | G-Graphs and Algebraic Hypergraphs[END_REF]

This can give the reader the intuition that G-graph may have in many cases relatively high connectivity. In particular, since each G-graph Φ(G, S) is formed of |S| maximal independent set that intersect any maximal clique in exactly one and only one vertex.

A family of groups yields an expander family of Cayley graphs means that Cayley graphs of this specific group family is an expander family. In this thesis, since we are dealing with another type of graphs that are defined from groups, the G-graphs, and in order to recognize the possible different results, we present in next chapter the notation of ❈❛②-expander and G-expander, which literally means yields an expander family of Cayley and G-graphs, respectively.

The vertices of the constructed expander families of G-graphs have in general smaller degree than those of Cayley graphs, and thus sparser, with possibly smaller expansion ratio (see the remarks after Corollary

4.3.5 and Theorem 4.5.6).

Acknowledgements I am deeply grateful to the people without whom this work would not have been possible. First of all, to my PhD thesis supervisors Alain Bretto and Bassam Mourad for their valuable support, advice and continuous guidance throughout my PhD study as well as for their patience, motivation and immense knowledge. I would like to thank Marc Demange and Faisal N. Abu-Khzam for their insightful comments and for kindly accepting to be the referees of my work. I thank Jean Paul Allouche, Isabelle Bloch, Etienne Grandjean and Amine El-Sahili for accepting to be members in the jury. I would like to thank Madam Arielle Perrette and Madam Abir Moukaddem for their valuable help as a part of the administrative body in GREYC and EDST. I would like to thank my fellow doctoral students for their feedback, cooperation and of course friendship. Special thanks to Abdelkader Ouali, Rafic Nader, and Kaoutar Ghazi for helping me organize my PhD defense. I would like to thank my two beloved sisters Zaina and Aminah, and my two dear brothers Ayad and Mahdi, for their tenderness and care. Last but not least, I send my deep appreciations to my loving parents mam and dad, for their endless encouragement and support.

Acknowledgements

Remark. Let Γ be a graph where its maximum and minimum degree is ∆ and δ , respectively. Hence, the following relation between its expansion ratio h(Γ) and its cheeger constant υ Γ follows directly from their definition,

Theorem 3.5.8. [START_REF] Chung | Spectral Graph Theory[END_REF] Let Γ be a graph with n vertices, then

where µ n-1 is the second smallest eigenvalue of the normalized Laplacian matrix L(Γ).

Remark. Note that both Cheeger's inequality presented in Theorems 3.5.6 and 3.5.8 are equivalent in the d-regular case. The first one is much more popular for the reason that most constructed expander families are indeed Cayley which are always regular graphs.

Alternative definitions : Vertex expansion and spectral gap

A useful equivalent to the expansion ratio h(Γ), is the vertex expansion constant, or h out (Γ), which is defined as follows,

where ∂ out F is the vertex boundary of F in the graph Γ, or the set of vertices emanating from the vertex set F to its complement.

Remark. Let Γ be a finite graph, it is easy to see that the expansion ratio h(Γ) and the vertex expansion constant h ′ (Γ) are related to each other by the following inequality,

Then, for a sequence of bounded degree graphs {Γ i , i ∈ N + }, the vertex and edge expansion are equivalent.

Spectral gap

Surprisingly, another definition of expander family comes from algebraic graph theory [START_REF] Nowak | Large Scale Geometry[END_REF]. Definition 3.5.9. A sequence of bounded degree graphs {Γ i , i ∈ N + } is expander family if the second smallest Laplacian eigenvalue of every graph µ |Γ i |-1 , or the spectral gap for the Example 14. For every i ∈ N + , let D 2i be the dihedral group:

In 2002, Rosenhouse [START_REF] Rosenhouse | Isoperimetric numbers of cayley graphs arising from generalized dihedral groups[END_REF] showed that h(Cay

In fact, it was shown later (see [START_REF] Krebs | Expander Families and Cayley Graphs: A Beginner's Guide. EBSCO ebook academic collection[END_REF]) that for any set of generator S i of D 2i , {Cay(D 2i , S i ), i ∈ N + } is not an expander family. Thus {D 2i , i ∈ N + } is not a ❈❛②-expander family.

Remark. Many similar results are proved for several other families of groups. A wellknown result in this direction states that no family of abelian groups is a ❈❛②-expander (see Corollary 4.26 in [50]). In Corollary 4.3.2, we prove a similar result for the G-expander case.

Construction of G-graph expanders: The technique and more

In this section, we mainly focus on two directions. The first is concerned with proving that G-graphs on an abelian group as in the Cayley graphs case, can not produce a family of expander graphs. In Subsection 4.3.2, we establish a relation between certain expander families of Cayley graphs and G-graphs. This relation will pave our way to construct many new infinite families of expander graphs on the special linear group SL(2, Z/pZ) group in Section 4.4, and on the projective special linear group PSL(2, Z/pZ) in Section 4.5.

Abelian groups are never G-expanders: A simple proof

From Chapter 1, the reader should be familiar with some common families of finite groups, for instance, the dihedral group, the dicyclic group, the special linear group, and so on. If we consider a family of finite groups, Cayley graphs allow us to construct in an effective and concise way large classes of regular and sparse graphs (when limiting the size of the generating set). These two graph qualities, in addition to its "expansion quantity", are the most important characteristics in the common definition of expander. When thinking about constructing expanders via Cayley graphs, it is logical to look first at the simplest case that is the cyclic group, or a little bit more general, the abelian groups, which are by the fundamental theorem of abelian groups, a direct product of cyclic groups. Unfortunately, it was proved [START_REF] Lubotzky | Groups and Expanders[END_REF] that Cayley graphs of finite abelian groups have logarithmic diameter growth, and hence by Proposition 3.5.2 no family of abelian groups is a ❈❛②-expander (see also [START_REF] Rogawski | Discrete Groups, Expanding Graphs and Invariant Measures[END_REF]). Before we prove this well-known result for the G-expander case, we need the following lemma.

3 S -1 2 }, and A 4 = {S ±1 2 , S 3 S 2 , S -1 2 S -1 3 }. There exist sets P a i of prime numbers such that {Cay(SL(2, Z/pZ); A i ), p ∈ P a i } is an expander family for all 1 ≤ i ≤ 4.

Let B 1 = {S 1 , S 1 S 3 }, by Corollaries 4.4.2 and 4.4.4 we directly deduce that there exists a set P ′ of prime numbers such that {Cay(SL(2, Z/pZ); B * 1 ), p ∈ P ′ } is an expander family. Using Theorem 4.3.3, we deduce that { Φ(SL(2, Z/pZ); B 1 ), p ∈ P ′ } is an expander family. By the same analogy, we obtain the followings.

1 , then we conclude:

By a similar fashion we conclude the following:

Similarly, we have the following.

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

}) respectively. By Lemma 4.5.1, we have: and, (1)

Let

ii. And if s 1 y ∈ H, then s 1 s 2 x ∈ H.

Let H 1 and H 2 be the set of vertices of H defined as follows:

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

From the definition of H 2 , we have

Thus we have

may be not isomorphic. An example of such a situation is given by the dihedral group D 2i which is defined earlier as follows:

Clearly, the 3-regular Cay(D 2i , {s ±1 1 , s ±1 2 }) is not isomorphic to the 2-regular graph Cay(D 2i , {s ±1 1 ,

Direct applications 2: Some expander families of G-graphs on the group

In this subsection, we combine the results presented in Subsection 4.5.

and the proof is completed.

The set S is independent by triples if for all s 1 , s 2 , s 3 ∈ S such that s a 1 1 s a 2 2 s a 3 3 = e we have a i = 0 mod o(si), i = 1, 2, 3. In [START_REF] Culus | About some robustness and complexity properties of G-graphs networks[END_REF] and [START_REF] Tomanová | A note on orbit graphs of finite groups and colour-clique graphs of Cayley graphs[END_REF] and by using different approaches the authors presents versions of the above result when S is independent by triples, or when the corresponding G-graph is simple (see e.g. Proposition 22 in [START_REF] Culus | About some robustness and complexity properties of G-graphs networks[END_REF] and Theorem 1 in [START_REF] Tomanová | A note on orbit graphs of finite groups and colour-clique graphs of Cayley graphs[END_REF]).

Here we choose to approach the problem from hypergraph theory point of view.

Remarks.

Corollary 5.2.2. Let Φ(G, S) be a d-regular G-graph, then P( Φ(G, S), λ ) = P(Cay(G, S * ) l , λ ) Corollary 5.2.3. (Corollary 6.17 in [START_REF] Bapat | Graphs and Matrices[END_REF]) Let Γ be a graph. If λ is an eigenvalue of Γ l then -2 ≤ λ . Theorem 5.2.4. (Theorem 6.18 in [START_REF] Bapat | Graphs and Matrices[END_REF]) Let Γ be a r-regular graph with a vertices. Then

Remark Let us first prove the following lemma which presents a relation between the adjacency matrices of a hypergraph, of a line graph with the incidence matrix. Proof. Note that the (i, j)-entry of M ′ M is obtained by taking the inner product of the i th column c i and the j th column c j of M ′ M. It is easy to see that c i .c j = O if c i = c j and c i .c j is equal to the number of common vertices between there corresponding hyperedges edges, then M ′ M = B + OI n . By the same analogy, we obtain the second result. Proof. Let B be the adjacency matrix of H l . By Lemma 5.2.5, we know M ′ M is a positive semidefinite matrix, then its eigenvalues must be nonnegative. If λ is an eigenvalue of H l , then by Proposition 1.4.4 we have 0 ≤ λ + O. Theorem 5.2.7. Let H be a r-regular t-uniform hypergraph with a vertices. If t ≤ r, then P(H l , λ ) = (λ + t) a( r t -1) P(H, λ + tr).

If r ≤ t, then P(H, λ ) = (λ + r) a(1-r t ) P(H l , λ + rt).

Proof. Let u = (1, 0), v = (0, 1), and w = (1, 1). Then the vertices of the levels of Φ(G, S) are

V v = {{(0, 1), (0, 1), . . . , (0, n -1), . . . , {(n -1, 0), (n -1, 1), . . . , (n -1, n -1)}}, V w = {{(0, 0), (1, 1), . . . , (n -1, n -1), . . . , u n-1 = {(n -1, 0), (0, 1), . . . , (n -2, n -1)}}.

Note that each vertex u ∈ V s is connected to every v ∈ u ∈ V s ′ for all s ̸ = s ′ ∈ S, hence Φ(G, S) is isomorphic to K n,n,n . Using Proposition 1.4.2, we have:

We Theorem 5.4.9. Let Γ be a graph on n vertices v 1 , ..., v n . For each i = 1, 2, ..., n, let Γ j be a d j -regular graph on n j vertices. Then the spectrum of Γ △ (Γ 1 , ..., Γ n ) is given by:

Proof. Recall that since Γ j is d j -regular on n j vertices, then d j is an eigenvalue of Γ j associated to its unit eigenvector u = 1 √ n j (1, . . . , 1). In the matrix B of (1) as well as in B of (2), we let ρ j j = 0 for all 1 ≤ j ≤ n and for all 1 ≤ i, j ≤ n with i ̸ = j if v i is adjacent to v j , let ρ i j =

√ n i n j and in the opposite case (i.e. when v i is not adjacent to v j ) we let ρ i j = 0. Now with this in mind, it suffices to notice that this choices of the ρ i j insures that in this case B is the adjacency matrix of Γ △ (Γ 1 , ..., Γ n ), and then the proof is complete in view of the preceding Theorem. Proof. Recall first that A(Γ) denotes the adjacency matrix of Γ. Then the adjacency matrix of Γ △ Γ ′ is obtained from the matrix B of (1) as follows. First replacing its diagonal blocks by A(Γ), P 2 A(Γ)P T 2 , ..., P n A(Γ)P T n for some permutation matrices P 2 , ..., P n and then taking ρ j j = 0 for all 1 ≤ j ≤ n and for all 1 ≤ i, j ≤ n with i ̸ = j if v i is adjacent to v j , we take ρ i j = √ n 2 = n and in the opposite case, we set ρ i j = 0. By noticing that in this case B = dI m + nA(Γ), then the proof is complete.

From the preceding corollary, we get the following.

Expander graphs

In the literature, the families of expander graphs can be defined in different ways, all these definitions turn out to be equivalent by Cheeger inequality given in Theorem 3.5.6. In this chapter, since we are mainly dealing with new approaches to compute the spectra of Cayley graphs, then we will stick with the algebraic point of view for expanders. From Section 3.2, we obtain the following restricted algebraic definition of expanders for the regular graph case.

Definition 5.7.1. A family of d-regular graphs {Γ i , i ∈ N + } is an expander family if the spectral gap λ 1 (Γ i ) -λ 2 (Γ i ) of any graph Γ i is greater than or equal to some ε ∈ R + .

As we have seen together in Sections 4.4 and 4.5, several new expander families are constructed on the special linear group SL(2, Z/pZ) group, and on the projective special linear group PSL(2, Z/pZ). In the following proposition, we show that the sufficient condition in Theorem 4.3.3 is also satisfied for the regular G-graph case.

Proposition 5.7.2. Let G be a group and S ⊂ G such that o(s) = o(s ′ ) for all s, s ′ ∈ S. Then the family of Cayley graphs {Cay(G, S * ), i ∈ N + } is an expander family if and only if the family of G-graphs { Φ(G, S), i ∈ N + } is an expander family.

Proof. The result follows directly from Definition 5.7.1 and Theorem 5.2.8.

Ramanujan graphs

A Ramanujan graph is a regular graph whose spectral gap is almost as large as possible. A bounded degree family of these graphs is clearly composed by Theorem 3.5.6 of excellent spectral expanders. Simple examples of Ramanujan graphs include the complete graph K n , the complete bipartite graph K n,n , and the Petersen graph. In the following, we present a sufficient condition for certain Cayley graphs and G-graphs to be Ramanujan graph. Proof. Followed by Theorem 5.5.5 and easy computation. Proof. Followed by Theorem 5.5.7 and easy computation.

Final thoughts and notes

In this chapter, a new method for computing the spectra of certain Cayley graphs is presented. This leads us in Sections 5.5 and 5.6 to construct new families of integral and strongly regular Cayley graphs. Our main results lie in establishing a link between Cayley graphs and G-graphs, also between their spectra (see Theorems 5.1.2 and 5.2.8). Then, the theory of G-graphs enables us to calculate the spectra of certain Cayley graphs. In Theorem 5.2.7 we present a relation between the spectrum of hypergraph and its line graph for the regular uniform case which allows us in Theorem 5.2.8 to give a relation between the spectrum of the Cayley graph Cay(G, S * ) and the G-graph Φ(G, S). Consequently, this last result can be improved if Theorem 5.2.8 can be generalized to the irregular non-uniform case.