The question is not strictly well-defined. But it goes like this:

Could you find an infinite family of graphs $G_i$, that are all $\epsilon$-expanders, but have many 4-cycles?

$\epsilon$ should be as large as possible as well as the number of 4-cycles. The family of graphs should be as wide as possible.

This is the basic question.

A trivial good example would be a cartesian graph product $G \times H$. The expansion of the product is the maximal $\epsilon$ of the involved graphs. If we take two $d$-regular graphs and we look at 2 paths of the product, then about $1/3$ of the paths are in $4$-cycle.

But could it be improved? Could the relation be bounded?

If we think in terms of Cayley graphs:

Say our graph is $\mathrm{Cay}(G,S)$ and $S$ is symmetric. A $4$-cycle arises from $4$ generators $a,b,c,d$ s.t. $ab=cd$. It is trivial if either ($c=b$ and $d=a$) or ($c=a$ and $d=b$).

I think many trivial cycles would harm expansion since, by Alon-Roichman theorem, abelian groups are bad expanders.

So I think the goal should be to find groups and generator sets that have many non-trivial 4-cycles.

  • 1
    $\begingroup$ What if you just consider a family of good expanders and add to them additional edges which form 4-cycles (in such a way that you still get $k$-regular graphs with slightly larger $k$)? $\endgroup$ – Mikhail Ostrovskii Jul 7 '19 at 2:13
  • $\begingroup$ Yes, this would work. Obvious, but didn't occur to me. Thanks. I guess it would keep you bounded degree too. The price is higher degree. And yet, I am looking for cases in which it occurs naturally. Suppose you start from Cayley graphs. The idea of adding edges this way is not natural. Does it happen naturally in the skeleton of Ramanujan complex? In some groups? Under some nice product? $\endgroup$ – user2679290 Jul 7 '19 at 6:04
  • 1
    $\begingroup$ Take an expanding 4-regular graph and replace each vertex by a 4-cycle. You get an expanding 3-regular graph with a linear number of 4-cycles. $\endgroup$ – Brendan McKay Jul 7 '19 at 12:09

Your Answer

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

Browse other questions tagged or ask your own question.