8
$\begingroup$

I've come across a family of posets which appear to have a couple of remarkable enumerative properties, and I'm wondering whether anyone has seen these before.

Take $n\geqslant3$, and let $\preccurlyeq$ be a partial order on the set $\{1,\dots,n\}$. Say that $\preccurlyeq$ has property M if:

  1. There is a unique way to write $\{1,\dots,n\}$ as the union of two $\preccurlyeq$-chains, and

  2. $\preccurlyeq$ is maximal with this property, i.e. any refinement of $\preccurlyeq$ destroys the uniqueness in (1).

For example, if $n=5$, there are four partial orders (up to isomorphism) with property M. Given as sets of covers, these are as follows:

$$\{(1,2),(2,3),(3,4)\},\{(1,2),(2,3),(2,5),(4,5)\},\{(1,3),(3,4),(2,3),(2,5)\},\{(1,3),(3,5),(2,4),(1,4),(2,5)\}$$

Now here are the (apparent) remarkable properties:

  1. Up to isomorphism, there are exactly $2^{n-3}$ partial orders on $\{1,\dots,n\}$ with property M.

  2. If $\preccurlyeq$ has property M, then the size of $\preccurlyeq$ (i.e. the number of pairs $i\preccurlyeq j$) is $\binom n2+1$.

I've checked these properties for $n\leqslant8$. Does anyone know whether they are true generally?

(I also have a conjectural construction of all partial orders with property M, coming from representation theory, but I can't prove anything!)

$\endgroup$
1
  • 1
    $\begingroup$ In remarkable property 2, should $\binom n2$ be $\binom n2 +1$? $\endgroup$ Aug 8, 2017 at 9:22

1 Answer 1

8
$\begingroup$

I claim:

A poset with property M has precisely two maximal elements.

Precisely one maximal element is greater than every non-maximal element. Call this the supermaximal element.

Removing the supermaximal element (if $n>3$) leaves a poset with property M.

So there is a unique way to build any example from the $n=3$ example by repeatedly adding a new supermaximal element.

For an $n=k$ example, there are two ways to add a new supermaximal element (choose which of the existing maximal elements remains maximal), each of which increases the "size" by $k$.

Now the two properties you observed follow by induction.

$\endgroup$
0

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.