## Confused about orbits

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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 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 at 15:49
@Mariano: Like I said, I get 9, but it seems to be wrong... – Felix Goldberg Dec 24 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 at 15:59
@ARupinski: Let's assume $c \geq 4$ (I'll update the question too).  – Felix Goldberg Dec 24 at 16:02
show 3 more comments

## 2 Answers

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 at 19:07

### You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

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.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 33, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9306444525718689, "perplexity_flag": "middle"}