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)$? – Mariano Suárez-Alvarez Dec 24 '12 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}$. – ARupinski Dec 24 '12 at 15:49
@Mariano: Like I said, I get 9, but it seems to be wrong... – Felix Goldberg Dec 24 '12 at 15:56
I don't understand why you say that «you count 3 orbits but you plug in $9$». – Mariano Suárez-Alvarez Dec 24 '12 at 15:59
@ARupinski: Let's assume $c \geq 4$ (I'll update the question too). – Felix Goldberg Dec 24 '12 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}
-
Thanks! That's very nice. – Felix Goldberg Dec 24 '12 at 19:07

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.

-