A (finite) poset $P = (X, <)$, or partially ordered set, is a (finite) set $X$ equipped with a transitive antisymmetric relation $<$; it can be equivalently seen as a DAG $G = (X, E)$ that is transitive (whenever $(x, y) \in E$ and $(y, z) \in E$ then $(x, z) \in E$).An automorphism of $P$ is a bijection $f$ from $X$ to $X$ such that $x < y$ iff $f(x) < f(y)$, in other words, both $f$ and $f^{-1}$ are order-preserving. The automorphism is fixed-point-free if there is no $x$ such that $f(x) = x$. Of course, the identity is always an automorphism (which is not fixed-point-free); other automorphisms are said to be non-trivial. Both automorphisms and fixed-point-free automorphisms are well-studied natural notions for posets; intuitively, posets that have non-trivial (fixed-point-free) automorphisms have a certain symmetry.Is anything known about the complexity of determining if a poset has a non-trivial automorphism, or fixed-point-free automorphism? Or the complexity of counting the number of automorphisms, or fixed-point-free automorphisms?For DAGs that are not transitive, determining if a DAG has a non-trivial automorphism is in NP and its complexity is unknown, like that of graph isomorphism (source). So, while the problem for transitive DAGs is still in NP, it should not be realistic to prove hardness as that would imply hardness of that open problem; but maybe the graph being transitive makes the problem easier (solvable in polynomial time)?For other natural counting problems about posets, the problems of antichain counting (antichains are subsets of elements that are all pairwise incomparable), or of linear extension counting (linear extensions are the way to extend the partial order to a total order by adding more comparability relations), are all #P-complete to compute. (source and source). Is it also hard to count automorphisms, then?
Complexity of counting poset automorphisms
cc.complexity theory;counting complexity;directed acyclic graph;partial order;automorphism
Graph isomorphism for bipartite graphs is as hard as graph isomorphism for general undirected graphs. Considering bipartite posets (i.e., seeing bipartite graphs as Hasse diagrams of posets), you may see that counting the automorphisms of bipartite posets is as hard as counting the automorphisms of general undirected graphs.