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
    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$ 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$ 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$ 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$ 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$ 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$ 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$ 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$ 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$ Nov 27, 2016 at 19:48

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.