Given a subgraph $H$ of a general Cayley graph Cay($G$,$S$), is there a bound on the number of edges in H dependent only on the sizes $|H|, |S|,$ and $|G|$?

As an example, consider the graph $H_n=Cay(S(2,n),C)$, where S(2,n) is the hyperoctahedral group, and $C$ is the generator set consisting of cycles (when $S(2,n)$ is viewed as the signed symmetric group). I am interested in finding subgraphs of $H_n$ which are isomorphic to the Birkhoff graph $B_n=Cay(S_n,C)$. I was surprised to learn for n=3 that no such subgraph exists due to the fact that any subgraph of size $6$ in $H_3$ has at most $9$ edges (rather than the requisite $15$). I would like to generalize this result, but have not had much success, and the above question seems like the most natural way to approach it.

  • 2
    $\begingroup$ This question seems to general - the complete graphs are Cayley graphs. $\endgroup$ – Chris Godsil Apr 1 '18 at 21:46
  • 1
    $\begingroup$ Cayley graphs are $|S|$-regular. So a subgraph $H$ of a Cayley graph has at most $\frac{1}{2} |H| \cdot |S|$ edges. As Chris Godsil pointed out, complete graphs are Cayley graphs, so this bound may not get you much. $\endgroup$ – ml0105 Apr 1 '18 at 22:10
  • $\begingroup$ @ChrisGodsil Good catch, I meant to say on the size of $|H|$, $|S|$, and $|G|$--so the complete graph is simply the case where $|S| = |G|-1$. Edited to reflect this mistake $\endgroup$ – Max Hopkins Apr 2 '18 at 2:02
  • 1
    $\begingroup$ Take $k \in [n/2 + 1, n-1]$ to be an even integer, and consider the $k$-distance graph of the hypercube $Q_{n}$. This is a Cayley graph, with the underlying group $\mathbb{F}_{2}^{n}$. The generating set $S = C_{n, k}$, the set of $k$-bit strings in $\mathbb{F}_{2}^{n}$. Now the graph has two disjoint components: the component of even vectors and the component of odd vectors. Taking one of these components, we achieve the bound of $\frac{1}{2}|H| \cdot |S|$. In fact, this provides an infinite family satisfying that bound with equality. $\endgroup$ – ml0105 Apr 2 '18 at 2:15
  • 1
    $\begingroup$ This example actually comes from @ChrisGodsil's paper on Graph Homomorphisms via Vector Colorings. $\endgroup$ – ml0105 Apr 2 '18 at 2:18

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.