# Conditions for subgraph relationship in circulant Cayley digraphs

I have two circulant Cayley digraphs: that is, Cayley digraphs X = Cay(ℤ/mS) and Y = Cay(ℤ/nT), for odd integers m < n, and sets with sizes |S| = (m − 1)/2, and |T| = (n − 1)/2.

These digraphs are antisymmetric, in that S is disjoint from −S, and T is disjoint from −T. (It follows that for each distinct pair of vertices a,b in either graph, there is either an arc from a to b, or vice versa.)

Question. What conditions on m, n, S, and T must hold for X to be an induced directed subgraph of Y?

-

I very much doubt that there is a nice answer for this. I suspect that this question is not essentially easier than the more general problem, where we allow $X$ to be any tournament. If $n$ is a prime congruent to 3 mod 4 and $T$ is the set of non-zero squares in $\mathbb{Z}/n$, the Cayley graph $Y$ is the Paley tournament. It follows from an old result of Graham and Spencer that any smallish tournament is an induced directed subgraph of $Y$. (Here smallish'' is technical term that means something like $\log(n)$, or perhaps $\sqrt{(\log(n))}$.)

-
Thanks for reminding me of the term 'tournament' (and 'Payley tournament' in particular). In fact, I was hoping to show an upper bound stronger than m for the size of the cliques in the [symmetrized version of the] tensor product of the Paley tournaments on m and n. I was trying to do this by getting a handle on induced subgraphs of the Paley tournaments on the non-zero quadratic residues, which led me to the question above. However, your final comment suffices to show that the stronger bound I seek is impossible. –  Niel de Beaudrap May 19 '10 at 20:39