Even smaller universal posets

JÃ³zsef Balogh; Ramon I. Garcia; Marcelo Sales

combinatorics

Even smaller universal posets

arXiv:2607.12980

summary

The paper proves that for any small ε>0 and large n there exists a poset of size 2^{(1+ε)n/2} that contains every n‑element poset as an induced subposet, improving previous bounds using a transitivity‑preserving labeling scheme and the Szemerédi Regularity Lemma.

Abstract

We show that for every $I^\cdot > 0$ and sufficiently large $n$ , there exists a poset of size $2^{(1 + I^\cdot) n /2}$ containing all the $n$ -element posets as induced subposets. This improves a recent result of Bastide, Groenland and Nenadov. Our proof provides a labeling scheme preserving transitivity, inspired by the Boolean lattice. Among other tools, we use the SzemerÃ©di Regularity Lemma.

Topics & keywords

#universal posets #induced subposets #labeling schemes #boolean lattice #szemerédi regularity lemmauniversal posetinduced subposetszemerédi regularity lemmaboolean latticelabeling schemecombinatorial construction