I am trying to apply the main theorem of this paper to a certain kind of graph and keep getting confused. The theorem uses $$rank(Aut\Gamma)$$ which is defined as "the number of $$Aut \Gamma$$ orbits on the set $$V(\Gamma) \times V(\Gamma)$$". ($$\Gamma$$ is a graph).

Now, my graph $$\Gamma$$ is built in this way: take a clique of $$c$$ vertices, labelled $$\{1,2,\ldots,c\}$$ and add $$s=\binom{c-1}{2}$$ additional vertices, each of which is connected to a different pair of two vertices from $$\{2,\ldots,c\}$$.

Question: What is $$rank(Aut\Gamma)$$?

My answer is 9 because the automorphism group is (apparently) $$S_{c-1} \times S_{s}$$ and there are 3 orbits for it. However, when I plug 9 into the theorem I get a contradiction with the rest of it (which involves objects I have a better grasp of so I am pretty sure I got the rest right).

Therefore, I suspect that my answer to the above question is wrong and I am in dire need of some enlightenment.

EDIT: Let's assume $$c \geq 4$$ to rule out sporadic cases.

• You count three orbits of the group on $V(\Gamma)$. And on $V(\Gamma)\times V(\Gamma)$? Dec 24, 2012 at 15:38
• Unless I misunderstood the description of the graphs, your automorphism group seems to be wrong, for example when $c=3$, the automorphism group of $\Gamma$ is $S_2\times S_2$, not $S_2\times S_1$ as your formula posits and for $c\geq 4$, the automorphism group seems to be just $S_{c-1}$. Dec 24, 2012 at 15:49
• @Mariano: Like I said, I get 9, but it seems to be wrong... Dec 24, 2012 at 15:56
• I don't understand why you say that «you count 3 orbits but you plug in $9$». Dec 24, 2012 at 15:59
• @ARupinski: Let's assume $c \geq 4$ (I'll update the question too). Dec 24, 2012 at 16:02

The automorphism group of this graph is $S_{c-1}$. Note that the vertex 1 in your clique cannot be moved anywhere (look at the degrees). On the other hand, a permutation of the remaining vertices in {2,...,c} induces a permutation on these $s$ vertices $P$. The 14 orbitals (aka orbits on $V\times V$) are as follows:

1. {(1,1)}
2. {(x,x) | x in {2..c}}
3. {(p,p) | p in P}
4. {(x,y) | x,y in {2..c}, x not equal to y}
5. {(p,q) | p,q in P, the corresponding pairs of elements of {2..c} do not intersect}
6. {(p,q) | p,q in P, the corresponding pairs of elements of {2..c} intersect in one element}
7. {(1,x) | x in {2..c}}
8. {(x,1) | x in {2..c}}
9. {(1,p) | p in P}
10. {(p,1) | p in P}
11. {(x,p) | x in {2..c}, p in P, x in p}
12. {(p,x) | x in {2..c}, p in P, x in p}
13. {(x,p) | x in {2..c}, p in P, x not in p}
14. {(p,x) | x in {2..c}, p in P, x not in p}

First, let me point out that I think ARupinski is right and $\rm{Aut}(\Gamma)$ is simply $S_{c-1}$. (This could be relevant.)

Next, note that there are at least 11 orbits on $V(\Gamma)\times V(\Gamma)$.

There is an obvious partition into 9 parts (coming from the 3 orbits on $V(\Gamma)$) each belonging to a different orbit, but 2 of these split into two orbits, a diagonal part and a non-diagonal part.

For example $(2,2)$ is in a different orbit than $(2,3)$.

In fact, there are even more orbits than this. For example, the part corresponding to $s\times s$ splits even further : ({1,2},{2,3}) is not in the same orbit as ({1,2},{3,4}). The first is an ordered pair of vertices having a neighbour in common, while the second is a pair of vertices with no neighbour in common.

EDIT: As Dima Pasechnik explained, two of the other parts also split further in two, for a total of 14 orbits.