Optimal Embeddings of Posets in Hypercubes

Abstract

Given a finite poset $\mathcal{P}$, the hypercube-height, denoted by $h^{\ast }(\mathcal{P})$, is defined to be the minimum $h$ such that there exists a natural number $n$ for which the subsets of $[n]$ of size at most $h$ contain an induced copy of $\mathcal{P}$. The hypercube-width, denoted by $w^{\ast }(\mathcal{P})$, is the smallest $w$ such that the subsets of $[w]$ of size at most $h^{\ast }(\mathcal{P})$ contain an induced copy of $\mathcal{P}$. In other words, $h^{\ast }(\mathcal{P})$ asks how `low' can a poset be embedded, and $w^{\ast }(\mathcal{P})$ asks for the first hypercube in which such an `optimal' embedding occurs. These notions were introduced by Bastide, Groenland, Ivan and Johnston in connection to upper bounds for the poset saturation numbers. While it is not hard to see that $h^{\ast }(\mathcal{P})\le |\mathcal{P}|-1$ (and this bound can be tight), the hypercube-width has proved to be much more elusive. It was shown by the authors mentioned above that $w^{\ast }(\mathcal{P})\le |\mathcal{P}{|}^2/4$, but they conjectured that in fact $w^{\ast }(\mathcal{P})\le |\mathcal{P}|$ for any finite poset $\mathcal{P}$. In this paper we prove this conjecture. The proof uses Hall's theorem for bipartite graphs as a precision tool for modifying an existing copy of our poset.

7 pages, 1 figure