Paper deep dive
An Explicit Counterexample to Stanley's Rankwise Lower-Bound Conjecture for Differential Posets
Xinan Dai, Yuchen Yang, Wenhao Deng, Yingdong Shi, Tailin Wu
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:In Problem~6 of his 1988 paper on differential posets, Stanley asked for the least possible cardinality of a fixed rank of an $r$-differential poset and suggested that the minimum should be attained by $Y^r$, the $r$-fold Cartesian power of Young's lattice. We disprove the resulting universal coefficientwise lower bound. For every $r\geq 3$, we construct an infinite $r$-differential poset $P^{(r)}$ satisfying \[ \card{P^{(r)}_4} =\card{(Y^r)_4}-\left\lfloor\frac r3\right\rfloor. \] For $r=3$, the construction replaces thirteen rank-four lower-cover blocks of $Y^3$ by twelve blocks with the same point and pair incidence multiplicities, producing the initial rank sequence $1,3,9,22,50$ instead of $1,3,9,22,51$. A reflection extension then yields an infinite differential poset. The construction does not address the cases $r=1$ and $r=2$.
Tags
Links
- Source: https://arxiv.org/abs/2607.22988v1
- Canonical: https://arxiv.org/abs/2607.22988v1
Trouble viewing inline? Open PDF directly →
Full Text
16,035 characters extracted from source content.
Expand or collapse full text
An Explicit Counterexample to Stanley’s Rankwise Lower-Bound Conjecture for Differential Posets Xinan Dai Key Laboratory of Information Science of Electromagnetic Waves, Innovation School of Future Information and Technology, Fudan University, Shanghai, China Department of Artificial Intelligence, School of Engineering, Westlake University, Hangzhou, China xndai23@m.fudan.edu.cn , Yuchen Yang Department of Artificial Intelligence, School of Engineering, Westlake University, Hangzhou, China yangyuchen@westlake.edu.cn , Wenhao Deng Department of Artificial Intelligence, School of Engineering, Westlake University, Hangzhou, China dengwenhao@westlake.edu.cn , Yingdong Shi School of Information Science and Technology, ShanghaiTech University, Shanghai, China shiyd2023@shanghaitech.edu.cn and Tailin Wu Department of Artificial Intelligence, School of Engineering, Westlake University, Hangzhou, China wutailin@westlake.edu.cn (Date: 24 July 2026) Abstract. In Problem 6 of his 1988 paper on differential posets, Stanley asked for the least possible cardinality of a fixed rank of an r-differential poset and suggested that the minimum should be attained by YrY^r, the r-fold Cartesian power of Young’s lattice. We disprove the resulting universal coefficientwise lower bound. For every r≥3r≥ 3, we construct an infinite r-differential poset P(r)P^(r) satisfying |P4(r)|=|(Yr)4|−⌊r3⌋. P^(r)_4 = (Y^r)_4 - r3 . For r=3r=3, the construction replaces thirteen rank-four lower-cover blocks of Y3Y^3 by twelve blocks with the same point and pair incidence multiplicities, producing the initial rank sequence 1,3,9,22,501,3,9,22,50 instead of 1,3,9,22,511,3,9,22,51. A reflection extension then yields an infinite differential poset. The construction does not address the cases r=1r=1 and r=2r=2. Key words and phrases: Differential poset, Young’s lattice, rank function, extremal poset, incidence trade 2020 Mathematics Subject Classification: Primary 06A07; Secondary 05B30 Author note: Xinan Dai received his B.S. degree in Mathematics and Applied Mathematics from Shanghai University. He is currently enrolled as a Ph.D. student at Fudan University and is a visiting student at the AI for Scientific Simulation and Discovery Lab, Westlake University. Introduction Stanley introduced differential posets as an axiomatic framework retaining many local and enumerative features of Young’s lattice [5]. In Problem 6 of his original paper, he asked for the greatest and least possible number of elements of rank n in an r-differential poset and suggested that YrY^r should be the rank-minimizing example. Byrnes subsequently settled the maximum side of the problem [1]. Stanley and Zanello later restated the proposed lower bound explicitly [6, Question 17]: must every r-differential poset P satisfy (1) |Pn|≥|(Yr)n|(n≥0)? P_n ≥ (Y^r)_n (n≥ 0)? We show that the universally quantified assertion in (1) is false. The basic counterexample occurs at r=3r=3 and rank four. Its finite mechanism is an unequal replacement of lower-cover blocks: thirteen blocks in Y3Y^3 are replaced by twelve new blocks while preserving every one-point and two-point incidence multiplicity. These multiplicities are precisely the entries of the operator D4U3D_4U_3. Consequently, the differential-poset relation remains valid through rank three, although the fourth rank has one fewer element. Stanley’s reflection construction then extends the finite initial segment to an infinite differential poset. Section 1 recalls the relevant definitions and states the main result. Section 2 gives the rank-four replacement for r=3r=3 and verifies it directly. Section 3 gives the infinite extension, and Section 4 transports the construction to every r≥3r≥ 3. 1. Differential posets and the main result Young’s lattice Y is the graded poset of integer partitions ordered by inclusion of Ferrers diagrams. Its rank-n elements are the partitions of n, and a cover relation adds one cell. Write p(n)=|Yn|p(n)= Y_n for the number of integer partitions of n. Hence FY(q)=∑n≥0|Yn|qn=∏i≥1(1−qi)−1.F_Y(q)= _n≥ 0 Y_n q^n= _i≥ 1(1-q^i)^-1. The Cartesian product of r copies is denoted by YrY^r. An element of (Yr)n(Y^r)_n is an r-tuple of partitions whose total size is n, and FYr(q)=FY(q)r.F_Y^r(q)=F_Y(q)^r. Definition 1.1. Let r be a positive integer. An r-differential poset is a locally finite graded poset P=⨆n≥0PnP= _n≥ 0P_n with a unique least element and the following properties. (D1) If x≠yx≠ y have the same rank, then the number of their common upper covers equals the number of their common lower covers. (D2) If x has d lower covers, then it has d+rd+r upper covers. Let ℚPnQP_n be the vector space with basis PnP_n. Define the up and down operators by Unx=∑z∈Pn+1z⋗xz,Dnx=∑w∈Pn−1x⋗w.U_nx= _ subarraycz∈ P_n+1\\ z x subarrayz, D_nx= _ subarraycw∈ P_n-1\\ x w subarrayw. The two axioms are equivalent to (2) Dn+1Un−Un−1Dn=rIℚPn(n≥0),D_n+1U_n-U_n-1D_n=rI_QP_n (n≥ 0), with the evident convention in rank zero. Young’s lattice is 11-differential, and Cartesian products add the parameters; hence YrY^r is r-differential. Theorem 1.2. For every integer r≥3r≥ 3, there exists an infinite r-differential poset P(r)P^(r) such that |Pi(r)|=|(Yr)i|(0≤i≤3),|P4(r)|=|(Yr)4|−⌊r3⌋. P^(r)_i = (Y^r)_i (0≤ i≤ 3), P^(r)_4 = (Y^r)_4 - r3 . Moreover, (3) |(Yr)4|=r(r+1)(r2+17r+42)24. (Y^r)_4 = r(r+1)(r^2+17r+42)24. In particular, the first five rank sizes of P(3)P^(3) are (1,3,9,22,50),(1,3,9,22,50), whereas those of Y3Y^3 are (1,3,9,22,51)(1,3,9,22,51). The rank-growth results of Miller [4] and Gaetz–Venkataramana [2] do not imply the coefficientwise comparison in (1) and are consistent with Theorem 1.2. 2. The finite r=3r=3 construction 2.1. Lower-cover blocks Retain ranks zero through three of Y3Y^3. For a proposed rank-four element z, set Bz=x∈(Y3)3:x⋖z.B_z=\x∈(Y^3)_3:x z\. We call BzB_z the lower-cover block of z. Lemma 2.1 (Point-and-pair criterion). Fix the poset through rank three. Let (Bz)z∈Q(B_z)_z∈ Q be a finite indexed family of nonempty subsets of P3P_3, one for each proposed rank-four element z∈Qz∈ Q. For x,y∈P3x,y∈ P_3, the (x,y)(x,y)-entry of D4U3D_4U_3 is |z∈Q:x∈Bz|,x=y,|z∈Q:x,y⊆Bz|,x≠y. cases \z∈ Q:x∈ B_z\ ,&x=y,\\[5.69054pt] \z∈ Q:\x,y\ B_z\ ,&x≠ y. cases Consequently, replacing rank-four blocks by blocks having the same incidence multiplicity on every one- and two-element subset of P3P_3 leaves D4U3D_4U_3 unchanged. Proof. For x=yx=y, the coefficient of x in D4U3xD_4U_3x is the number of rank-four elements covering x. For x≠yx≠ y, the coefficient of y is the number of rank-four elements covering both x and y. ∎ Because the ranks below four are unchanged, U2D3U_2D_3 is unchanged as well. It therefore suffices to preserve the point and pair incidence multiplicities of the rank-four lower-cover blocks. 2.2. Indexing rank three Write a triple of partitions as (λ;μ;ν)(λ;μ;ν), write 0 for the empty partition, and concatenate the parts of a partition; for example, 2121 denotes (2,1)(2,1). We label the elements of (Y3)3(Y^3)_3 as follows. Index Element Index Element 0 (3;0;0)(3;0;0) 11 (1;0;11)(1;0;11) 1 (21;0;0)(21;0;0) 12 (0;3;0)(0;3;0) 2 (111;0;0)(111;0;0) 13 (0;21;0)(0;21;0) 3 (2;1;0)(2;1;0) 14 (0;111;0)(0;111;0) 4 (2;0;1)(2;0;1) 15 (0;2;1)(0;2;1) 5 (11;1;0)(11;1;0) 16 (0;11;1)(0;11;1) 6 (11;0;1)(11;0;1) 17 (0;1;2)(0;1;2) 7 (1;2;0)(1;2;0) 18 (0;1;11)(0;1;11) 8 (1;11;0)(1;11;0) 19 (0;0;3)(0;0;3) 9 (1;1;1)(1;1;1) 20 (0;0;21)(0;0;21) 10 (1;0;2)(1;0;2) 21 (0;0;111)(0;0;111) 2.3. The thirteen-for-twelve replacement Begin with the 5151 lower-cover blocks supplied by rank four of Y3Y^3. Delete (4) ℛ= =\ 1,13,20,5,7,5,8,6,10,6,11, \1\,\3\,\0\,\5,7\,\5,8\,\6,0\,\6,1\, 1,3,5,1,4,6,3,4,9,5,6,9,7,8,13,10,11,20. \1,3,5\,\1,4,6\,\3,4,9\,\5,6,9\,\7,8,3\,\0,1,0\\. In the displayed order, these are the lower-cover blocks of (5) (22;0;0),(0;22;0),(0;0;22),(11;2;0),(11;11;0),(11;0;2),(11;0;11), (2;0;0),\ (0;2;0),\ (0;0;2),\ (1;2;0),\ (1;1;0),\ (1;0;2),\ (1;0;1), (21;1;0),(21;0;1),(2;1;1),(11;1;1),(1;21;0),(1;0;21). (1;1;0),\ (1;0;1),\ (2;1;1),\ (1;1;1),\ (1;1;0),\ (1;0;1). The list in (5) is checked directly by deleting one removable corner cell from one of the three partition coordinates. Insert twelve new rank-four elements with lower-cover blocks (6) = =\ 1,5,1,6,5,6,7,13,8,13,10,20,11,20, \1,5\,\1,6\,\5,6\,\7,3\,\8,3\,\0,0\,\1,0\, 1,3,4,3,5,9,4,6,9,5,7,8,6,10,11. \1,3,4\,\3,5,9\,\4,6,9\,\5,7,8\,\6,0,1\\. Every block in (6) is nonempty and therefore defines a rank-four element once the indicated cover relations are declared. 2.4. Verification Only the twelve vertices 1,3,4,5,6,7,8,9,10,11,13,201,3,4,5,6,7,8,9,10,11,13,20 occur in ℛ∪R . Their incidence multiplicities agree: (7) v1345678910111320degℛ(v)=deg(v)322442222222. array[]c|rv&1&3&4&5&6&7&8&9&10&11&13&20\\ _R(v)= _A(v)&3&2&2&4&4&2&2&2&2&2&2&2. array Both sides contain each of the following twenty-two pairs exactly once: (8) 1,3,1,4,1,5,1,6,3,4,3,5,3,9,4,6,4,9,5,6, \1,3\,\1,4\,\1,5\,\1,6\,\3,4\,\3,5\,\3,9\,\4,6\,\4,9\,\5,6\, 5,7,5,8,5,9,6,9,6,10,6,11,7,8,7,13,8,13, \5,7\,\5,8\,\5,9\,\6,9\,\6,0\,\6,1\,\7,8\,\7,3\,\8,3\, 10,11,10,20,11,20, \0,1\,\0,0\,\1,0\, and neither side contains any other pair. Equations (7) and (8) are therefore a complete incidence check. Let P≤4(3)P^(3)_≤ 4 be obtained by leaving (Y3)≤3(Y^3)_≤ 3 unchanged and replacing ℛR by A in rank four. By Lemma 2.1, its D4U3D_4U_3 matrix is the same as that of Y3Y^3, while U2D3U_2D_3 is unchanged. Hence D4U3−U2D3=3ID_4U_3-U_2D_3=3I on rank three. The lower-rank identities are inherited from Y3Y^3, so P≤4(3)P^(3)_≤ 4 is a partial 33-differential poset and |P4(3)|=51−13+12=50. P^(3)_4 =51-13+12=50. Remark 2.2. The replacement has a design-theoretic interpretation. Define a signed function on subsets of the twelve affected vertices by f(B)=+1,B∈ℛ,−1,B∈,0,otherwise.f(B)= cases+1,&B ,\\ -1,&B ,\\ 0,&otherwise. cases Then ∑B⊇Sf(B)=0(1≤|S|≤2), _B Sf(B)=0 (1≤ S ≤ 2), whereas ∑Bf(B)=1 _Bf(B)=1. After adjoining the empty block to the A-side, the two collections form a simple [2][2]-trade of volume 1313 in the sense of [3]. The differential-poset axioms detect the first two incidence moments but not the zeroth, which accounts for the one-element saving. 3. Extension to an infinite poset The construction above is finite. The following reflection extension, appearing in [5, Proposition 6.1], preserves its initial ranks. Proposition 3.1 (Reflection extension). Suppose P≤nP_≤ n is a finite partial r-differential poset of rank n, meaning that (2) holds in ranks below n. Then P≤nP_≤ n extends by one rank to a partial r-differential poset of rank n+1n+1. Iteration produces an infinite r-differential poset whose first n+1n+1 ranks, including their cover relations, are exactly P≤nP_≤ n. Proof. For each y∈Pn−1y∈ P_n-1, add an element y∗y^* of rank n+1n+1 that covers precisely the elements x∈Pnx∈ P_n covering y. For each x∈Pnx∈ P_n, also add r rank-(n+1)(n+1) elements, each covering only x. If x∈Pnx∈ P_n has d lower covers, then the elements y∗y^* provide d upper covers and the singleton elements provide r more. Thus x has d+rd+r upper covers. If x≠x′x≠ x lie in PnP_n, their common new upper covers are precisely the elements y∗y^* indexed by their common lower covers. The differential conditions therefore hold at rank n, and all lower-rank relations are unchanged. Iterating and taking the union gives the required infinite poset. ∎ Applying Proposition 3.1 to P≤4(3)P^(3)_≤ 4 gives an infinite 33-differential poset with initial rank sequence 1,3,9,22,50.1,3,9,22,50. 4. The construction for every r≥3r≥ 3 Fix r≥3r≥ 3 and put k=⌊r/3⌋k= r/3 . Partition the first 3k3k coordinates of YrY^r into disjoint triples Tj=3j+1,3j+2,3j+3,0≤j<k.T_j=\3j+1,3j+2,3j+3\, 0≤ j<k. For each TjT_j, the elements supported on the coordinates in TjT_j form an embedded copy of Y3Y^3. Perform the replacement ℛ↝R inside ranks three and four of each copy. The affected rank-three vertices belonging to different triples are disjoint. Each replacement preserves all point and pair incidences among its affected vertices. Incidences involving an unaffected vertex are unchanged, and no replacement block mixes two coordinate triples. Thus the identity D4U3−U2D3=rID_4U_3-U_2D_3=rI remains valid. Each of the k replacements removes one rank-four element, and Proposition 3.1 extends the resulting partial poset to an infinite r-differential poset. It remains to compute the fourth rank of YrY^r. Distributing four cells among the r coordinates gives the size patterns 4,3+1,2+2,2+1+1,1+1+1+1.4, 3+1, 2+2, 2+1+1, 1+1+1+1. Using p(1)=1p(1)=1, p(2)=2p(2)=2, p(3)=3p(3)=3, and p(4)=5p(4)=5, their contributions are 5r,3r(r−1),4(r2),2r(r−12),(r4).5r, 3r(r-1), 4 r2, 2r r-12, r4. Therefore |(Yr)4| (Y^r)_4 =5r+3r(r−1)+4(r2)+2r(r−12)+(r4) =5r+3r(r-1)+4 r2+2r r-12+ r4 =r(r+1)(r2+17r+42)24. = r(r+1)(r^2+17r+42)24. For r=3r=3, this is 5151, while the construction gives 5050. This proves Theorem 1.2 and disproves (1) in its universally quantified form. The construction gives mr(4)≤r(r+1)(r2+17r+42)24−⌊r3⌋(r≥3),m_r(4)≤ r(r+1)(r^2+17r+42)24- r3 (r≥ 3), where mr(n)m_r(n) denotes the minimum possible size of rank n among infinite r-differential posets. It neither determines mr(4)m_r(4) exactly nor addresses r=1r=1 or r=2r=2. Statement on AI-assisted discovery and human verification The counterexample presented in this paper was initially generated by the TARS agent system through an autonomous mathematical search and was subsequently examined and independently verified by the human authors. References [1] P. Byrnes, Structural Aspects of Differential Posets, Ph.D. thesis, University of Minnesota, 2012. [2] C. Gaetz and P. Venkataramana, Path counting and rank gaps in differential posets, Order 37 (2020), no. 2, 279–286, arXiv:1806.03509. [3] E. Ghorbani, S. Kamali, G. B. Khosrovshahi, and D. S. Krotov, On the volumes and affine types of trades, Electron. J. Combin. 27 (2020), no. 1, Paper No. P1.29, arXiv:1810.02296. [4] A. R. Miller, Differential posets have strict rank growth: a conjecture of Stanley, Order 30 (2013), no. 2, 657–662, arXiv:1202.3006. [5] R. P. Stanley, Differential posets, J. Amer. Math. Soc. 1 (1988), no. 4, 919–961. [6] R. P. Stanley and F. Zanello, On the rank function of a differential poset, Electron. J. Combin. 19 (2012), no. 2, Paper No. P13.