Optimal embeddings of posets in hypercubes

Given a finite poset P , the hypercube-height, denoted by ⁎ h ⁎ ( 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 P . The hypercube-width, denoted by ⁎ w ⁎ ( P ) , is the smallest w such that the subsets of [ w ] of size at most ⁎ h ⁎ ( P ) contain an induced copy of P . In other words, ⁎ h ⁎ ( P ) asks how ‘low’ can a poset be embedded, and ⁎ w ⁎ ( 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 ⁎ ( P ) ≤ | 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 ⁎ ( P ) ≤ | P | 2 / 4 , but they conjectured that in fact ⁎ w ⁎ ( P ) ≤ | P | for any finite poset 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.