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)?

$\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
    Apr 25 '16 at 0:37
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

$\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$ Apr 24 '16 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
    Apr 26 '16 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.