Smaller universal posets
Paul Bastide, Carla Groenland, Rajko Nenadov · 2025
Read Smaller universal posets by Paul Bastide, Carla Groenland, Rajko Nenadov (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-17820.txt.
Introduction
Paul Bastide, Carla Groenland, and Rajko Nenadov shrink a poset that must hold all small posets inside it. A poset is a set with a partial order, where some pairs can be compared and some cannot. Their 2025 note gives a size bound for such a host set.
For each size n, they build a host whose size stays below a bound tied to n. The host holds each poset of that size as an induced part, with order kept intact. A smaller host means less waste in this classic maths ask. The note states the bound in a short, clean form.
Catalog record
| CREATOR | Paul Bastide, Carla Groenland, Rajko Nenadov |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 24 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-17820
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Smaller universal posets Paul Bastide, Carla Groenland, Rajko Nenadov Abstract We show that there is a constant C > 0 C>0 such that for each integer n ≥ 1 n\geq 1 , there is a poset on at most 2 2 n / 3 + C n 2^{2n/3+C\sqrt{n}} elements that contains each n n -element poset as an (induced) subposet. 1 Introduction A graph U is said to be universal for a family of graphs \mathcal{G} if for any graph G\in\mathcal{G} , U contains 1 1 1 In this work contains will always refers to the induced containment relation. G . Moreover if U\in\mathcal{G} , then we call U faithful . This concept emerged in the 1950s [ Fra53 , Joh56 , Rad64 , Moo65 ] , and has been extensively studied since then [ KP84 , Die85 , KMP88 , FK97a , FK97b , Kom99 , CSS99 , CS01 , CS07 , CT07 , CS16 , HMŠ+21 , BEG+25 ] . A well-known example of this notion is the Rado graph . Ackermann [ Ack37 ] , Erdős and Rényi [ ER63 ] and Rado [ Rad64 ] independently proved that the Rado graph is universal for the class of all countable graphs. The Rado graph has, since then, proven to be useful in solving numerous other questions in combinatorics (see the following surveys [ Cam97 , Cam01 ] ). Universal structures are also of interest to the computer science community because of their close connection to efficient data structures [ FK10 , AKTZ15 , AAH+17 , MN16 , ADK17 , ACK+01 , EJM23 ] . Similarly, a poset U is said to be universal for a family of posets \mathcal{P} if U contains all posets P\in\mathcal{P} . This notion is arguably even older than universality for graphs. Indeed, the existence of a countable universal poset containing all countable posets has been proven multiple times [ Fra53 , Jón56 , Joh56 ] and, as written in [ HN05 ] , in the context of category theory, “ motivated the whole research area ”. For finite posets, similar questions have been asked. This paper studies the following natural problem which was highlighted in the conclusion of [ BEGS21 ] , and originates from a question posed by Hamkins [ Ham10 ] . 1.1 . What is the minimum order of a poset that contains every n -element poset? Posets have also been studied through the graph they induce, called comparability graphs 2 2 2 See Section 2 for a formal definition. . For any pair of posets P and U where P is contained in U , the comparability graph of P will be an induced subgraph of the comparability graph of U . This means that an upper bound for 1.1 also provides an upper bound to the following problem. 1.2 . What is the minimum order of a comparability graph which contains every n -vertex comparability graph as an induced subgraph? The Boolean lattice Q_{n}=(2^{[n]},\subseteq) on 2^{n} elements, consisting of the subsets of \{1,\dots,n\} as elements and set inclusion \subseteq as partial order, is well-known to contain all posets on n elements (see Proposition 2.2 ), and therefore gives an upper bound of 2^{n} to both 1.1 and 1.2 . Hamkins [ Ham10 ] asked whether any substantial improvement can be made on this upper bound. Regarding lower bounds, the size of a universal poset U is at least 2^{(1+o(1))n/4} , which can be derived from the following simple information-theoretic argument. Consider two antichains of size n/2 , one containing minimal elements and the other maximal elements, and any subset of the (n/2)^{2} possible order relations from a minimum to a maximum between the two antichains. From this, we deduce that there are at least 2^{n^{2}/4}/n! posets on n elements. A universal poset U must then satisfy \binom{|U|}{n}\geq 2^{(1+o(1))n^{2}/4} , which implies the lower bound |U|\geq 2^{(1+o(1))n/4} . We remark that the lower bound on the number of posets above is asymptotically correct, since Kleitman and Rothschild [ KR70 ] proved that there are 2^{n^{2}/4+O(n^{3/2}\log n)} posets on n elements. The lower bound 2^{(1+o(1))n/4} and upper bound 2^{(1+o(1))n} were the best bounds known for 1.1 and 1.2 before our work. We improve on the upper bound by showing that an exponentially small fraction of the Boolean lattice already embeds all posets on n elements. 1.3 . There is a constant C>0 such that for any n\in\mathbb{N} , there is a subposet P_{n} of (2^{[n]},\subseteq) on at most 2^{\frac{2}{3}n+C\sqrt{n}} elements that contains all n -element posets. In particular, there is an induced subgraph U_{n} of the hypercube comparability graph which contains all comparability graphs on n vertices as an induced subgraph with |V(U_{n})|\leq 2^{\frac{2}{3}n+C\sqrt{n}} . Further related work A relaxation of 1.2 , where the universal object representing all posets does not need to be a poset but can be any kind of data structure, has been the focus of considerable research. Munro and Nicholson [ MN16 ] designed a succinct data structure using only n^{2}/4+o(n) bits for this problem, which supports precedence queries in constant time. Dulȩba, Gawrychowski and Janczewski [ DGJ20 ] provided a data structure, called comparability labelling scheme , which assigns short labels to each element of the posets such that, given the labels of two elements, and no other information regarding the poset, it is possible to decide whether these two elements are comparable. In [ DGJ20 ] , the authors showed that (1+o(1))n/3 bits of label per element is sufficient. This was improved to (1+o(1))n/4 by Bonamy, Esperet, Groenland and Scott [ BEGS21 ] , which is asymptotically optimal. This last results imply the existence of a universal graph on 2^{(1+o(1))n/4} vertices that contains all comparability graphs as induced subgraphs. However, as also mentioned in [ BEGS21 ] , these universal graphs do not need to be (and will not be) comparability graphs themselves so do not yield a universal poset. The strength of the hypercube as a universal structure has also been studied in terms of the minor relation: Benjamini, Kalifa and Tzalik [ BKT25 ] showed that the d -dimensional hypercube \{0,1\}^{d} contains all graphs with O(2^{d}/d) edges and no isolated vertices as a minor, and this bound was shown to be best possible by Hogan, Michel, Scott, Tamitegama, Tan and Tsarev [ HMS+25 ] . In [ FK10 ] , Fraigniaud and Korman studied data structures called ancestry labeling schemes , which aim to assign a label to every vertex in a tree such that, for any two vertices u and v , it is possible to determine whether u is an ancestor of v by inspecting only the labels of u and v . They used this labeling scheme, to design small universal posets for posets of bounded tree-dimension (see [ FK10 ] for formal definitions). In the context of finite graphs, Gol’dberg and Livshits [ GL68 ] showed the existence of a tree on 2^{O(\log^{2}n)} vertices which is universal for the class of n -vertex trees, which was later proven to be the optimal order of magnitude [ CGC81 ] . Recently, Bergold, Iršič, Lauff, Orthaber, Scheucher and Wesolek [ BIL+24 ] proved that both the