Even smaller universal posets

Abstract

We show that for every $\eta >0$ and sufficiently large $n$, there exists a poset of size $2^{(1+\eta )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.