Introduction

Let $X$ be a poset of all $n$-tuples, $x = (x_1, x_2, ..., x_n)$, where $0 \leq x_i \leq m_i - 1$ for $i = 1, ..., n$ together with the relation $x \prec y$ defined so that for $y=(y_1,y_2, ..., y_n)$, $x \prec y$ if and only if $x_i \leq y_i$ for all $1 \leq i \leq n$.

This poset is a bounded lattice in which $(m_1 - 1, m_2 - 1, ..., m_n - 1)$ is the greatest element and $(0, 0, ..., 0)$ is the least element.

I am trying to derive an upper bound on the sum of the size of the common prefixes of an (arbitrary) element with all incomparable elements with lower rank from an (arbitrary) antichain.

Definitions

For two elements $x = (x_1, x_2, ..., x_n)$ and $y=(y_1,y_2, ..., y_n)$ the size of the common prefix $s(x,y)$ is the maximal $k$, such that $x_i \leq y_i$ for $0 \leq i \leq k$. For example, $s((0, 0, 2, 0),(2, 2, 1, 0))= 2$, i.e., they have a common prefix of length $2$.

The rank of an element $x$ is the sum of its components: $rank(x) = \sum\limits_{i=1}^{n}x_i$

Two elements $x$ and $y$ are comparable if $x \prec y$ or $y \prec x$. We denote comparability of two elements $x$ and $y$ with $x \bot y$ and incomparability with $x||y$.

An antichain is a subset of the elements of $X$ which are pairwise incomparable.

Problem statment

For a given poset $X$, I want to find an upper bound $b$ such that for any element $x \in X$ and any antichain $A \subset X$ the following holds: $\sum\limits_{a \in A:~rank(a)<rank(x)~\wedge~a||x} s(a,x) \leq b$.

What have I done so far?

The closest structure that I could find is the chain product poset studied in Carroll et al. "Counting Antichains and Linear Extensions in Generalizations of the Boolean Lattice"1. It is a special case of the structure considered here, with $m_1 = m_2 = ... = m_n = m$.

Let $c$ be the cardinality of a maximum antichain of the chain product poset constructed from $X$ by choosing $m = max(m_1, m_2, ... m_n)$. It follows that $c * n$ is an upper bound for the number investigated here. Presumably, the bound is significantly overestimated, as this approach simply assumes the largest possible common prefix with all elements from the largest possible antichain. It does not consider the fact that we are only interested in incomparable elements with lower rank. In addition, most $m_i$s from $X$ will actually be smaller than $m$, meaning that the constructed chain product poset is a superset of $X$.

Regarding the number $c$, in the article by Carroll et al. it is stated that any chain product poset is a Sperner poset and that, as a consequence, the largest antichain is a level set. If I understand the paper correctly, the level of an element equals its rank and the structure forms a ranked poset. I concluded that the size of the middle level, which contains all elements with rank $\lfloor \frac{(m-1)*n}{2} \rfloor$, equals the size of the largest antichain. The paper cites an article by Mattner et al. 2, which shows that the size of the middle level is $m^n \sqrt{\frac{6}{\pi(m^2-1)n}}(1+\mathcal{o}(1))$. In addition to the formula provided by Mattner et al., I have found a webpage discussing Balls in Bins With Limited Capacity, which provides formulas that can be used to calculate the size of any level in the structure originally discussed here as well as in chain product posets.

Questions

Does anyone know a better upper bound? Are my assumptions and the current upper bound correct? Is there any common name for the type of poset considered that I can use to find information about it?Has this structure been studied somewhere? Are there any different ways of looking at the problem? As I am by no means a mathematics wizard, any help on this question is highly appreciated!