Expander cayley graphs pdf

A beginners guide is a comprehensive introduction to expander graphs, designed to act as a bridge between classroom study and active research in the field of expanders. Iterative construction of cayley expander graphs thus the iteration process need only be provided with an initial. Hypergraph expanders from cayley graphs david conlon abstract we present a simple mechanism, which can be randomised, for constructing sparse 3uniform hypergraphs with strong expansion properties. Then we will see why abelian groups do not yield expander families of graph. It is therefore related to the books of lubotzky 74 and his colloquium lectures 75, of sarnak. This material is based upon work supported by the national science foundation under grants no.

Lecture notes on graph partitioning, expanders and. The replacement product and semidirect product 531 11. Finally, we will state alonboppana theorem and will understand the proof,and will show why ramanujan graphs with regularity greater than three turns out to be expander graphs. Cayley graphs of groups and their applications by anna m. A disconnected graph is not an expander, since the boundary of a connected component is empty. Most notably, this is the case with the ramanujan graphs. Ebook pdf ebook expander families and cayley graphs. A beginners guide, by mike krebs, anthony shaheen book right here, you will get some advantages not to opt for the book store. This is your time and your serenity to obtain all that you desire from this book expander families and cayley graphs. Most of the information found here is taken from john meiers, groups graphs and trees, 1. Kazhdan constant and expansion of cayley graphs 529 11. Its vertex set is the unit group of a finite extension of a finite local ring r and its adjacency. By downloading the online expander families and cayley graphs. Spectral graph theory, expanders, and ramanujan graphs christopher williamson 2014 abstract we will introduce spectral graph theory by seeing the value of studying the eigenvalues of.

An expander graph is a sparse graph that has strong connectivity properties, quanti ed using vertex, edge or spectral expansion. Lecture notes on graph partitioning, expanders and spectral. An expander is a sparse graph with the property that every small vertex subset expands, that is, is adjacent to many vertices outside of the set. This is the graph that has the elements of gas vertices and two elements g. On expander cayley graphs from galois rings request pdf. Quantum expanders from any classical cayley graph expander. In this work, we define and study the algebraic cayley directed graph over a finite local ring.

We will give various examples, such as cayley graphs, which are expanders. We survey some of the known results on eigenvalues of cayley graphs and their applications, together with related results on eigenvalues of cayley digraphs and generalizations of cayley graphs. A graph his called a c expander if for every set of vertices s, j sjcjsj1 j sjjhj, where s is the set of all neighbours of s. Constructing expander families by iterated semidirect. A major consideration we had in writing this survey was to make it accessible to mathematicians as. However in order to do so it is useful to have some understanding of the analogous spectral notions of amenability and kazhdan property t which are important for in nite groups. Expander graphs have many interesting applications in communication networks and other areas, and thus these graphs have been extensively studied in theoretic computer sciences and in applied. We then discuss biased distributions, which we use to construct cayley graphs which are good expanders. Cayley graphs do not form an expander family, even though the degree of these graphs goes to in. We present a simple mechanism, which can be randomised, for constructing sparse 3. We present a simple mechanism, which can be randomised, for constructing sparse 3uniform hypergraphs with strong expansion properties.

Informally, a graph is a good expander if it has low. Cayley graphs abstract there are frequent occasions for which graphs with a lot of symmetry are required. I want to ask the question in two parts, 1 is there some fundamental distinguishing property between abelian and nonabelian cayley graphs. Most of the information found here is taken from john meiers. Thus one can generate larger cayley expanders of small degree from smaller ones. For knot of this form it is an interesting question as to whether ramanujan graphs exist. A beginners guide is a comprehensive introduction to expander graphs, designed to act as a bridge between classroom study and active research in. First we prove that they are expander graphs by using. Citeseerx document details isaac councill, lee giles, pradeep teregowda. Then, we will learn about applications to the study of expanders and. This result is very relevant to the novikov and baumconnes conjectures since it might give counterexamples to refute these conjectures. In what follows we are concerned with using group theoretic methods to construct expander graphs, so we dont really care about all the extra structure that comes with a cayley graph. Pdf on some expander graphs and algebraic cayley graphs. An introduction to expander graphs a report submitted in partial ful llment of the requirements for the award of the dual degree of bachelor of sciencemaster of science in.

The complete graph has the best expansion property, but it has largest possible degree. Luca trevisan c 2011, 20, 2014 by luca trevisan this work is licensed under the creative commons attributionnoncommercialnoderivs 3. Hypergraph expanders from cayley graphs david conlon abstract we present a simple mechanism, which can be randomised, for constructing sparse 3uniform hypergraphs with. Abstract we construct a sequence of groups gn, and explicit sets of generators yn.

An introduction to expander graphs people eth zurich. However, unlike the case of unstructured graphs, the restrictions on generators alluded to above for applying the zigzag product on cayley graphs, make iterations a highly nontrivial and illuminating task. Representations and irreducible representations 526 11. A huge amount of research has been devoted to them in the computer science literature in the last four decades.

Expander graphs are highly connected sparse finite graphs. The third section connects eigenvalues of a cayley graph to representation theory, with a view towards. Hypergraph expanders of all uniformities from cayley graphs. Cayley graph, one can obtain a sequence of expander cayley graphs via an iterative process using the zigzag theorem. Uniform expansion bounds for cayley graphs of sl 2fp 629 is a consequence of our graph being connected that is, of s p generating all of sl 2f p.

Ramanujan graphs, graphs with optimal spectal properties. More precisely, the zigzag product of two cayley graphs, with certain important restrictions on the structure of their generating sets, is a cayley graph of the semidirect product of the associated groups. Constructing expander families by iterated semidirect products 533 11. The goal of this book is to give an introduction to expander graphs and their applications. Later, the paper by alon, lubotzky, and wigderson 1 related this idea to cayley graphs by showing that under. Spectral graph theory, expanders, and ramanujan graphs. We give a simple recipe for translating walks on cayley graphs of a group g into a quantum operation on any irrep of g. Spectral graph theory, expanders, and ramanujan graphs christopher williamson 2014 abstract we will introduce spectral graph theory by seeing the value of studying the eigenvalues of various matrices associated with a graph.

Lecture notes on expansion, sparsest cut, and spectral. Each of these is a wonderful source of information, but we. Most properties of the classical walk carry over to the. Their expansion properties, which are derived from the underlying cayley graphs, include. A graph his called a cexpander if for every set of vertices s, j sjcjsj1 j sjjhj, where s is the set of all. However in order to do so it is useful to have some understanding of the analogous spectral notions of amenability and kazhdan property. Tripi abstract cayley graphs are graphs associated. One such family of graphs is constructed using groups.

Many explicit constructions of expander graphs are obtained as cayley graphs of a family of nite groups. These notes are a lightly edited revision of notes written for the course \graph partitioning, expanders and spectral methods o ered at o ered at u. It is therefore related to the books of lubotzky 74 and his colloquium lectures 75, of sarnak 96, and of tao 104, and to the detailed survey of hoory, linial and wigderson 51. A classical cayley graph expander on a group g with gap 1.

In what follows we are concerned with using group theoretic methods to construct expander graphs. T are isomorphic, but they are distinguished via the labels. In fact one important aspect of asymptotic group theory the part of group theory concerned with studying the. Representation theory and eigenvalues of cayley graphs. We survey some of the known results on eigenvalues of cayley graphs and their applications, together with related results on eigenvalues of cayley digraphs and generalizations of cayley. Hypergraph expanders from cayley graphs springerlink. Request pdf on expander cayley graphs from galois rings in this paper, we study new cayley graphs over the additive group of galois rings. The algorithmic problem of finding a small balanced cut in a graph that is, of finding a certificate that a graph is not an expander is a fundamental problem in the area of approximation algorithms, and good algorithms for it have many applications, from doing. Lecture notes on expansion, sparsest cut, and spectral graph. Cayley graphs of groups and their applications mathematics missouri state university, august 2017 master of science anna m. Limor friedman in this lecture we introduce cayley graphs and examine some of their spectral properties.

We begin by introducing the requisite background information in the subjects of graph theory and cryptography. These hypergraphs are constructed using cayley graphs over zt 2 and have vertex degree which is polylogarithmic in the number of vertices. Expander graphs, the subject of these notes, are certain families of graphs, becoming larger and larger, which have the following two competing properties. By selbergs theorem g p 1 and g2p are families of expander graphs. This property can be viewed from several di erent angles. Iterative construction of cayley expander graphs eyal rozenman aner shalevy avi wigdersonz.

Expander graphs and explicit constructions semantic scholar. Tripi a masters thesis submitted to the graduate college of missouri state university in partial ful llment of the requirements for the degree of master of science, mathematics july 2017 approved. In 24 shalom gave an example of in niteindex subgroup in psl 2z. Using the relative property t of the pair sl 2r r2,r2 for. It is obvious that any c expander for some xed c0 has a logarithmic diameter, but the converse does not hold, as shown, for. Well often abuse nomenclature slightly, and just refer to the expander g j, or even just g, omitting explicit mention of the entire family of graphs. Expander graphs expander graphs are highly connected sparse graphs. Most properties of the classical walk carry over to the quantum operation. Lecture notes on graph partitioning, expanders and spectral methods luca trevisan university of california, berkeley. A beginners guide, by mike krebs, anthony shaheen prepares to delight in reading. Currently, your expander families and cayley graphs. The mathematics of expander graphs is studied by three distinct communities. Expander graphs are highly connected sparse nite graphs which play a basic role in various areas of computer science. We also establish the existence of expander graphs, and demonstrate some algebraic properties that are necessary conditions for groups to have cayley graphs that are expanders.