Visualisation of Young diagrams in Clojure

This takes a Young diagram expressed as an additive partition and converts it into an image using the Java standard library. Then it creates a Swing frame for you to display the image. Young diagrams are important in a wide variety of mathematical contexts from number theory to abstract algebra.

(import java.awt.image.BufferedImage)
(import javax.swing.JFrame)
(import javax.swing.JLabel)
(import javax.swing.ImageIcon)

(defn determine-coordinates
  [coll]

  (let [sorted-seq (sort > (seq coll))]
    (apply
     concat
     (map-indexed
      (fn [x v]
        (map
         (fn [y]
           [x y])
         (range 0 v)))
      sorted-seq))))

(defn signature-image
  [sig block-size]

  (let [coords (determine-coordinates sig)
        sig-width (count sig)
        sig-height (if (empty? sig) 0 (apply max sig))
        padding-size (int (/ block-size 2))
        img-width (+ (* block-size (inc sig-width)))
        img-height (+ (* block-size (inc sig-height)))
        img (BufferedImage.
             img-width
             img-height
             BufferedImage/TYPE_INT_RGB)
        g (.createGraphics img)]
    (.setColor g java.awt.Color/WHITE)
    (.fillRect g 0 0 img-width img-height)
    (.setColor g java.awt.Color/BLACK)
    (doseq [coord coords]
      (let [[x y] coord]
        (.drawRect
         g
         (+ padding-size (* x block-size))
         (- img-height
            (+ padding-size
               (* (inc y) block-size)))
         block-size
         block-size)))
    img))

(defn display-image
  [img]

  (let [f (JFrame.)]
    (.add (.getContentPane f)
          (JLabel.
           (ImageIcon. img)))
    (.pack f)
    (.setVisible f true)))

The example that I have prepared is the Young diagram of the prime signature of the monster group. It is suprisingly imbalanced because the maximum multiplicity is much larger then the total number of primes.

Image equivalence classes

The image endofunctor of the category of sets $Im : Sets \to Sets$ maps any function $f: A \to B$ to $Im(f) : \wp(A) \to \wp(B)$. The image of $Im(f)$ is a power set equal to $\wp(I)$ where I is the image of $f$. The image is therefore just another power set. On the other hand, the equivalence classes of $Im(f)$ are a type of set system which you may not have seen before.

Proposition. the equivalence classes of $Im(f) : \wp(A) \to \wp(B)$ are upper bounded convex sets whose minima are the maximal cliques of a cocluster graph.

The family of maximal representatives of $Im(f)$ forms a partition topology, and so these equivalence classes are equivalent to those of the closure of a partition topology. If we treat a partition as a cluster graph, then clearly the minimal generators of any image are maximal independent sets because equivalence-equal elements are redundant.

By complementation, they are maximal cliques of a cocluster graph. Which means that the minimal sets are a maximal clique family. This is interesting because not all sperner families are maximal clique families. The upper boundedness of image equivalence classes is a special case of the fact that $Im(f)$ is the lower adjoint of a monotone Galois connection. The partition topology of maximal representatives is the image of the inverse image which is an upper adjoint.

Example 1.

Example 2.

Example 3.

Actions on posets

Preorders and monoid actions are deeply related. Starting with a monoid action, we can get a preorder. This preorder then determines the lattice of subobjects of the monoid action. In the other direction, when considering actions on preorders we can get additional types of monoid actions. This leads to the following ontology of posetal actions, all of which form monoids:

Typically, when considering the endomorphisms monoid $End(X)$ of an object $X$ of a category $C$ we can create a full theory of actions, but posets are different because their strong link with actions. In order to continue further, it is useful to add a posetal structure on the hom classes of posetal transformations.

Definition. let $(P, \subseteq), (Q, \subseteq)$ be partially ordered sets then we can partially order the hom class $Hom(P,Q)$ so that $f, g \in Hom(P,Q)$ have $f \subseteq g$ iff $\forall x : f(x) \subseteq g(x)$.

Let $(P, \subseteq)$ be a poset, then this can even be applied to $T_P$ the set of all transformations on $P$. Then we have taht a transformation $f$ is increasing iff $id_P \subseteq f$ and it is decreasing iff $f \subseteq id_P$. It follows that increasing transformations are the principal filter of the identity function $id_P$ in the pointwise ordering, and decreasing transformations are its principal filter. The only transformation that is both increasing and decreasing is therefore the identity $id_P$.

Theorem. The monoid of increasing actions on a poset is R-trivial.

Proof. Suppose that we have $f,g$ that are R-related then we have that $af = g$ and that $bg = f$. By the fact that each action is increasing we have that $\forall x : x \subseteq f(x) \subseteq a(f(x)) = g(x)$. In the other direction, we have that $\forall x : x \subseteq g(x) \subseteq b(g(x)) = f(x)$. The statement that $f(x) \subseteq g(x)$ and $g(x) \subseteq f(x)$ contradicts antisymmetry, so $f,g$ cannot be R-related. $\square$

Although it is the case that increasing actions on a poset are R-trivial, we cannot get that they are L-trivial in general, however, in the restricted case of increasing monotone actions then we can get L-triviality.

Theorem. The monoid of increasing monotone actions is D-trivial

Proof. Suppose that $f \subseteq_L g$ then $\exists a : fa = g$. We have that $\forall x : x \subseteq a(x) \subseteq f(a(x))$. By monotonicity, $x \subseteq a(x)$ implies $f(x) \subseteq f(a(x))$ now since $f(a(x)) = g(x)$ this implies $f(x) \subseteq g(x)$. So therefore, if $f,g$ are in the same L class then we have $f(x) \subseteq g(x)$ and $g(x) \subseteq f(x)$ which contradicts antisymmetry. Therefore, the monoid of increasing monotone actions is L-trivial. It is already R-trivial, so if it is both L-trivial and R-trivial then it is D-trivial. $\square$

One corollary that is worth mentioning, is that the poset of monoid actions is group-free. This distinguishes increasing actions from monotone ones which can include the group of automorphisms.

Corollary. The monoid of increasing actions is group-free

Proof. R-trivial $\implies$ H-trivial $\implies$ group-free $\square$

Let $C$ be the category of partial orders and monotone maps. Then we can easily make the following observation about the group of automorphisms $Aut(P)$ of a finite poset $P$.

Theorem. Let $P$ be a finite poset. Then $Aut(P)$ is never increasing/decreasing.

Proof. We can rank the elements of $P$ in the following form: $R(x)$ is equal to the maximum height of the principal ideal of $x$. Then if we have $x \subset y$ we must have that $R(x) \lt R(y)$. Permutable elements must have the same invariant rank, therefore they must be incomparable. $\square$

It is wrong to assume that $Aut(P)$ is never increasing/decreasing in general because it may not always be possible to rank elements of a poset. In particular, there are order-automorphisms of the dense total order $(\mathbb{Q}, \subseteq)$ because no well-ordered ranking can be established on it.

Corollary. The orbits of the group action of a finite partially ordered set $Aut(P)$ are an equivalence subrelation of the partition of $P$ into co-connected components.

The automorphism group of a finite weak order is an orbit symmetric group, and the orbits of the group action coincide with the connected components of the complement of the comparability graph.

Self-induced actions

It is common to represent a semigroup, monoid, or group by action on some set, but in the case where an action is not given to us we can recover one by the action of the semigroup on itself. This process can even be applied to magmas, to get the action of a magma on itself. In that case, the lack of associativity means that the self-induced actions need not be complete, which produces a subset of a semigroup. This leads to an interesting connection between semigroup theory and magma theory.

Left and right actions:

Introduction:
Let $S$ be a set, $* : S^2 \to S$ be a magma, and $T_{S}$ be the complete transformation monoid on $S$, whose members are actions $f: S \to S$. Then we can define the left and right actions of elements by mappings: \[ L : S \to T_{S} \] \[ L(a) = \lambda(x) (a*x) \] \[ R : S \to T_{S} \] \[ R(a) = \lambda(x) (x*a) \] The following elementary observations are immediate from these definitions:

• An element is L/R cancellative, unital, or zero if its corresponding L/R actions are mono, unital, or constant.
• The centralizer of an element is the equalizer of its left and right actions.
• An element is central if its left and right actions coincide.

Action systems:
The image of the L,R mappings are both subsets of $T_{S}$. For general magmas, these action systems $Im(L),Im(R)$ do not need to be semigroups, however, they are always subsets of a semigroup and partial semigroups. Their closures are the $L,R$ action semigroups.

Equal actions:
The L,R mappings don't need to be mono, instead they can produce equal actions for different values. This produces ${=}L, {=}R$ equivalence relations on $S$.

Example 1. in a constant semigroup all L,R actions are equal and so both the L,R mappings are constant.

[[1 1 1]
 [1 1 1]
 [1 1 1]]

Example 2. in the following pure rectangular band $L$ is mono and always maps to a different constant function and $R$ is constant and always maps to the same identity action.

[[1 1 1]
 [2 2 2]
 [3 3 3]]

In general semigroups there are often equal actions, as demonstrated in the above actions but that doesn't need to be the case. A magma is called left faithful or right faithful, provided that the left and right self actions $L,R$ are monomorphisms. Groups are clearly left and right faithful because if they had equal actions that would violate cancellativity.

The special case of semigroups:
In the special case of semigroups, $L,R$ are actually semigroup homomorphisms. Their image action systems are semigroups and the equivalence relations ${=}L,{=}R$ are congruences. This is clarified in the following theorem. By the first isomorphism theorem, we have isomorphisms $\frac{S}{{=}L} \cong Im(L)$ and $\frac{S}{{=}R} \cong Im(R)$.

Theorem. $L : S \to T_S$ and $R : S \to T_S^{Op}$ are semigroup homomorphisms.

Proof. By definition $L(ab) = \lambda(x) (ab)x$ by associativity $(ab)x = a(bx)$ but then $a(bx)$ is equal to $(L(a) \circ L(b))(x)$. Therefore, $L(ab) = L(a) \circ L(b)$. In other direction, $R(ab) = \lambda (x) x(ab)$. Then by associativity $x(ab) = (xa)b$. This is then equal to $(R(b) \circ R(a))(x)$. $R(ab) = R(b) \circ R(a)$ which is a homomorphism in the opposite direction.

Remarks. the distinction between $T_S$ and $T_S^{Op}$ doesn't really matter and is dependent upon our notation for composition. All that matters is that $L$ and $R$ are opposite directions, so their corresponding semigroups homomorphisms are opposite to one another.

In the case of semigroups, $L$ and $R$ can be seen as reducing semigroups to their faithful counterparts. The fact that group's are faithful directly leads to Cayley's theorem which is the representation of any group by the group action defined by $L$.

The special case of groups:
The action of a group on itself is simply transitive, which means that all elements are contained in the same orbit and all stabilizers are trivial. The former is a consequence of the existence of inverses and the later is a consequence of cancellativity.

Two sided actions:

The J semigroup:
The images $Im(L),Im(R)$ of the L and R mappings are both subsets of the semigroup $T_S$. Their closures are therefore both members of $Sub(T_S)$. They both must therefore have a semigroup join, which contains all actions both left and right.

Definition. the $J$ semigroup is the semigroup join of the $L$ and $R$ action semigroups, which are defined as the closures of the images of the $L$ and $R$ mappings.

$J$ is the ultimate semigroup defining actions of a magma, semigroup, or other related structure on itself.

Inclusions:
The three semigroups $L,R,J$ form a three element suborder of $Sub(T_S)$ with $L,R \subseteq J$. The intersection $L \cap R$ contains at least all actions by central elements.

Magma theory:

The $L,R$ mappings produce a connection between semigroup theory and magma theory that is worth examining. In particular, magmas correspond to subsets of semigroups, because their $L,R$ images don't need to be closed.

Example 1. consider the following non-commutative monogenic magma

[[2,1]
 [2,2]]

Then we have the following left actions: {[2,1],[2,2]}. This is a subset of $T_2$ but it is not closed, which demonstrates that the images of $L$ don't need to be closed for magmas. Its closure is ${[1,2],[2,1],[1,1],[2,2]}$ which is an upper invariant swapper semigroup because the half invariant upper constant elements are acted upon by their predecessor group. This is a first example of a semigroup constructed from a magma.

In the other direction we get the semigroup {[1,2],[2,2]} which is a subsemigroup, therefore this semigroup is R action composition closed. This semigroup action is the total order semilattice on two elements.

Example 2. let $\mathbb{Z}_+$ be the positive integers then $^ : \mathbb{Z}_+^2 \to \mathbb{Z}_+$ is a magma.

The right actions of exponentation are composition closed because $(a^x)^y = a^{xy}$. In this case, the operation is not associative so composition is determined by an operation other then exponentation itself. In this case, we have a semigroup homomorphism $Im(R) \to *$.

The left actions of exponentation on the other hand are not composition closed. When we have $a^(b^x)$ there is no way to reduce it to a single exponentation. Left actions are not composable at all unless one of them is equal to one, which is the trivial case. The semigroup closure of left actions is the set of all exponentation towers closed under composition.

As $Im(L)$ is a subset of a semigroup, we can form a Cayley digraph of it consisting of all pairs of elements $(a,b)$ such that there exists some $c$ such that $c^a = b$. We can call this the 'base of' binary relation, as elements are related provided that the first is a base of the other with respect to some exponent. This binary relation is not transitive because 3 is a base of 9, 9 is a base of 512, and 3 is not a base of 512.

Green's relations:

It is clear that Green's preorders is a special type of action preorder and now we can directly construct monoid actions whose action preorders correspond to the Green's preorders of a semigroup.

• $\subseteq_L$ is the action preorder of $Im(L)$
• $\subseteq_R$ is the action preorder of $Im(R)$
• $\subseteq_J$ is the action preorder of the $J$ semigroup

Green's relations are the strongly connected components of each of these action preorders. We can also form similar preorders from magmas or any structure that acts on itself in some manner.

Subsets of semigroups

In this post, we will examine subsets of semigroups that are not necessarily subsemigroups. Let $S$ be a set, $* : S^2 \to S$ be a semigroup on $S$, and $T$ be a subset of $S$. Then we can form a restriction binary operation $*_{T^2} : T^2 \to S$, but this restricted binary operation may produce values that are not in $T$. We can restrict the semigroup further by a composability binary operation, which creates a partial operation.

Composability:
The composability binary relation of a subset $T$ of a semigroup has a pair of elements related to one another provided that their composition is in $T$.

Definition. let $(S,*)$ then composability $C(T) : \wp\{S\} \to \wp\{S^2\}$ is a map from subsets of $S$ to relations of $S$ defined by $\{ (x,y) \in T^2: x*y \in T \}$

By restricting to $C(T)$ instead of $T^2$ we get a partial binary operation because now it is defined on a subset of the cartesian product $T^2$, which is a partial binary operation.

Partial semigroups:
Let $* : R \to S$ be a partial binary operation with domain $R \subseteq S^2$. Suppose that we have an ordered triple $(x,y,z)$ of elements of $S$ then the compositions $(xy)z$ and $x(yz)$ need not exist. There is a nine-element existence lattice that determines the extent to which they do exist.

This defines the ontology of associatity conditions of partial binary operations. Given any existence condition, we can require that $(xy)z$ and $x(yz)$ exist and that they coincide.

• * is strongly associative if $xy, yz$ exists implies associativity
• * is left pre-associative if $(xy)z, yz$ exists implies associativity
• * is right pre-associative if $x(yz), xy$ exists implies associativity.
• * is a partial semigroup if $(xy)z, x(yz)$ exists implies associativity.

You could then form an ontology of conditions of associativity of partial binary operations by taking the ideals of the nine-element existence lattice. For further discussion about the ways of defining associativity of partial operations see [1]. Given a set $T$ with composability relation $C(T)$ we can now form a restricted binary operation $*_{C(T)} : C(T) \to T$ whose output set is $T$ rather then $S$. It is not hard too see that this is a partial semigroup because the parent operation is associative.

Proposition. $*_{C(T)} : C(T) \to T$ is a partial semigroup

It follows that we can form partial semigroups from any subset of a semigroup. A common technique is to take a partial semigroup and adjoin a zero element to it, so that all compositions that don't exist instead map to the zero element. This can be used to construct semigroups from certain partial semigroups. For example, given an ideal $I$ then its rees quotient is produced by adjoining a zero to the partial semigroup $I^C$.

Induced relations:
Recall that there is a monotone map from subsemigroups to action preorders. When we are dealing with general subsets, the lack of composition closure corresponds to a lack of transitivity. This leads to left/right Cayley relations $\Gamma$, which can be defined for any semigroup. Given a subset $T$ of a semigroup $(S,*)$ then $(x,y) \in \Gamma$ if $\exists t \in T: y = xt$. If the subset is composition closed, then this action relation is a preorder.

References:
[1] The Theory of Partial Algebraic Operations (Mathematics and Its Applications (414))

Action representatives

Let $S$ be a set and $R \subseteq S^2$ a preorder on $S$. Then the preorder $R$ defines the direction in which the elements of $S$ can move over time, but it says nothing about the driving forces responsible for moving the elements of the preorder in the direction they are going in. Take spacetime for example, then we can partially order events in spacetime by causality, but by itself a causal set does nothing to explain the fundamental forces responsible for motion or what makes one event cause another.

In general, given a preorder we want to describe in more detail the sort of actions that move the elements of the order along. Abstract algebra allows us to do this by using structures like transformation monoids. This leads to the idea of action representatives. Let $S$ be a set, $T$ a monoid acting on $S$, and $R$ the increasing action preorder of the transformation semigroup $T$. Then the action preorder $R$ is a set of ordered pairs, if we select an ordered pair $(x,y) \in R$ then a representative action $t \in A(x,y)$ is an element $t$ of $T$ that transforms $a$ into $b$. \[ A(x,y) = \{ t \in T: t(x) = y \} \] A representative action for an ordered pair only exists if it is in the preorder $R$. At the same time, for a transformation monoid representative actions always exist for any ordered pair in the action preorder. To see this note that if $x \subseteq y \subseteq z$ then the composition of the actions that transform $x$ to $y$ and $y$ to $z$ transform $x$ to $z$. The identity is an action representative for any loop. The composition of actions generalizes transitivity, and so representative actions are always ensured to exist.

The interesting thing, and the purpose of this discussion, is the analogy with category theory. We can treat a category $C$ as a set of morphisms acting on a set of objects. In that case, the representative actions of $C$ of an ordered pair $(x,y)$ correspond to hom classes $Mor_C(x,y)$. As in the case of transformation monoids, representative actions exist if and only if an element precedes another one in the corresponding morphic preordering. In this way, a category is one way of extending a preorder with actions that describe the ways that one element can be transformed to another.

The difference between the monoid action picture and the categorical picture, is that given any morphic action of a category $C$ it corresponds to only one ordered pair. On the other hand, a transformation of a set is the representative of as many actions as the cardinality of the set itself. By restricting to describing only the invidual actions that move elements along, categories most readily provide for structural descriptions of preorders.

Monotone maps and Galois connections

Let $(P, \subseteq)$ and $(Q,\subseteq)$ be partially ordered sets and $f: (P, \subseteq) \to (Q,\subseteq)$ a function between them. Recall that a function is a one-to-one map between the lattices $Part(P)^d$ and $\mathcal{P}(Q)$. These are the lattices of subobjects and quotients of the topoi of sets. In the special case of functions between partial orders the equivalence classes and images of the function produce suborders. We will consider these suborders in the case of monotone maps in general and Galois connections in particular.

Maximal and minimal representatives:
The function $f : (P,\subseteq) \to (Q, \subseteq)$ induces an equivalence relation $x =_f y \Leftrightarrow f(x) = f(y)$. If the equivalence classes of $=_f$ are upper bounded suborders, then there is a maximal representative input that produces any given output. Dually, if the equivalence classes of $=_f$ are lower bounded suborders, then minimal representatives exist. It is also possible that both or neither exist. The existence of maximal and minimal representatives can be represented symbolically:

• Maximal representatives: $(F(a) = b) \Rightarrow (a \subseteq G(b))$
• Minimal representatives: $(F(a) = b) \Rightarrow (G(b) \subseteq a)$

Maximization produces an increasing idempotent action and minimization produces a decreasing idempotent action. For a given map between posets for which either process is possible, maximization and minimization don't necessarily have to be monotone. In the case which they are such as in a Galois connection then they form closure and interior operators.

Image suborders:
The image of $f : (P, \subseteq) \to (Q,\subseteq)$ is a suborder of $(Q, \subseteq)$. We can therefore classify monotone maps between partial orders based upon the properties of their image suborders. We say that a suborder is a Moore suborder if it has a closure operation and a Comoore suborder if it has an interior operation. These are the two special cases of interest in Galois connections.

Suppose that $f : (P, \subseteq) \to (Q,\subseteq)$ is a monotone map and we have $(F(a) \subseteq b) \Rightarrow (a \subseteq G(b))$. Then by monotonicity we have that $F(a) \subseteq F(G(b))$. Which proves that the $F$ image of $G(b)$ is greater then any other which is less then $b$. This means there must be on the images of $f$. Dually, if we have the same condition in the other direction there must be a closure operator on the images of $f$.

Overview:
There are three types of map associated to Galois connections: lower adjoints, upper adjoints, and polarities. Upper and lower adjoints are monotone and polarities are antitone. We can use the results proved thus far to describe the images and equivalence classes of each type of map:

• Lower adjoints:
  • Upper bounded equivalence classes
  • An interior operator of images
• Upper adjoints:
  • Lower bounded equivalence classes
  • A closure operator of images
• Polarities:
  • Upper bounded equivalence classes
  • A closure operator of images

A Galois connection is from a lower adjoint by taking the maximal representative of the largest image less then a given output value. For an upper adjoint it is determined by taking the minimal representative of the smallest image greater then a output value. Finally, for a polarity it is determined by the maximal representative of the closure of an output value. In this way, when Galois connections exist they are uniquely determined by each map.

For example, in algebraic geometry we saw that the antitone map $V: \wp(R[x,y,z,...]) \to \wp(\mathbb{A}^n)$ from any polynomial system to its algebraic set has upper bounded equivalence classes and its image has a closure operator. Therefore, V is a polarity in an antitone Galois connection. There are stronger properties, like that the images form a cotopology (the Zariski cotopology) and in the case of an algebraically closed field the maximal representatives are radical ideals.

As a function is a one-to-one map between its equivalence classes and its image, in order to construct a one-to-one restriction mapping of a function it is only necessary to get representatives of each equivalence class. In both types of Galois connection this can be achieved by selecting minimal and maximal representatives of a map. In the case of algebraic geometry, by Hilbert's nullstellensatz there is a one to one mapping between radical ideals and algebraic sets of a polynomial ring over an algebraically closed field.

Suprema and infima:
The purpose of this post is to compile all the relevant aspects of the monotone maps of a Galois connection, rather then considering the connections themselves. There is one more property worth considering and that is the relationship between maps and suprema/infima:

• Lower adjoints preserve suprema
• Upper adjoints preserve infima

Order theory and category theory comparison:
Almost everything in category theory is a slight variant of something older in order theory. One reason to consider Galois connections then, is their relationship to category theoretic adjoints. In that case, the most important property is that lower adjoints preserve colimits and upper adjoints preserve limits. An example of relevance to algebraic-geometry is the tensor-hom adjunction. There we see that the tensor product is a lower adjoint and so it preserves colimts and the hom is an upper adjoint so it preserves limits. The limit/colimit preserving conditions for adjoint functors correspond to the suprema/infima preserving conditions of Galois connections.

Monotone maps and divisibility

Categories are direct generalisations of transitivity. This is formalized by the hom class congruence $\frac{C}{Hom} = R$ of a category which produces a thin quotient category $R$. In this way, category theory is a natural development of order theory. There is a stronger condition, which is that in the most common categories structure preserving maps produce induced inclusions in corresponding partial orders. A family of common input morphisms then produces a partially ordered family of induced inclusions, whose structure is determined by a comma category.

Example. Let $(\mathbb{Z}_+, |)$ be the divisibility lattice of the positive integers. Then there are six fundamental monotone maps from the divisibility of the positive integers to other partial orders.

identity : $(\mathbb{Z}_+, |) \to (\mathbb{Z}_+, |)$ which maps any positive integer to itself

radical : $(\mathbb{Z}_+, |) \to (\mathbb{Z}_+, |)$ which maps any positive integer to its square-free part

signature : $(\mathbb{Z}_+,|) \to (\mathbb{Y}, \leq)$ which maps any positive integer to its prime signature, which is a monotone map with respect to Young's lattice

$\omega : (\mathbb{Z}_+,|) \to (\mathbb{Z}, \leq) $ which maps any positive integer to its number of distinct prime factors

$\Omega : (\mathbb{Z}_+,|) \to (\mathbb{Z}, \leq) $ which maps any positive integer to its number of prime factors counting multiplicity

one : $(\mathbb{Z}_+, |) \to (\{1\}, |)$ which maps any positive integer to the terminal preorder

Each of these monotone maps produces an induced inclusion of the divisibility lattice in an induced preorder. This follows from the fact that $x \subseteq y \Rightarrow f(x) \subseteq f(y)$ is an inclusion of the relation $\subseteq$ in $\subseteq_f$. Induced preorders are therefore larger then input preorders. The constant map produces a complete relation $(\mathbb{Z}_+)^2$ and the identity map produces the divisibility lattice $(\mathbb{Z}_+,|)$. All the induced preorders together form a suborder of the lattice of preorders:

Let $C$ be a category. Then the morphisms of $C$ are preordered by either the input action preorder or the output action preorder. Corresponding to their respective preorders are the input action and output action categories, whose morphic preorders are the corresponding action preorders and whose morphisms are the respective input or output actions that relate one morphism to another. The connected components of these categories are then the comma categories $X/C$ and $C/X$ of each object of the category. In particular, we can form a comma category $(\mathbb{Z}_+,|)/Ord$ of all monotone maps starting from $(\mathbb{Z}_+, |)$.

Proposition. output actions in the category of partial orders and monotone maps are increasing with respect to induced preorders.

Proof. Let $f : (X, \subseteq) \to (Y, \subseteq)$, $g: (Y, \subseteq) \to (Z,\subseteq)$ and $g \circ f : (X, \subseteq) \to (Z,\subseteq)$ be monotone maps. Then let $x,y \in X$ and suppose that $f(x) \subseteq f(y)$. By the monotonicity of $g$ in $Y$ we have that $f(x) \subseteq f(y)$ implies $g(f(x)) \subseteq g(f(y))$. It follows that $\subseteq_f$ is a subrelation of $\subseteq_{g \circ f}$. $\square$

We have that morphisms in the category $Ord$ produce induced inclusions in the lattice of preorders. This does not, however, account for intermediate induced inclusions like those in the divisibility example. In order to account for these intermediate inclusions, we can now use the comma category $(\mathbb{Z}_+,|)/Ord$. Output actions are increasing with respect to induced relations, so for intemerdiate inclusions we can find corresponding monotone maps that map smaller morphisms with respect to the output action preordering to larger ones.

In the example described above, we can map the prime signature to $\omega$ by the size of the signature and $\Omega$ by the sum. Likewise, we can map the radical to $\omega$ by the number of distinct prime factors. Any monotone map can be converted to the map to the trivial preorder, by mapping everything to the same output value. As a result, the ordering on induced relations corresponds to the output action ordering of the comma category.

Commutative semigroups of order [2 1 1]

Let [2,1,1] be the weak order on four elements. It has up to isomorphism three types of elements: lower elements, middle elements, and upper elements denoted L,M, and U for short. There are also four types of unordered pairs up to isomorphism: $L^2, LM, LU, ML$. We want to partially order each semigroup isomorphism type with this factorisation order pointwise up to isomorphism. In order to do this it is necessary to introduce some measure of how much larger a given output is then expected.

The measure of the greatness of an output is the covering distance from its original location. We see that given this partial order, $L+1$ means that a given minimal element iterates to produce the middle element and $L+2$ means it iterates to produce the maximal element. It is clear then that $L+2$ is greater then $L+1$ in the ordering, and so on. Given this format, we can determine where a given commutative semigroup isomorphism type is based upon a set of relations like these on isomorphism classes of subsets. So for example, this is the poset of commutative semigroup isomorphism types with factorisation order [2 1 1]:

As previously mentioned, the other upper bounded partial orders of size four or less have commutative semigroup families that either form total orders or boolean algebras. Total orders have boolean algebras of semigroup types determined by sets of idempotents, and max height two partial orders have total orders determined by the number of idempotents. Both have a unique maximal upper bound, which is the unique commutative nilpotent semigroup of that order type.

The lower bound of the above poset is the unique semilattice with that order type, which is the least upper bound. However, there are two different maximal elements which demonstrates that partial orders don't always have a greatest upper bound commutative semigroup. In this case, in order for the factorisation order to be [2,1,1] the lower elements must produce the middle element somehow and there are two ways to that: individually or together. This produces the two different maximal commutative semigroups with this factorisation order.

Finite commutative totally ordered semigroups

Let $P$ be a finite upper bounded partially ordered set. Then there exists a family of commutative semigroup isomorphism types which have $P$ in common as their factorisation order. We will study these factorisation order equal families of isomorphism types by first considering the special case in which $P$ is a total order.

Structure theory:
We will clasify finite commutative tosetal semigroups by first classifying finite commutative unipotent tosetal semigroups. We will start by locating the unique idempotent in such a semigroup and examining the idempotents in .

Proposition. The maximal element in a finite commutative partially ordered semigroup $S$ is idempotent

Proof. Let $x$ be the maximal element in $S$. Suppose that $x$ is not idempotent, then there exists an element $y$ such that $x^2 = y$ which implies $x \subseteq y$ which contradicts the supposition that $x$ is maximal. Therefore, $x$ must idempotent. $\square$

Proposition. All finite commutative unipotent totally ordered semigroups $S$ are monogenic

Proof. Let $x$ be the the maximal element of $S$ and $y$ the minimal element. Then by the previous proposition, $x$ is idempotent. The minimal element $y$ generates a monogenic subsemigroup $(y)$. Suppose that $(y)$ is not equal to the entire semigroup $S$ then $(y)$ has a maximal element which is idempotent, and since it doesn't generate the entire semigroup it is distinct from $x$. This implies that there are two idempotents in the semigroup which contradicts the condition that it is unipotent. Therefore, $y$ generates the entire semigroup, which means that $S$ is monogenic. $\square$

This should make the structure theory of finite commutative tosetal semigroups clear. By semilattice decompositions all finite commutative posetal semigroups can be decomposed into semilattices of finite commutative unipotent semigroups.

Proposition. Finite commutative tosetal semigroups are semilattices of monogenic semigroups

Proof. By semilattice decompositions every finite commutative semigroup can be decomposed into a semilattice of unipotent semigroups. All of these unipotent semigroups are monogenic. Therefore, finite commutative tosetal semigroups are semilattices of monogenic semigroups. $\square$

With this classification in place, we can introduce numerics to measure the number of commutative semigroups associated to a finite total order.

Theorem. There are $2^{n-1}$ finite commutative tosetal semigroups on $n$ elements.

Proof. Let $F$ be the family of commutative semigroups on the total order $T_n$. We can prove this constructively by constructing a bijection $f : \mathcal{P}(1..n-1) \to F$.

(1) Let $S$ a member of $\mathcal{P}(1..n-1)$ and construe its elements as idempotents in the semigroup. Then we can take each of these elements of $\mathcal{P}(1..n-1)$ and add to them all the non-idempotents before them until we get to an idempotent to get a family of intervals with cardinalities $N_1, ... N_{i-1}$. Then take the ordinal sum of semigroups of monogenic semigroups with orders $N_1, ... N_{i-1}$ to get a semigroup isomorphism type in $F$.

(2) Let $S$ be a semigroup isomorphism type and a member of $F$. Then we can map $S$ to $\mathcal{P}(1..n-1)$ by taking the set of all proper idempotents of $S$. By extending the set of idempotents to a family of intervals, we can get a different semilattice of monogenic subsemigroups for each set of idempotents. By the the classification of finite commutative tosetal semigroups as semilattices of monogenic subsemigroups, this determines finite commutative tosetal semigroups up to isomorphism. $\square$

Boolean algebra of isomorphism types:
The fact that there are $2^{n-1}$ isomorphism types of commutative semigroups on a finite total order suggests that there is an underlying boolean algebra structure of isomorphism types. Recall from basic lattice theory that partitions of a finite total order into intervals forms a boolean algebra.

Proposition. the lattice of all partitions of a finite total order $T_n$ into intervals forms a boolean algebra with $T_{n-1}$ elements.

You can take a finite commutative tosetal semigroup and get a partition into intervals from it by taking its semilattice decomposition, which is natural way to get a connection to boolean algebras.

Proposition. semilattice decompositions of finite commutative tosetal semigroups are partitions of total orders into intervals

This makes makes the family of commutative semigroups on a total order into a boolean algebra. This is similar to the boolean algebra of lattice congruences on a finite total order, which is also constructed from partitions into intervals.

The minimal element of $Part(S)$ is the finest partition of $S$. As a semilattice has the finest semilattice decomposition, it is the minimal element of the boolean algebra of isomorphism types. It makes sense to have semilattices be the minimal, because they are the least upper bound function so every greater element is a greater upper bound.

Addendum:
Let $P$ be an upper bounded lower common point free tree. Then the set of non-maximal elements forms a disjoint union of total orders, and so every semigroup principal ideal is a tosetal semigroup. Then a semigroup $S$ with this order type is fully determined by its maximal principal ideals, which are all tosetal. In particular, this fully classifies all semigroups with order type [n, 1].

Proposition. let $P$ be a partial order of order $n$ with maximum height two then there are $n$ isomorphism types on $P$ and they are totally ordered by number of idempotents.

We see that for the simplest order types: those that are $T_n$ or $[n, 1]$ their families of commutative semigroups are lattice ordered. This is true for any upper bounded lower common point free interval ordered tree, in which case the poset of isomorphism types is a power multiset lattice. In the case of $[\{[1,1],[1,1]\}, 1]$ which is not an interval order, however, the ten isomorphism types do not form a lattice because the set orbit poset of 2+2 poset does not.

Proposition. Let $P$ be the diamond partial order with type [1,2,1]. Then the minimal element of $P$ is idempotent.

Proof. Let $x$ be the minimal element of $P$ and suppose that $x$ is not idempotent, then $x^2$ is another element in $S$. Let $y$ be one of the two middle elements not generated by $x$ then the fact that $x$ is less then $y$ implies that $xy=y$ which means that $x^2y=y$, and so $x^2 \subseteq y$ which contradicts the fact that the only predecessor of $y$ is $x$. Therefore, $x$ must be idempotent. $\square$

Therefore, the total order of semigroups on [1,2,1] is the same as those on [2,1]. The minimal idempotent has no effect. It would be wrong to assume that this is the case for any element whose order ideal is a diamond because we must remember that order ideals and semigroup ideals don't necessarily need to coincide. Recall that the factorisation preorder of a subsemigroup is a subpreorder of the preorder of the semigroup.

Proposition. the factorisation preorder of a subsemigroup $S \subset T$ is a subpreorder of the subpreorder of the factorisation preorder of $T$ induced by $S$.

The relationship between action preorders and subalgebras is monotone. If the factorisation preorder of a subsemigroup is reduced that means there is external actions by elements outside the semigroup principal ideal that determine what elements an element is a factor of.

In general, we study commutative semigroups using three things (1) the classification of commutative groups which are the H classes of a commutative semigroup (2) the partially ordered commutative semigroups that emerge from quotient by the H congruence which determines how H classes are related to one another and (3) the action of predecessor Schutzenberger groups on sucessor H classes.

References:
Commutative semigroups by Grillet

Factor relations

In this post we will consider the different ways of comparing subsets of a partially ordered set. Let $(A,\subseteq)$ be a partially ordered set and $S,T$ be two different types of subsets of $A$. There are five types of relationship $\sqsubseteq$ between subsets $S,T$ of partial orders as described below:

• Ordinary precedence: $ \exists x \in S, y \in T : x \subseteq y$
• Strong ordinary precedence : $\forall x \in S : \exists y \in T : x \subseteq y$
• Upper ordinal precedence : $ \exists y \in T : \forall x \in S: x \subseteq y$
• Lower ordinal precedence : $ \exists x \in S : \forall y \in T : x \subseteq y$
• Strong ordinal precedence : $\forall x \in S, y \in T : x \subseteq y$

These five concepts clearly form a hierarchy with ordinary precedence being the most general case, and strong ordinal precedence being the most restricted. With such a variety of cases, it is not obvious at first what type of set comparison we want to work with.

The idea of a relation homomorphism lends a hint as to sort of relationship between sets we want to consider. Suppose that $(A,\subseteq)$ is a set $A$ with binary relation $\subseteq$ and that $P$ is a partition of the ground set $A$. Then there is a natural projection map $f : A \to P$. We want to form a relation on $P$ such that $f$ is a homomorphism using one of the five comparisons of sets. Then in general we need to use ordinary precedence.

To see this, notice that whenever have $S,T$ and we have $x \in S$ and $y \in T$ such that $x \subseteq y$ then in order for $f$ to be a relation homomorphism we must have $f(x) \subseteq f(y)$ in other words $S \sqsubseteq Y$. Therefore, in order for a projection map to always be a relation homomorphism we need to use ordinary precedence in general because the other types of relation may miss things. The other other types of projection are not always homomorphisms.

Proposition. Let $(A, \subseteq)$ be a partially ordered set and $P$ a partition of $A$. In order for the factor relation by ordinary precedence to be antisymmetric, then every set of $P$ must be convex.

Proof. Let $S$ be a non-convex subset of $A$ then there exists an element $x$ such that $s_1 \subseteq x \subseteq s_2$ for elements $s_1,s_2 \in S$. Let $T$ be the set containing $x$ in $P$. Then by $s_1 \subseteq x$ we have $S \subseteq T$ and by $x \subseteq s_2$ we have $T \subseteq S$. Therefore, $S,T$ are symmetrically related which is a contradiction. $\square$

This is a generalization of the fact that the equivalence classes of a lattice congruence are all convex. Lattice congruences produce quotient semilattices and ordinary predecendence produces factor relations. It would be interesting to see if the relational quotient agrees with the algebraic one.

Proposition. let $(L,\subseteq)$ be a lattice with congruence $C$. Then ordinary precedence on the congruence classes of $C$ and the lattice quotient $\frac{L}{C}$ coincide.

Proof. Let $f : L \to C$ be the map which takes any lattice element to its congruence class. Let $C_1, C_2$ be congruence classes such that $C_1 \subseteq C_2$ in the quotient lattice. Select arbitrary elements $x \in C_1$ and $y \in C_2$ then take $x \vee y$ then it is in $C_2$ and we have $x \in C_1$ and $x \vee y$ such that $x \subseteq x \vee y$ so that $C_1$ is an ordinary predecessor of $C_2$. Conversely, suppose that $C_1$ is an ordinary predecessor of $C_2$ then there exist $x \in C_1$ and $y \in C_2$ such that $x \subseteq y$. We clearly have that $x \vee y = y$ therefore, in the quotient lattice $C_1 \vee C_2 = C_2$ so $C_2$ is greater then $C_1$. $\square$

So the ordinary factor relation is sufficient to recover the order on a lattice congruence. Given a finite lattice, we also have upper ordinal precedence and lower ordinal precedence. We do not have strong ordinal precedence in all cases unless we are dealing with a total order, then of course strong ordinal precedence applies.

It is often use to quotient a lattice by a partition which doesn't necessarily form a congruence. For example, consider the simple example of the diamond partially ordered set $\{\emptyset,\{0\},\{1\},\{0,1\}\}$. Then we might want to form a partition by cardinality $\{ \{ \emptyset \}, \{ \{0\},\{1\} \}, \{ \{0,1\} \} \}$ these does not form a lattice congruence, but it does form a quotient partially ordered set which is the total order on cardinal numbers $\{0,1,2\}$.

Example 1. finite sets partitioned by cardinality produces the total order $\omega$

Example 2. finite multisets partitioned by signature produces the young's lattice $Y$

Example 3. subsets partitioned an automorphism group acting on sets produces the set orbit poset

Example 4. isomorphism types of algebraic structures can be ordered by subalgebras, quotients, or subquotients.

Example 5. finite abelian groups are determined up to isomorphism by a product of primary cyclic groups, then up to isomorphism a subalgebra is a reduction in the number of cyclic groups or in one of their exponents

Example 6. let $S$ be a finite set with cardinality $n$ then $Part(S)$ partitioned by set partition isomorphism type produces the refinement ordering of additive partitions of $n$

Commuting graphs of subsemigroup lattices

Let $S$ be a semigroup. Then the commuting graph on $S$ has an underlying set consisting of the elements of $S$, however, we often want to work with subalgebras rather then individual elements. We can address this by creating a commuting graph on $Sub(S)$.

Definition. Let $Sub(S)$ be the lattice of subsemigroups of a semigroup $S$. Then the commuting graph $G$ on $Sub(S)$ has subsemigroups as vertices and the following binary family of sets as an edge set: \[ \{\{A,B\} : \forall x \in A, y \in B : xy = yx\} \] This means that $Sub(S)$ is simultaneously a lattice and a graph. Recall that graphs are naturally preordered by adjacency: one vertex is greater then another if it is adjacent to more elements then it. These two preorders have the following interesting relationship:

Theorem 1. Let $S$ be a semigroup and $G$ the commuting graph on $Sub(S)$. If $A,B \in Sub(S)$ and $A \subseteq B$ then $Adj_G(b) \subseteq Adj_G(a)$

Proof. Let $X$ be any given subsemigroup that commutes with $B$ then we have that $\forall x \in X, y \in B : xy=yx$. We have that $A \subseteq B$ which means that $\forall x: x \in A \implies x \in B$. Therefore, suppose $x \in X$ and $y \in A$ then we have $x \in X, y \in B$ and by our original supposition this means that $xy = yx$. $\square$

It follows that the inclusion and commutativity preorderings are inversely related. A related question is when it is that inclusion-comparable subsemigroups commute.

Centers of semigroups:
Recall that the center of a semigroup is the subsemigroup of elements that commute with everything. This forms an idempotent decreasing action on the lattice of subsemigroups $Sub(S)$. It is not monotone, because larger semigroups can have smaller centers. \[ Center : Sub(S) \to Sub(S) \] The image of the $Center$ consists of all commutative subsemigroups. Therefore it is a map from the subsemigroup lattice $Sub(S)$ to its lower set of commutative subsemigroups. We can now address the question of when two inclusion-comparable subsemigroups commute with one another. A pair of semigroups $A \subseteq B$ commute if and only if $A \subseteq Center(B)$.

Theorem 2. Let $S$ be a semigroup and let $A,B \in Sub(S)$ such that $A \subseteq B$ then $A,B$ commute iff $A \subseteq Center(B)$.

Proof. Let $B$ be a subsemigroup then we will show that $Center(B)$ commutes with $B$. Let $c \in Center(B)$ and $b \in B$. Then by the definition of the center $cb = bc$. It follows that $Center(B)$ and $B$ commute, now by theorem 1 if we have $A \subseteq Center(B)$ then $A$ and $B$ commute.

Conversely, suppose that $A \subseteq B$ and $A$ commutes with $B$ this means that $\forall x \in A, y \in B$ we have $xy=yx$. The center of $B$ is equivalent to $\{z \in B : \forall y \in B : zy=yz \}$. By the fact that $A \subseteq B$ we have that every element $x$ of $A$ is in $B$ and by the fact that $A$ and $B$ commute we have $\forall y \in B : xy=yx$. It follows that $x \in Center(B)$. By the fact that every element of $A$ is in the center of $B$ we have $A \subseteq Center(B)$. $\square$

Monogenic subsemigroups:
There is a natural mapping from any semigroup to its lattice of subsemigroups $g : S \to Sub(S)$ defined by mapping any element to the monogenic subsemigroup it generates. \[ g : S \to Sub(S) \] \[ g(x) = cl_{Sub(S)}(\{x\}) \] The kernel of this map is the generator equality relation of the semigroup and its image is the subalgebra system consisting of all monogenic subsemigroups.

Theorem. Let $S$ be a semigroup then $x,y$ commute iff $g(x),g(y)$ commute.

Proof. If $g(x)$ and $g(y)$ commute then we have that $x,y$ commute because $x \in g(x)$ and $y \in g(x)$. Conversely, suppose that $xy = yx$ and consider any element $x^n$ in $g(x)$ and $y^n$ in $g(y)$. Then we will show that $x^ny^n = y^nx^n$. The base case is that $x^ny^n = yx^n y^{n-1}$. Then for any $m$ less then $n$ we have that $y^mx^ny^{n-m} = y^{m+1}x^n y^{n-m-1}$. $\square$

As the commutativity of elements is determined entirely be the monogenic subsemigroups that they generate, it follows that generator equality is a subrelation of adjacency equality. This has been proved before, but it never hurts to restate a corollary.

Corollary. generator equality is a subrelation of adjacency equality

If we have that $G$ is the commuting graph on elements and $G'$ is the commuting graph on subsemigroups then $g : G \to G'$ is a morphism in the category of graphs from $G$ to $G'$ and so we have a second corollary.

Corollary. $g : S \to Sub(S)$ is a graph homomorphism from the commuting graph of elements to the commuting graph of the subsemigroup lattice

It follows that the commutativity graph of the subalgebra system consisting of all monogenic subsemigroups of a semigroup is the commuting graph of the semigroup condensed by generator equality. It doesn't necessarily have to be the overall condensation of the commuting graph because two elements can be commutativity equal even if they don't generate each other. However, the condensation of the commuting graph on elements and the condensation of the commuting graph on monogenic subsemigroups do coincide.

Direct product decompositions:
Let $A,B,C$ be a family of monoids with identity elements $1_A, 1_B, 1_C$. Let $A \times B \times C$ be the direct product of all of these monoids then we can form submonoids $A' : \{(x,1_B,1_C)\}$, $B' : \{(1_A,x,1_C)\}$, $C' : \{(1_A,1_B,x)\}$. The family of submonoids $\{A',B',C'\}$ forms a commuting clique. This can be generalized to direct products of any size. This is the quintessential example of subsemigroup commutativity.

Definition. let $S$ be a monoid and let $a,b$ be elements of the monoid $S$ then $a$ and $b$ are independent provided that there are monoids $M_1,M_2$ and a direct product decomposition $S = M_1 \times M_2$ with submonoids $M_1' = \{(x,1_B)\}$ and $M_2' = \{(1_A,x)\}$ such that $x \in M_1$ and $y \in M_2$.

It is not hard to see that independent elements commute, because they are part of commuting pairs of submonoids in a direct product decomposition. The point of this definition is to formalize independence (in the sense of direct products) of elements of a semigroup. Often times commuting elements are seemingly independent in the sense that they effect different things, but that is not always the case, and this distinguishes when that is the case. In general, we see that the components of a direct product decomposition commute.

This is one final case worth mentioning. Recall that meet-minimal normal subgroups commute and if they are also join-maximal they form a direct product decomposition of the group. This is an important special case of the commutativity of submonoids in a direct product decomposition, and it demonstrates the utility of commutativity of subgroups in group theory.

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