4
$\begingroup$

When I search about expander graphs in google I see a lot of articles about expander Cayley graphs. Now my questions are as follows:

Are all expander regular graphs are Cayley, or there is a special case of connected prime-order expander regular graphs which are not Cayley (specially graphs that constructed from disjoint cycles)?

Improve this question
$\endgroup$
1
  • 4
    $\begingroup$ If we take an infinite family of finite quotients of $G=SL_3(\mathbf{Z})$, we get expander graphs (which are Cayley). If we fix a finite subgroup $F$ of $G$, and we mod out these by $F$, it sounds likely that we get non-Cayley examples (even with $F$ of order 2); possibly these are even not vertex-transitive graphs. $\endgroup$
    – YCor
    Commented Apr 25, 2016 at 0:37

2 Answers 2

Reset to default
5
$\begingroup$

The first existence proof (due to Mark Pinsker, in 1973) for expanders relied on the probabilistic method. As such these expanders are (with probability one) not Cayley graphs.

https://en.wikipedia.org/wiki/Mark_Semenovich_Pinsker

Improve this answer
$\endgroup$
2
  • $\begingroup$ Can you give me a reference? I saw this link and I couldn't see any detail about my question in it. $\endgroup$
    – Meysam Ghahramani
    Commented Apr 24, 2016 at 19:44
  • $\begingroup$ See, for example, pages 5 and 6 of Lubotzky's book "Discrete groups, expanding graphs, and invariant measures". $\endgroup$
    – Sam Nead
    Commented Apr 26, 2016 at 16:51
2
$\begingroup$

The answer to your question is yes. The existence of such expanders which proved by probabilistic method, give us an optimistic view for search to find non-Cayley expanders. But, a first class of such graphs are $k$-regular bipartite which has some parallel edges. So, for your question these are not interesting. There is a general method which you can use for construction non-Cayley expander from an other family of expanders. The only key in this way, is preserving the below bound for the Cheeger constant. For more results and updated things, you can see these two resources, specially the section 3.1 of the second one:

1) Expander graphs, E. Kowalski, ETH Zurich – Spring Semester 2016 Version of February 24, 2016 2) Expander Graphs and Explicit Constructions, Angeliki Lountzi, U.U.D.M. Project Report 2015.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .