Automorphisms of threshold graphs

The action of a group on a set $S$ induces a symmetric preorder of orbits on $S$. A permutation group on a set is orbit symmetric provided that the permutation group restricted to each orbit forms a symmetric group. Suppose that we have a structure defined by element invariants, then its automorphism group will be orbit-symmetric. In other words, orbit symmetric groups are permutation groups that preserve only the properties of elements and not anything else.

Orbit symmetric groups can be formed by the restriction of a symmetric group to a partition. Every permutation group is a subgroup of its orbit symmetric group acting on its orbits, which is the parent permutation group that preserves only element properties as represented as orbits. We will show that there is an interesting relationship between orbit symmetric groups and threshold graphs, first by demonstrating that they are their automorphism groups.

Proposition. the automorphism group of a threshold graph is the direct product of symmetric groups $S_{n_1} ... \times S_{n_i}$ acting on each of its orbits.

Proof. Let $G$ be a threshold graph, then we can distinguish two different cases based upon rather or not $G$ is connected:

(1) Suppose that $G$ is disconnected then by the definition of the threshold graph there is a family $S$ of $n$ isolated vertices of $G$ by the definition of threshold graphs. Isolated vertices are externally equivalent, so they are all transposeable and therefore they generate a symmetric group acting on $S$. If $S = G$ then we are done and $Aut(G)$ is a symmetric group, otherwise there is a unique non-isolated connected component $C$ of $G$, and as threshold graphs are subgraph closed $C$ is a threshold graph. $S$ and $C$ now form separate orbit-closed components of $G$. We can apply this process again to get the automorphisms of the threshold subgraph $C$ and then $Aut(G) \simeq S_n \times Aut(C)$.

(2) Suppose that $G$ is connected then there is a family $S$ of $n$ adjacency equivalent dominant vertices. These elements are transposeable so $S$ is acted on by the symmetric group. Form $C$ from $G - S$, then $C$ is a disconnected graph and $C$ and $S$ form separate orbit-closed components of $G$. We can form $Aut(C)$ similarily and apply this process again to get $Aut(G) \simeq S_n \times Aut(C)$. $\square$

So threshold graphs are orbit-symmetric, but the interesting thing is that they are precisely the graphs that are hereditary orbit-symmetric. Recall that a graph is a threshold graph if it is $ \{ C_4, \overline{C_4}, P4 \}$-free. In the first case we have $Aut(C_4) = Aut(\overline{C_4} ) = D_4$ and $D_4$ is not an orbit symmetric group, because it is a transitive group which is not symmetric. In the second case we have $Aut(P_4) = C_2$ acting on orbits 2+2 so it must transpose its two orbits at the same time, which means it is not orbit symmetric. Therefore, it would seem that threshold graphs are precisely the hereditary orbit-symmetric graphs.

Recall that threshold graphs are completely determined by their adjacency preorders. The adjacency preorder of a threshold preorder is an upper forest. In this way, threshold graphs can be treated like a tree, as demonstrated by how we compute the orbit symmetric permutation group associated to any threshold graph. In this case, the element invariants of a threshold graph are the depth, number of predecessors, and number of equal elements in the adjacency preorder. This makes threshold graphs similar to weak orders, in that they are completely determined by element properties.

External links:
https://www.graphclasses.org/classes/gc_328.html