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 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.

share|cite|improve this question
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
up vote 5 down vote accepted

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

share|cite|improve this answer

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.