2
$\begingroup$

Let $\ h\ $ be a natural number. A partially ordered set (poset) $\ X\ $ is uniformly high, and of height $\ h\quad\Leftarrow:\Rightarrow\quad $ every $\ x\in X\ $ is a member of a sequence $\ x_1 < \ldots < x_h\ $ for some $\ x_1\ \ldots\ x_h\in X\ $ (which depend on $\ x\ $) while there do not exist any $\ x_0\ \ldots\ x_h\in X\ $ such that $\ x_0<\ldots<x_h.$

Consider the number $\ pos(n;h)\ $ of all posets in $\ \{1\ \ldots\ n\}\ $ of uniform height $\ h.$

I don't expect an exact computation of $\ pos(n;3)\ $ for large $\ n\ $ (would be nice but it seems quite unlikely). Thus,

what would be sharp approximations of $\ pos(n;3)\ ?$

$\endgroup$
5
  • 2
    $\begingroup$ In other words, every element lies in a chain of length $h$, but there are no chains of length $h+1$? $\endgroup$
    – Asaf Karagila
    Commented Oct 26, 2016 at 17:43
  • 1
    $\begingroup$ I assume you want to count the number of non-isomorphic posets, that is, for example, that for $n=3$, $\mbox{pos }(3;3)$ does not count both the posets $1<2, 2<3$ and $1<3,3<2$. For concreteness, this would say $\mbox{pos }(3;3)=1$ and $\mbox{pos }(4;3)=3$. Is this the right interpretation of your question? $\endgroup$ Commented Oct 26, 2016 at 19:41
  • 1
    $\begingroup$ The condition as stated does not imply that there are no chains of length $h+1$. There could be a chain of length $h+1$, but not every element is contained in such a chain. So what exactly is meant? A somewhat related paper is sciencedirect.com/science/article/pii/S0021980069801006. This counts labelled posets for which every maximal chain has height $h$. This is not the same, however, as saying that every element is contained in a chain of height $h$ and that there are no chains of height $h+1$. $\endgroup$ Commented Oct 27, 2016 at 1:42
  • $\begingroup$ Traditionally, people compute both. As I have formulated the question, all posets (the partial ordering relations in $\ \{1\ \ldots\ n\}\ $ are counted (as different)--the non-identical isomorphic relations are counted as different. E.g. $\ pos(2;2) = 2\ $ while there is only $1$ isomorphic class. Also, according to the definition above, $\ pos(3;3)=6\ $ and again not $1$. $\endgroup$ Commented Oct 27, 2016 at 1:47
  • $\begingroup$ @RichardStanley, thank you for your comment. I have edited the question to make my intention free from any linguistic traps. Every element should belong to an $n$-chain while there should be no $(n+1)$-chain. $\endgroup$ Commented Oct 27, 2016 at 1:57

1 Answer 1

1
$\begingroup$

Obtaining an expression for $\mbox{pos}(n;3)$ is somewhat easier than obtaining the analagous expression for the number of isomorphism classes. In the case at hand, the number of non-identical uniform-height-$3$ posets is obtained by the following reasoning:

Consider the "middle" set of numbers $\{b_m\}$ such that $\forall m :( (\exists a: a < b_m) \wedge (\exists c: b_m < c))$. In a graphical picture, there are three rows of numbers, with $<$ arrows connecting top row numbers to middle row numbers and middle row numbers to bottom row numbers; $\{b_m\}$ is the middle row, and we can label its count $b$.

Let there be $a$ values of $x: x < b_m$ for some $m$, and $c$ values of $x: x < b_m < x$ for some $m$; so that $n=a+b+c$. Then to form a uniform-height-$3$ poset with row structure $(a,b,c)$ we must follow these rules:

  • Select which $b$ elements will be in the middle row, and which $a$ elements will be in the top row. This gives an overall factor of $\binom{n}{b}\binom{n-b}{a}$

  • Each of the $a$ top-row elements must connect (via a $<$ relationship) with some non-empty subset of the middle row elements; this provides a factor of $(2^b-1)^a$.

  • None of the $b$ elements may be devoid of any connections to the $a$ row. This subtracts, from the previous factor, $(2^{b-1}-1)^a$. However, this double subtracts cases where two elements of the $b$ row are devoid of these connections. Overall, imposition of the condition that for all $b_m$ there must be an $a$ such that $a<b_m$ turns the previous factor into $$ \sum_{j=0}^b (-1)^j \binom{b}{j}(2^{b-j}-1)^a $$

  • Similarly, the possibilities of connections between the middle and bottom rows provides a factor of $$ \sum_{k=0}^b (-1)^k \binom{b}{k}(2^{b-k}-1)^c $$

Correction based on comment by OP

  • After specifying the relationships as above, every chain is of length $3$. Since the definition of uniformly high does not preclude some connections of length $2$, each element of row $a$ may have a direct relationship with any subset of the elements of row $c$. This gives a further factor which must be smaller than $2^{ac}$, because the direct connections which replicate indirect connections must not be counted. (That is, there is no difference between $(1<2,2<3)$ and $(1<2,2<3,1<3)$.)

It is difficult to account for the possibility of direct connections (forming chains of length $2$), and I therefore have no results for the problem as posed.

For posets in which every chain is of length precisely, $3$, combining these factors, and summing over all tuples $(a,b,c)$ that add to $n$, we obtain

$$ \mbox{posExact}(n;3) = \sum_{a=1}^{n-2} \,\,\,\sum_{b=1}^{n-1-a}\left[ \binom{n}{b}\binom{n-b}{a} \left( \sum_{j=0}^b (-1)^j \binom{b}{j} (2^{b-j}-1)^a \right) \\\left( \sum_{k=0}^b (-1)^k \binom{b}{k} (2^{b-k}-1)^{n-a-b} \right) \right] $$

The next observation is that for $n>37$, $$\log\left(\mbox{posExact}(n;3) \right) < n^2/5$$. Using the usual Stirling approximation tricks, one can show that for sufficiently large $n$,
$$\frac{\log\left(\mbox{posExact}(n;3) \right)}{n^2}$$ is a decreasing function of $n$; in this case, "sufficiently large $n$ is $n>7$ (the peak is reached at $n=7$). Apparently, for all $n\geq 3$, $\log\left(\mbox{posExact}(n;3) \right) > n^2/6$ but I can't seem to prove that. (It is true at least up to $n=800$.)

Numerically, for sufficiently large $n$, it appears that $$ e^{0.1719n^2} < \mbox{posExact}(n;3) < e^{0.1733n^2} $$

$\endgroup$
5
  • $\begingroup$ @MarkFischer, the situation doesn't want to be this simple. A bottom element $a$ is connected indirectly, via the middle row, to a set $C_a$ of the top elements. Then there can be also other connections--an arbitrary set of the direct connections from $a$ to elements of $\ C\setminus C_a,\ $ where $C$ is the top row. This is why the case of height $h=3$ is the first non-simple case, it is already something of a mess to compute it. $\endgroup$ Commented Oct 28, 2016 at 2:58
  • $\begingroup$ Your second point, about direct connections between rows $a$ and $c$ is right; I overlooked those, assuming that every chain must be of length 3. However, this just adds a factor of $2^{ac}$ to each term in the sum. Your first point, about indirect connections, is already taken care of in the expression given. Any indirect connection is a combination of connections between $a$ and $b$ and those between $b$ and $c$, so if we get those right, we do not need to separately account for indirect connections between $a$ and $c$. $\endgroup$ Commented Oct 28, 2016 at 15:25
  • 1
    $\begingroup$ I note (see correction in the answer) that the possibility of direct connections is much more subtle than just factors of $2^{ac}$. So my statement that the full problem is much easier than the problem of counting the isomorphism classes is not true. $\endgroup$ Commented Oct 28, 2016 at 16:51
  • $\begingroup$ Mark, thank you for your answer and comments. I'd be glad if you continue, I hope that you will make further progress. This theme is one of my hobbies to which I come back a time and again, hoping for a definite answer, at least for a clear structure if not outright a truly efficient algorithm. Each time I get more but am still far from anything definite. $\endgroup$ Commented Oct 29, 2016 at 0:32
  • $\begingroup$ Just by the way of terminological clarification, the row $a$ comprises the minimal elements, the row $c$ comprises the maximal elements, and row $b$ comprises the rest; row $a$ elements have height 0 and row $b$ elements have height 1; "no direct connections" condition means that the poset is graded (here: all maximal chains have the same length), so that the height (or rank) of every row $c$ (i.e. maximal) element is 2. $\endgroup$ Commented Nov 27, 2016 at 19:48

You must log in to answer this question.

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