0
$\begingroup$

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!

$\endgroup$
4
  • $\begingroup$ This is a good question which may be even more well received on Mathematics StackExchange. After a couple of days, if you don't get satisfaction here, I recommend posting it at math.stackexchange.com with a link to this question. Also, you might find it useful to fix n to 1, 2 , 3 successively and doing computations using those constraints. Of course, an upper bound will be suggested by letting x be an extreme element and A an extreme antichain, and the literature will support your work above. Gerhard "Post Your Computational Result Summary" Paseman, 2015.09.02 $\endgroup$ Sep 2, 2015 at 16:12
  • $\begingroup$ From what you've written, it looks like you're maximizing over all $x$. Clearly, the best choice of $x$ is the all zeros vector, since it will have a length $n$ common prefix with every element of the poset. $\endgroup$ Sep 3, 2015 at 3:56
  • $\begingroup$ Thank you very much for your comments @GerhardPaseman and @HughThomas! Of course, your are both correct and choosing the greatest element and the largest antichain will not only suggest and upper bound, but be the exact solution to the problem as I originally stated it. In fact, that is exactly what I did to derive my current upper bound. Your comments made me realize that I forgot to add an important additional restriction on the elements from the antichain that I need to consider: $\endgroup$ Sep 3, 2015 at 9:41
  • $\begingroup$ 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. This means that for choosing the greatest element and the maximal antichain this sum is actually 0, as the greatest element is comparable with all elements from the poset. I have updated the problem definition accordingly and I would be very grateful for any further feedback. $\endgroup$ Sep 3, 2015 at 9:42

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.