Pith. sign in

REVIEW 2 major objections 3 minor 42 references

Smaller universal posets

T0 review · 2 major / 3 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves that for every $n$ there is a subposet of the Boolean lattice $2^{[n]}$ with at most $2^{2n/3+C\sqrt n}$ elements that contains every $n$-element poset as an induced subposet.

desk verdict First real improvement over the 2^n Boolean-lattice upper bound for minimum universal posets, sound overall but with a repairable off-by-inclusion bug in Lemma 3.2 and a false convexity remark in Lemma 3.1. read the letter →

arxiv 2509.17820 v3 pith:YRDK6MY7 submitted 2025-09-22 math.CO

Paul Bastide , Carla Groenland , Rajko Nenadov This is my paper · ORCID
classification math.CO MSC 06A0705D05
keywords universalposetsBooleanlatticeinducedsubposetscomparabilitygraphsantichainchaindecompositionDilworth'stheorempartitionfunction
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper attacks a question asked by Joel David Hamkins: how many elements are needed in a single poset that contains every $n$-element poset as an induced subposet? The full Boolean lattice $2^{[n]}$ gives an upper bound of $2^n$, and the best lower bound known is only $2^{n/4+o(n)}$. The paper narrows this exponential gap by proving that a carefully chosen subposet of the Boolean lattice, of size at most $2^{2n/3+O(\sqrt n)}$, already contains every $n$-element poset. A sympathetic reader should care because this is the first improvement over the trivial $2^n$ upper bound for this problem, and it transfers directly to universal comparability graphs.

What carries the argument

The proof is carried by two encoding mechanisms inside the Boolean lattice. For posets whose largest antichain has size at most $a$, Dilworth's theorem gives a chain decomposition into $a$ chains; the paper encodes each element by the set of earlier chain-elements below it, keeping only the prefix of each chain, which yields a family of size at most $p(n)\,a(n/a+1)^a$, where $p(n)$ is the partition number. For posets with an antichain of size $a$, the paper chooses the least $\ell$ with $\binom{\ell}{\lfloor\ell/2\rfloor}\ge a$ and assigns each antichain element a distinct subset of a fresh $\ell$-coordinate block, all of the same size $\lfloor\ell/2\rfloor$; the equal size is what makes distinct antichain elements incomparable in the image. Elements below and above the antichain are encoded by down-sets and by not-above sets. Taking $a=\lfloor n/3\rfloor$ and using $p(n)=2^{O(\sqrt n)}$ balances the two families at $2^{2n/3+O(\sqrt n)}$.

What would settle it

Apply Lemma 3.2 to the family of all $n$-element posets with a largest antichain of size $a=\lfloor n/3\rfloor$ and check the equivalence (1) for each one; in particular, build a poset in which two antichain elements have identical below-sets and above-sets but distinct equal-size labels, and verify whether their images remain incomparable. Any poset for which (1) fails would disprove the claimed $2^{2n/3+O(\sqrt n)}$ bound.

Watch

Extended reading notes

Core claim

The central result is Theorem 1.3: there is a constant $C$ such that for every $n$, some subposet $P_n$ of the Boolean lattice $(2^{[n]},\subseteq)$ on at most $2^{2n/3+C\sqrt n}$ elements contains all $n$-element posets as induced subposets. Equivalently, the minimum order of a universal poset, and the minimum order of a comparability graph universal for $n$-vertex comparability graphs, is at most $2^{(2/3+o(1))n}$. The proof achieves this by splitting the class of $n$-element posets according to antichain size: posets with no antichain larger than $\lfloor n/3\rfloor$ are embedded using a chain decomposition, while posets that do contain such an antichain are embedded by labelling the antichain with equal-size subsets of a separate coordinate block. The union of the two set systems is a subposet of $2^{[n]}$ of the claimed size.

Load-bearing premise

The large-antichain construction of Lemma 3.2 depends on encoding every element of the antichain by a distinct subset of a fresh coordinate block, all of the same size $\lfloor\ell/2\rfloor$; without that equal-size choice, distinct antichain elements would not be guaranteed incomparable images and the equivalence $u\le_P v\iff f(u)\subseteq f(v)$ could fail.

Editorial extensions

If this is right

  • The exponent $2/3$ replaces $1$ as the best known upper bound for both the minimum order of a universal poset and the minimum order of a comparability graph universal for all $n$-vertex comparability graphs.
  • Because the construction is a subposet of $2^{[n]}$, only $2^{2n/3+O(\sqrt n)}$ of the $2^n$ Boolean-lattice elements are needed, so the Boolean lattice is universal in a much smaller sub-slice than previously known.
  • The proof provides an explicit embedding for every $n$-element poset: a chain-decomposition prefix encoding for small-antichain posets and an equal-size antichain labelling for large-antichain posets.
  • Proposition 4.2 shows the new bound cannot be achieved by the naive down-set embedding: any subposet $S\subseteq 2^{[n]}$ that works for all posets through the standard map $v_j\mapsto\{i:v_i\le_P v_j\}$ must have size $2^{(1-o(1))n}$, so the improvement necessarily uses embeddings adapted to each poset.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The threshold $a=\lfloor n/3\rfloor$ is where the chain-decomposition family and the antichain family have equal exponential weight; a construction that interpolates between the two, or applies the antichain trick recursively to the region above the antichain, might lower the exponent further.
  • The equal-size subset trick for antichains is effectively a binomial labelling scheme; since comparability labelling schemes already produce $2^{(1/4+o(1))n}$-sized universal graphs that are not themselves posets, the $2/3$ barrier may come from requiring the universal object to be a comparability graph rather than from information content.
  • A testable design principle suggested by Proposition 4.2 is that beating $2^{2n/3}$ requires embeddings that use structure beyond a fixed ordering of the poset's elements, such as first compressing by a chain decomposition and then labelling the antichain of the compressed poset.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 3 minor

Summary. The paper studies the minimum order of a finite poset that contains every n-element poset as an induced subposet. The trivial upper bound is the Boolean lattice of size 2^n, and the previous best lower bound was 2^{(1+o(1))n/4}. The authors prove Theorem 1.3: there is a universal subposet of the Boolean lattice on at most 2^{2n/3 + C sqrt(n)} elements, giving an exponential improvement over the 2^n bound. The proof splits into two cases according to the width of the poset. For posets of width at most a, Lemma 3.1 uses Dilworth's theorem to decompose the poset into a chains and encodes each element by the initial segment of each chain that lies below it, yielding at most p(n) a (n/a + 1)^a subsets. For posets containing an antichain of size a, Lemma 3.2 encodes the antichain by equal-sized subsets of a separate coordinate block and encodes the elements below and above the antichain by their down-sets and up-sets in the remaining coordinates. Setting a = ceil(n/3) balances the two size estimates and gives the theorem. The same bound is shown to hold for universal comparability graphs.

Significance. If the proof is correct, this is a substantial advance on a natural problem highlighted by Hamkins and by Bonamy, Esperet, Groenland and Scott: it is the first exponential improvement over the trivial Boolean-lattice upper bound for Problem 1.1, and it simultaneously improves the upper bound for universal comparability graphs from 2^n to 2^{(2/3+o(1))n}. The construction is self-contained and uses only standard tools (Dilworth's theorem, the asymptotic partition function, and an elementary antichain encoding). The paper is clearly written and the main idea, splitting by width, is elegant. The two lemmas are mostly carefully argued, and the counting at the end is correct. The remaining issues are localized and repairable.

major comments (2)
  1. [Lemma 3.2, proof] The parameter b is defined as the number of elements x with x <=_P y for some y in A. Since A is an antichain, this definition includes all elements of A itself, but the construction and the counting treat b as the number of elements strictly below A. As written, the 'remaining n-a-b elements' should be n-b elements, and the elements of A would be counted both among the x_i and among the y_S, breaking the indexing and the equivalence (1). The proof works if b is redefined to count elements x with x <_P y for some y in A (or equivalently x <=_P y and x not in A). This is a load-bearing correction, because the counts of the three blocks x_i, y_S, z_j and the case analysis for (1) all depend on it.
  2. [Lemma 3.1, proof] The sentence claiming that the function f(z_1,...,z_a) = prod_i (z_i+1) is convex and therefore maximized at z_k = n/a is incorrect: this product of affine functions is not convex on the simplex. The intended bound is nevertheless true, since by AM-GM one has prod_i(z_i+1) <= ((sum_i(z_i+1))/a)^a = (n/a + 1)^a. The proof should replace the convexity justification with this AM-GM argument (and note that the bound holds regardless of integrality). Because Lemma 3.1's size estimate is one of the two pillars of Theorem 1.3, this needs to be corrected in the final version.
minor comments (3)
  1. [Lemma 3.2, Case 2] In the case where v = y_{S'} and S and S' have the same size, the text says that S is not a subset of S' and concludes that f(u) is not a subset of f(v). This conclusion also uses the fact that the only coordinates from the block [b+1, b+ell] appearing in f(y_S) come from S itself; adding this sentence would make the argument fully explicit.
  2. [Theorem 1.3, proof] Lemma 3.2 produces a subposet of the Boolean lattice 2^{[n-a+ell]}, while the proof of Theorem 1.3 takes a union of two set systems inside 2^{[n]}. The authors should state explicitly that subsets of [n-a+ell] are viewed as subsets of [n] by the natural inclusion, so that the union of the two families is indeed a subfamily of 2^{[n]}.
  3. [Lemma 3.1, proof] Dilworth's theorem gives a chain decomposition with at most a chains, but the proof then works with exactly a non-empty chains. This reduction is immediate (one can split chains), but it should be stated explicitly to avoid a gap in the presentation.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the 2n/3 exponent is set by balancing two independent size bounds, and both embedding lemmas are self-contained.

full rationale

The derivation chain is self-contained. Lemma 3.1 uses only Dilworth's theorem (Theorem 2.1), the folklore Boolean-lattice embedding (Proposition 2.2), and the Hardy–Ramanujan bound on p(n) (Theorem 2.3); the constructed family S_n(c_1,...,c_a) is an explicit set of initial-segment cuts along a chain decomposition, and the embedding S_j={i:x_i≤_P x_j} is checked directly, with no input quantity reused as the output. Lemma 3.2 encodes a large antichain A by equal-sized subsets S of a fresh coordinate block and verifies equivalence (1) by a case analysis on below/antichain/above elements. The exponent 2n/3 arises only from balancing the independent bounds 4^(n/3) (Lemma 3.1) and 2^(n-a+ell) (Lemma 3.2) at a=n/3; it is not fitted to any data or to the target theorem. Self-citations ([Bas25], [BEG+25], [BEGS21]) are contextual related work and carry no load-bearing assumption; no uniqueness theorem or ansatz is imported from the authors' own prior work. Separately, Lemma 3.2 as written defines b as counting x≤_P y for y∈A, which includes the antichain itself although the later proof treats 'below A' and 'in A' as disjoint; the map f is then not well-defined on the antichain elements and the count n-a-b is off. The construction is repairable by reading b via the strict inequality x<_P y, so this is a correctness/presentation issue, not a circularity, and it does not affect the non-circularity verdict.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No free parameters are fitted to data. The constants C and the threshold a = ceil(n/3) are chosen inside the proof to balance two constructions; they are not empirical fit parameters. All background results are standard and cited. No new entities are postulated.

assumptions (4)
  • standard math Dilworth's theorem: the size of a largest antichain equals the minimum size of a chain decomposition.
    Used in Lemma 3.1 to decompose any poset without an antichain of size a+1 into at most a chains, cited to Dilworth [Dil50].
  • standard math Hardy-Ramanujan asymptotic for the partition function p(n), implying p(n) = 2^(O(sqrt(n))).
    Used in the proof of Theorem 1.3 to absorb the partition count in Lemma 3.1's size bound, cited to Andrews [And98].
  • standard math Central binomial coefficient asymptotic: binom(2x,x) = Theta(2^(2x)/sqrt(x)).
    Used in Lemma 3.2 to estimate ell = (1+o(1)) log_2 a, controlling the size of the second construction; this is standard but not explicitly cited.
  • standard math The Boolean lattice 2^[n] is universal for all n-element posets.
    Proved in Proposition 2.2 and used as the base embedding in both Lemma 3.1 and Lemma 3.2.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Smaller universal posets." pith.science (2026). https://pith.science/paper/YRDK6MY7

@misc{pith2026250917820,
  author       = {Pith},
  title        = {Pith review of: Smaller universal posets},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YRDK6MY7}},
  note         = {Machine review of arXiv:2509.17820}
}
abstract

We show that there is a constant $C>0$ such that for each integer $n\geq 1$, there is a poset on at most $2^{2n/3+C\sqrt{n}}$ elements that contains each $n$-element poset as an (induced) subposet.

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

42 extracted references · 39 canonical work pages

  1. [1]

    Near-optimal induced universal graphs for bounded degree graphs

    Mikkel Abrahamsen, Stephen Alstrup, Jacob Holm, Mathias B k Tejs Knudsen, and Morten St \" o ckel. Near-optimal induced universal graphs for bounded degree graphs. In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland , volume 80 of LIPIcs , pages 128:1--128:14. Schloss Dagstuhl - Leibniz-Ze...

    work page 2017

  2. [2]

    Die widerspruchsfreiheit der allgemeinen mengenlehre

    Wilhelm Ackermann. Die widerspruchsfreiheit der allgemeinen mengenlehre. Mathematische Annalen , 114(1):305--315, 1937

    work page 1937

  3. [3]

    Near-optimum universal graphs for graphs with bounded degrees

    Noga Alon, Michael Capalbo, Yoshiharu Kohayakawa, Vojt e ch R \"o dl, Andrzej Ruci \'n ski, and Endre Szemer \'e di. Near-optimum universal graphs for graphs with bounded degrees. In International Workshop on Randomization and Approximation Techniques in Computer Science , pages 170--180. Springer, 2001

    work page 2001

  4. [4]

    Optimal induced universal graphs and adjacency labeling for trees

    Stephen Alstrup, S ren Dahlgaard, and Mathias B k Tejs Knudsen. Optimal induced universal graphs and adjacency labeling for trees. Journal of the ACM (JACM) , 64(4):1--22, 2017

    work page 2017

  5. [5]

    Adjacency labeling schemes and induced-universal graphs

    Stephen Alstrup, Haim Kaplan, Mikkel Thorup, and Uri Zwick. Adjacency labeling schemes and induced-universal graphs. In Proceedings of the forty-seventh annual ACM Symposium on Theory of Computing , pages 625--634, 2015

    work page 2015

  6. [6]

    The theory of partitions

    George E Andrews. The theory of partitions . Number 2. Cambridge university press, 1998

    work page 1998

  7. [7]

    Structures locales en combinatoire : reconstruction, saturation, dispersion et universalité

    Paul Bastide. Structures locales en combinatoire : reconstruction, saturation, dispersion et universalité . Thèse de doctorat en informatique, Université de Bordeaux, Bordeaux, France, June 2025. https://perso.eleves.ens-rennes.fr/people/paul.bastide/thesis.pdf

    work page 2025

  8. [8]

    Faithful universal graphs for minor-closed classes

    Paul Bastide, Louis Esperet, Carla Groenland, Claire Hilaire, Cl \'e ment Rambaud, and Alexandra Wesolek. Faithful universal graphs for minor-closed classes. arXiv preprint arXiv:2504.19582 , 2025

    work page Pith review arXiv 2025

Show all 42 references
  1. [9]

    Optimal labelling schemes for adjacency, comparability, and reachability

    Marthe Bonamy, Louis Esperet, Carla Groenland, and Alex Scott. Optimal labelling schemes for adjacency, comparability, and reachability. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing , STOC 2021, pages 1109--1117, New York, NY, USA, 2021. Associ...

    2021

  2. [10]

    Subgraph-universal planar graphs for trees

    Helena Bergold, Vesna Ir s i c , Robert Lauff, Joachim Orthaber, Manfred Scheucher, and Alexandra Wesolek. Subgraph-universal planar graphs for trees. arXiv preprint , 2024. arXiv:2409.01678 https://arxiv.org/abs/2409.01678

    2024 arXiv

  3. [11]

    Hypercube minor-universality

    Itai Benjamini, Or Kalifa, and Elad Tzalik. Hypercube minor-universality. arXiv:2501.13730 , 2025

    2025 arXiv

  4. [12]

    The random graph

    Peter J Cameron. The random graph. The Mathematics of Paul Erd \"o s II , pages 333--351, 1997

    1997

  5. [13]

    The random graph revisited

    Peter J Cameron. The random graph revisited. In European Congress of Mathematics: Barcelona, July 10--14, 2000, Volume I , pages 267--274. Springer, 2001

    2000

  6. [14]

    Fan R. K. Chung, Ronald L. Graham, and Don Coppersmith. On trees which contain all small trees. The Theory of Applications of Graphs , pages 265--272, 1981

    1981

  7. [15]

    Forbidden subgraphs and forbidden substructures

    Gregory Cherlin and Niandong Shi. Forbidden subgraphs and forbidden substructures. The Journal of Symbolic Logic , 66(3):1342--1352, 2001

    2001

  8. [16]

    Universal graphs with a forbidden subtree

    Gregory Cherlin and Saharon Shelah. Universal graphs with a forbidden subtree. Journal of Combinatorial Theory, Series B , 97(3):293--333, 2007. arXiv:0512218 https://arxiv.org/abs/math/0512218

    2007 arXiv

  9. [17]

    Universal graphs with a forbidden subgraph: block path solidity

    Gregory Cherlin and Saharon Shelah. Universal graphs with a forbidden subgraph: block path solidity. Combinatorica , 36(3):249--264, 2016. arXiv:1404.5757 https://arxiv.org/abs/1404.5757

    2016 arXiv

  10. [18]

    Universal graphs with forbidden subgraphs and algebraic closure

    Gregory Cherlin, Saharon Shelah, and Niandong Shi. Universal graphs with forbidden subgraphs and algebraic closure. Advances in Applied Mathematics , 22(4):454--491, 1999

    1999

  11. [19]

    Universal graphs with a forbidden near-path or 2-bouquet

    Gregory Cherlin and Lasse Tallgren. Universal graphs with a forbidden near-path or 2-bouquet. Journal of Graph Theory , 56(1):41--63, 2007

    2007

  12. [20]

    Efficient labeling for reachability in digraphs

    Maciej Dul e ba, Pawe Gawrychowski, and Wojciech Janczewski. Efficient labeling for reachability in digraphs. In Proceedings of the 31st International Symposium on Algorithms and Computation (ISAAC 2020) , 2020

    2020

  13. [21]

    On universal graphs with forbidden topological subgraphs

    Reinhard Diestel. On universal graphs with forbidden topological subgraphs. European Journal of Combinatorics , 6(2):175--182, 1985

    1985

  14. [22]

    Dilworth

    Robert P. Dilworth. A decomposition theorem for partially ordered sets. Annals of Mathematics , pages 161--166, 1950

    1950

  15. [23]

    Sparse universal graphs for planarity

    Louis Esperet, Gwena \"e l Joret, and Pat Morin. Sparse universal graphs for planarity. J. Lond. Math. Soc., II. Ser. , 108(4):1333--1357, 2023

    2023

  16. [24]

    Asymmetric graphs

    Paul Erd o s and Alfr \'e d R \'e nyi. Asymmetric graphs. Acta Math. Acad. Sci. Hungar , 14(295-315):3, 1963

    1963

  17. [25]

    Nonexistence of universal graphs without some trees

    Zoltan F \"u redi and P \'e ter Komj \'a th. Nonexistence of universal graphs without some trees. Combinatorica , 17:163--171, 1997

    1997

  18. [26]

    On the existence of countable universal graphs

    Zoltan F \"u redi and P \'e ter Komj \'a th. On the existence of countable universal graphs. Journal of Graph Theory , 25(1):53--58, 1997

    1997

  19. [27]

    An optimal ancestry scheme and small universal posets

    Pierre Fraigniaud and Amos Korman. An optimal ancestry scheme and small universal posets. In Proceedings of the forty-second ACM Symposium on Theory of Computing , pages 611--620, 2010

    2010

  20. [28]

    Theory of relations

    Roland Fra \" ss \'e . Theory of relations . North-Holland, 1953

    1953

  21. [29]

    M. K. Gol'dberg and É. M. Livshits. On minimal universal trees. Mathematical notes of the Academy of Sciences of the USSR , 4:713--717, 1968

    1968

  22. [30]

    What is the minimal size of a partial order that is universal for all partial orders of size n ? MathOverflow, 2010

    Joel David Hamkins. What is the minimal size of a partial order that is universal for all partial orders of size n ? MathOverflow, 2010. https://mathoverflow.net/q/25874

    2010

  23. [31]

    Tony Huynh, Bojan Mohar, Robert S \'a mal, Carsten Thomassen, and David R. Wood. Universality in minor-closed graph classes. arXiv preprint , 2021. arXiv:2109.00327 https://arxiv.org/abs/2109.00327

    2021 arXiv

  24. [32]

    Tight bounds for hypercube minor-universality

    Emma Hogan, Lukas Michel, Alex Scott, Youri Tamitegama, Jane Tan, and Dmitry Tsarev. Tight bounds for hypercube minor-universality. arXiv:2502.06629 , 2025

    2025 arXiv

  25. [33]

    Universal partial order represented by means of oriented trees and other simple graphs

    Jan Hubi c ka and Jaroslav Ne s et r il. Universal partial order represented by means of oriented trees and other simple graphs. European Journal of Combinatorics , 26(5):765--778, 2005

    2005

  26. [34]

    Johnston

    John B. Johnston. Universal infinite partially ordered sets. Proceedings of the American Mathematical Society , 7(3):507--514, 1956

    1956

  27. [35]

    Universal relational systems

    Bjarni J \'o nsson. Universal relational systems. Mathematica Scandinavica , pages 193--208, 1956

    1956

  28. [36]

    Some universal graphs

    P \'e ter Komj \'a th, Alan H Mekler, and J \'a nos Pach. Some universal graphs. Israel Journal of Mathematics , 64(2):158--168, 1988

    1988

  29. [37]

    Some remarks on universal graphs

    P \'e ter Komj \'a th. Some remarks on universal graphs. Discrete mathematics , 199(1-3):259--265, 1999

    1999

  30. [38]

    Universal graphs without large bipartite subgraphs

    P \'e ter Komj \'a th and J \'a nos Pach. Universal graphs without large bipartite subgraphs. Mathematika , 31(2):282--290, 1984

    1984

  31. [39]

    Kleitman and Bruce L

    Daniel J. Kleitman and Bruce L. Rothschild. The number of finite topologies. Proceedings of The American Mathematical Society , 25:276--276, 1970

    1970

  32. [40]

    Ian Munro and Patrick K

    J. Ian Munro and Patrick K. Nicholson. Succinct posets. Algorithmica , 76(2):445--473, 2016

    2016

  33. [41]

    J. W. Moon. On minimal n -universal graphs. Proceedings of the Glasgow Mathematical Association , 7(1):32--33, 1965

    1965

  34. [42]

    Universal graphs and universal functions

    Richard Rado. Universal graphs and universal functions. Acta Arithmetica , 9:331--340, 1964

    1964

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.