Width of Join Semilattice in $\mathbb R^n$

60 Views Asked by At

Suppose $S$ is a join semilattice that can be generated by $m$ generators. I would like to know an asymptotic upper bound on the width of $S$ (the maximum cardinality of all antichains in $S$) under the condition that $S$ is a subsemilattice of $\mathbb R^n$, where the order on $\mathbb R^n$ comes from the product order on $\mathbb R$.

If we do not have the condition that $S \subseteq \mathbb R^n$, then the bound is $O\left(\binom{m}{m/2}\right)$ (where $m/2$ can be either $\lceil m/2 \rceil$ or $\lfloor m/2 \rfloor$). This bound is tight as it can be attained when $S$ is a free join semilattice on $m$ generators. However, in my situation, $n \ll m$, and I hope that the bound can be improved when $n$ is taken into consideration.

My current conjecture is that the width of $S$ could be $O(m^{n-1})$, but I don't really know how to think about this problem.

1

There are 1 best solutions below

0
On BEST ANSWER

Note that a join semilattice $S \subseteq \mathbb R^n$ generated by $(x_{11},\ldots,x_{1n}),\ldots,(x_{m1},\ldots,x_{mn})$ is contained in the Cartesian product $\{x_{11},x_{21},\ldots,x_{m1}\} \times \cdots \times \{x_{1n},x_{2n},\ldots,x_{mn}\}$, for this is a sublattice of $\mathbb R^n$. Then use Dilworth's theorem to obtain $\text{width}(S) \leq m^{n-1}$.