Optimal embeddings of posets in hypercubes
Discrete Mathematics · 2026-11 · 349 (11) · 115316
DOI: 10.1016/j.disc.2026.115316 ↗Kurz gefasst
Fachartikel in der Zeitschrift Discrete Mathematics, 2026-11. Verfasst von Tomáš Flídr und 2 weiteren Autor:innen. Die Arbeit nennt 8 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
Given a finite poset $\mathcal P$, the hypercube-height, denoted by $h^*(\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^*(\mathcal P)$, is the smallest $w$ such that the subsets of $[w]$ of size at most $h^*(\mathcal P)$ contain an induced copy of $\mathcal P$. In other words, $h^*(\mathcal P)$ asks how `low'can a poset be embedded, and $w^*(\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^*(\mathcal P)\leq |\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^*(\mathcal P)\leq|\mathcal P|^2/4$, but they conjectured that in fact $w^*(\mathcal P)\leq |\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.
Zitieren
APA
Flídr, T., Ivan, M., & Jaffe, S. (2026). Optimal embeddings of posets in hypercubes. Discrete Mathematics, 349(11), 115316. https://doi.org/10.1016/j.disc.2026.115316
Vancouver
Flídr T, Ivan M, Jaffe S. Optimal embeddings of posets in hypercubes. Discrete Mathematics. 2026;349(11):115316. doi:10.1016/j.disc.2026.115316
BibTeX
@article{Fldr2026,
author = {Flídr, Tomáš and Ivan, Maria-Romina and Jaffe, Sean},
title = {Optimal embeddings of posets in hypercubes},
journal = {Discrete Mathematics},
year = {2026},
volume = {349},
number = {11},
pages = {115316},
doi = {10.1016/j.disc.2026.115316}
}
EUVIMED