An Explicit Counterexample to Stanley's Rankwise Lower-Bound Conjecture for Differential Posets
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 $\lvert P^{(r)}_4\rvert=\lvert (Y^r)_4\rvert-\lfloor r/3\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$.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
AI-Assisted Discovery of Convex Relaxations via Dual Agents
Recent work shows that LLM agents can improve sharp-constant inequalities by searching for extremal constructions, which yield upper bounds. We address the complementary side: a lower bound holds for every admissible fun…
Complexity of Equivalence and Learning for Multiplicity Tree Automata
We consider the complexity of equivalence and learning for multiplicity tree automata, i.e., weighted tree automata over a field. We first show that the equivalence problem is logspace equivalent to polynomial identity t…
Quantitative Verification of Fairness in Tree Ensembles
This work focuses on quantitative verification of fairness in tree ensembles. Unlike traditional verification approaches that merely return a single counterexample when the fairness is violated, quantitative verification…
Are There Good Mistakes? A Theoretical Analysis of CEGIS
Counterexample-guided inductive synthesis CEGIS is used to synthesize programs from a candidate space of programs. The technique is guaranteed to terminate and synthesize the correct program if the space of candidate pro…
Counterexamples to the Low-Degree Conjecture
A conjecture of Hopkins (2018) posits that for certain high-dimensional hypothesis testing problems, no polynomial-time algorithm can outperform so-called "simple statistics", which are low-degree polynomials in the data…
Two-sample testing