1
$\begingroup$

I have two circulant Cayley digraphs: that is, Cayley digraphs X = Cay(ℤ/m, S) and Y = Cay(ℤ/n, T), 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?

Improve this question
$\endgroup$

1 Answer 1

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

Improve this answer
$\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$
    – Niel de Beaudrap
    Commented May 19, 2010 at 20:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .