I'm looking for a reference for the statement that almost every partial order on $n$ elements has trivial automorphism group. I've been told that this is a folklore result. Does anyone know of a good reference?
$\begingroup$
$\endgroup$
5
-
1$\begingroup$ Not for partial orders, but for many classes of structures, check out Ralph Freese and his 1990 article "On the two kinds of probability in algebra". It talks about labeled versus unlabeled structures, and notes how probabilities for them are similar since most automorphism groups will be trivial. You might find something useful in his bibliography. $\endgroup$– The Masked AvengerCommented Mar 6, 2014 at 17:11
-
$\begingroup$ If you let $L$ be a linear extension of your partial order, then it seems you can almost always construct at least some automorphisms by swapping adjacent elements of $L$. The only time this wouldn't work is if your partial order is already a total order. Am I missing something here? $\endgroup$– Kevin P. CostelloCommented Mar 6, 2014 at 19:23
-
1$\begingroup$ @KevinP.Costello Could you explain why one almost always gets an automorphism? (It's clear that not just any pair of adjacent elements of $L$ can be swapped: for example, adjacent elements may have different degrees in the comparability graph that corresponds to the underlying partial order.) $\endgroup$– Andrew UzzellCommented Mar 7, 2014 at 12:27
-
$\begingroup$ @AndrewUzzell, and that indeed is what I was missing. Sorry about the mistake. $\endgroup$– Kevin P. CostelloCommented Mar 7, 2014 at 18:24
-
$\begingroup$ Remark: the statement that among isomorphism classes, the number of "rigid" ones is larger, is stronger. Indeed, the counting is then different since in counting orders, rigid ones occur $n!$ times while non-rigid ones occur less times. $\endgroup$– YCorCommented Aug 7, 2021 at 10:44
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Prömel (1987) proves a more general statement of rigidity for many classes of structures. In particular he has:
Corollary 2.3. Let $P^u(n)$ denote the number of unlabeled partial orders on an $n$-element set. Then there exists a constant $s$ such that for all $n$ $$ P^u(n) \le \frac{P(n)}{n!} \left(1 + \frac{s}{2^{n/4}} \right), $$
and as a consequence,
Corollary 2.3.a. Almost all partial orders are rigid, i.e., have no non-trivial automorphism.
Prömel, Hans Jürgen, Counting unlabeled structures, J. Comb. Theory, Ser. A 44, 83-93 (1987). ZBL0618.05029.
answered Aug 7, 2021 at 10:23