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$ Commented 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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .