5
$\begingroup$

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?

$\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$ Mar 6 '14 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$ Mar 6 '14 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$ Mar 7 '14 at 12:27
  • $\begingroup$ @AndrewUzzell, and that indeed is what I was missing. Sorry about the mistake. $\endgroup$ Mar 7 '14 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$
    – YCor
    Aug 7 at 10:44
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.