1
$\begingroup$

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?

$\endgroup$

1 Answer 1

3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ May 19, 2010 at 20:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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