MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 2 down vote accepted

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))}$.)

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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