{"id":"6454615b-57c3-4c82-b6c4-c964cecc9136","arxiv_id":"2509.17820","paper_version":3,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Every n-element poset embeds into a poset of size at most 2^(2n/3 + C*sqrt(n)), improving the folklore 2^n upper bound for universal posets.","lead":"A new construction embeds every n-element poset into a universal poset of size only about 2^(2n/3), far smaller than the standard 2^n Boolean lattice. This is the first improvement on a long-standing question about the minimum size of a universal poset, originally asked by Hamkins.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 3.2's count b of 'below' elements includes A but is later treated as excluding it; the construction is repairable by defining b via strict inequality, so the fix should be verified.","rationale":"The reader's weakest assumption (the equal-size subset encoding in Lemma 3.2) is not, in my view, where the argument is fragile: the equal-size choice is proven and used exactly once to guarantee incomparability of antichain images, and that part of the proof is sound. The actual weak point is the inconsistent count of the 'below' set in the same lemma: b is defined to include A, but the construction and the counting of z_j's require b to exclude A. I traced the intended fix (defining b as the number of elements strictly below some antichain element) through the three cases of equivalence (1), and the proof goes through. So the central claim appears correct, but the manuscript should be revised to make this definition consistent before final acceptance.","tokens_in":9656,"tokens_out":19801,"duration_ms":175863,"concrete_test":"Re-derive Lemma 3.2 with b:=|\\(x∈P : x<_P y for some y∈A\\)| and re-verify (1): check |[n-a+ℓ]|=b+ℓ+(n-a-b), that f is injective on P, and that the three cases (u=x_i, u=y_S, u=z_j) remain valid, especially the argument that y_S≤x_i is impossible because x_i≤y_{S'} for some S'. If any case fails under this definition, the second construction is unsound.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"In Lemma 3.2, b is defined as the number of elements x with x≤_P y for some y∈A. Since A is an antichain, every y∈A satisfies y≤_P y, so A⊆{x_1,...,x_b}. Yet the construction then assigns the antichain elements the names y_S and numbers 'the remaining n-a-b elements' as z_j; if b includes A this count is wrong (there are only n-b remaining elements), and antichain elements would receive two images f(x_i) and f(y_S). The subsequent proof only works if b is interpreted as the number of elements strictly below A (x<_P y for some y∈A). With that reading the counts are b+ℓ+(n-a-b)=n-a+ℓ and all three cases of equivalence (1) check out; the 'y_S≤x_i is impossible' argument also uses the strict-below reading. Thus the theorem is not threatened, but the lemma as written needs correction.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":9917,"tokens_out":8880,"duration_ms":78933,"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":[{"comment":"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.","section":"Lemma 3.2, proof"},{"comment":"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.","section":"Lemma 3.1, proof"}],"minor_comments":[{"comment":"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.","section":"Lemma 3.2, Case 2"},{"comment":"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]}.","section":"Theorem 1.3, proof"},{"comment":"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.","section":"Lemma 3.1, proof"}],"recommendation":"major_revision","confidential_remarks":"The main result is sound in strategy and the two problematic points in Lemmas 3.1 and 3.2 are localized and easily repairable. I would be comfortable accepting the paper once the definition of b in Lemma 3.2 is corrected to the strict-below reading and the convexity justification in Lemma 3.1 is replaced by the AM-GM argument."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this is a genuine first improvement on a folklore upper bound, and the main theorem is sound. It deserves a serious referee and should be accepted after minor fixes.\n\nWhat's new: the prior best upper bound for the minimum universal poset was the Boolean lattice of size 2^n; the paper breaks that with 2^{2n/3 + O(sqrt n)}. The strategy splits posets into small-antichain and large-antichain cases. Lemma 3.1 uses Dilworth to encode a chain decomposition into down-sets; Lemma 3.2 handles large antichains by coding them as equal-size subsets of a separate coordinate block. The two bounds are balanced at a = ceil(n/3). The comparability graph corollary is immediate and correctly stated.\n\nThe proof is mostly careful, and there are no circular dependencies. The self-citations are to relevant earlier work, not padding.\n\nSoft spots, both minor and repairable:\n\n1. Lemma 3.1 calls the function product(z_i+1) convex; it is not. The intended bound is still true by AM-GM, so this is a justification slip, not a mathematical break.\n\n2. More substantive: Lemma 3.2 defines b as the number of elements x with x <=_P y for some y in A. Read literally, since elements of A satisfy y <=_P y, the set counted includes A. Then the number of 'remaining' elements is n-b, not n-a-b, and antichain elements would receive two images. The proof only makes sense if b counts elements strictly below A. With that strict reading, all counts and the three equivalence cases work, and the 'y_S <= x_i is impossible' step also checks out. So the theorem stands, but the lemma's definitions should be corrected, not just tightened.\n\nI double-checked the size estimate in Theorem 1.3 and the embedding equivalence in Lemma 3.2 under the strict-below reading; both are correct. The lower bound discussion is standard. The paper honestly reports the gap to the conjectured 2^{n/4}.\n\nWho this is for: anyone working on universal posets, induced-universal graphs, or poset labelling schemes. The technique is clean enough to be useful beyond this specific problem.\n\nRecommendation: send to peer review; expect acceptance after fixing the two small issues.","headline":"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.","tokens_in":10382,"tokens_out":6288,"would_cite":true,"duration_ms":52946,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["06A07","05D05"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["universal posets","Boolean lattice","induced subposets","comparability graphs","antichain","chain decomposition","Dilworth's theorem","partition function"],"falsifier":"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.","tokens_in":9413,"feed_emoji":"🧩","tokens_out":10275,"duration_ms":80939,"temperature":0.7,"pith_summary":"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.","feed_headline":"Universal posets shrink to 2^{2n/3} elements","feed_subtitle":"A slice of the Boolean lattice with 2^{2n/3+O(√n)} elements contains every n-element poset, improving the 2^n bound.","key_machinery":"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)}$.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"supplies Dilworth's theorem, which gives the chain decomposition used to encode posets without a large antichain in Lemma 3.1.","marker":"[Dil50]"},{"why":"supplies the asymptotic for the partition function used to bound the number of chain-length sequences by $p(n)=2^{O(\\sqrt n)}$.","marker":"[And98]"},{"why":"supplies the asymptotic count of $n$-element posets used to state the $2^{n/4+o(n)}$ lower bound against which the new upper bound improves.","marker":"[KR70]"}],"fun_headline_variants":["Universal posets: exponent drops to 2n/3","Every n-poset fits in 2^{2n/3} elements","Smaller universal posets: 2^{2n/3} bound","All n-posets embed in a 2^{2n/3}-element poset"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Universal posets: exponent drops to 2n/3","Every n-poset fits in 2^{2n/3} elements","Smaller universal posets: 2^{2n/3} bound","All n-posets embed in a 2^{2n/3}-element poset"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001225,"raw_usage":{"total_tokens":4965,"prompt_tokens":802,"completion_tokens":4163,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":418,"completion_tokens_details":{"reasoning_tokens":4078}},"tokens_in":418,"tokens_out":4163,"duration_ms":23783,"temperature":1.0,"reasoning_tokens":4078,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T15:48:07.592893+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":2}