2
$\begingroup$

An exercise in Stanley's Enumerative Combinatorics (Chapter 3, ex. 8) asked for an example of a finite self-dual poset, (i.e. there is a bijection $f: P\to P$ such that $s\le t \Longleftrightarrow f(s) \ge f(t)$) for which there is no such bijection $f$ satisfying $f(f(t)) = t$ for all $t \in P$.

I'm interested in how many of these such posets exist for a given order. Has there been any result obtained about this? It seems like an interesting problem, but I struggled to find a single one (I would put the Hasse diagram here, but I'm not good enough at $\LaTeX$ to do that) , much less count them.

I posted this question on Math.SE, but it didn't get much of a response, so perhaps the question is better suited for this website.

$\endgroup$

1 Answer 1

7
$\begingroup$

There is a 12-element poset $P$ satisfying the stated condition. Let $Q$ be any self-dual poset that does not have $P$ as a connected component. Then the disjoint union $P + Q$ also satisfies the condition. Hence a lower bound for the number of $n$-element posets satisfying the condition is $d(n-12)-d(n-24)$, where $d(m)$ is the number of self-dual $m$-element posets. I suspect that this lower bound is not far from the truth. More specifically, if $f(n)$ is the number of $n$ element posets satisfying the condition, then it shouldn't be too hard to show that $\log f(n)\sim \log(d(n-12)-d(n-24))\sim \log d(n)$. I don't know whether anyone looked at the asymptotics of $d(n)$. Since the total number $g(n)$ of $n$-element posets satisfies $\log g(n)\sim \frac{n^2}{4}\log 2$, we easily get that $\log d(n)$ is asymptotically at least as large as $\frac{n^2}{16}\log 2$. This suggests the question: is $\log d(n)\sim \frac{n^2}{16}\log 2$? If not, what constant should replace $1/16$?

Addendum. In fact, since $d(n-12)-d(n-24)<f(n)<d(n)$ and $d(n)>g(n/2)$, it follows that $\log f(n)\sim \log d(n)$.

$\endgroup$
1
  • $\begingroup$ Very cool. And who better to answer the question. Thanks. $\endgroup$ Sep 28, 2013 at 1:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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