# Bound on number of edges on subgraphs of Cayley graphs

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.

• This question seems to general - the complete graphs are Cayley graphs. – Chris Godsil Apr 1 '18 at 21:46
• 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. – ml0105 Apr 1 '18 at 22:10
• @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 – Max Hopkins Apr 2 '18 at 2:02
• 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. – ml0105 Apr 2 '18 at 2:15
• This example actually comes from @ChrisGodsil's paper on Graph Homomorphisms via Vector Colorings. – ml0105 Apr 2 '18 at 2:18