An Explicit Counterexample to Stanley's Rankwise Lower-Bound Conjecture for Differential Posets

• URL: http://arxiv.org/abs/2607.22988v2
• Date: Tue, 28 Jul 2026 09:17:14 GMT
• Title: An Explicit Counterexample to Stanley's Rankwise Lower-Bound Conjecture for Differential Posets
• Abstract summary: 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.<n>We disprove the resulting universal coefficientwise lower bound.<n>A reflection extension then yields an infinite differential poset.
• Score: 12.265438269252742
• License: http://creativecommons.org/licenses/by/4.0/
• 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 $\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$.

Related papers

• Thompson Sampling for Non-Monotone Convex Ridge Bandits: Monotonicity Is Not Needed for Polynomial Regret [6.657272312990604]
  We prove that Thompson sampling (TS) has Bayesian regret $tilde O(d5/2sqrt n)$ for bandit convex optimisation with convex emphmonotone ridge losses.
  arXiv  Detail & Related papers  (2026-09-10T01:58:03Z)
• SIC dimension towers via cyclotomic polynomials [0.0]
  We prove a structure for the dimension towers$d_k(D)_kgeq0$ which arise in the number-theoretic formulation of Zauner's SIC-POVM conjecture.
  arXiv  Detail & Related papers  (2026-09-03T19:51:19Z)
• Variable-Cliff Nielsen Geometry and an Exponent -4/3 Lower Bound for the Infinite-Cliff Diameter [0.0]
  We study the right-invariant one-step-cliff metric $d_Q$ on $operatornamePU(D)$.<n>For every fixed $0x/sqrt3$, [ _Dbigl(B_Q_D([I],xsqrtQ_D)bigr)le e-c_xD2.
  arXiv  Detail & Related papers  (2026-09-03T03:21:33Z)
• Exact Risk Ratios for Weighted Data Selection in Linear Regression [0.0]
  Hanneke, Moran, Shlimovich and Yehudayoff (COLT 2025) posed the following open problem.<n>A selector sees a finite dataset $D subseteq mathbbRd times mathbbR$, picks at most $n$ examples together with nonnegative weights, and hands the weighted least squares objective to the minimum-norm ERM.<n>We give explicit counterexamples showing that several shorter routes fail, and constructive sign-time selection algorithms for all proved cases.
  arXiv  Detail & Related papers  (2026-08-28T07:19:17Z)
• The Condition-Number Barrier in Sparse Least Squares [77.64108812086542]
  In [AS21], Axiotis and Sviridenko conjectured that the linear dependence on the restricted condition number in convex optimization cannot be improved by a sparse-time algorithm.<n>We establish their conjectured lower bound for least-squares objectives, conditional on the randomized exact-volume Small-Set Expansion Hypothesis.
  arXiv  Detail & Related papers  (2026-08-03T17:57:01Z)
• Costs of Arbitrary Real Matrix Factorizations for Pure-DP Continual Counting [0.9023847175654603]
  We prove $c_mathrmF(T_n),c_2(T_n)=(log(n+1)3/2)$ with no sign, sparsity, or squareness restriction.<n>Within the pure-$varepsilon$-DP matrix-mechanism class, the optimized maximum and mean squared errors are both $(varepsilon-2log3(n+1))$.
  arXiv  Detail & Related papers  (2026-07-30T14:41:34Z)
• Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence [54.59847568544922]
  We study horizon-free regret for finite-horizon time-homogeneous Markov decision processes with $A$ states, $A$ actions, horizon $H$, and per-trajectory total reward bounded by $1$.<n>We prove a regret upper bound [tilde O(sqrtSAK+S8A3)] with failure probability $$, where $K$ is the number of episodes and $tilde O(sqrtSAK+S3K)$ hides $mathsfpoly
  arXiv  Detail & Related papers  (2026-07-22T07:42:19Z)
• The Price of Hidden Curvature: An $\widetildeΩ (d^{5/4} \sqrt{T})$ Lower Bound for Bandit Convex Optimization [4.774251262663345]
  We show that a $widetilde(d5/4sqrt T)$ lower bound on the minimax expected regret of bandit convex optimization of $1$-Lipschitz functions grows faster than $dsqrtT$.<n>This presents the first nontrivial regret lower bound that grows faster than $dsqrtT$ for this problem.
  arXiv  Detail & Related papers  (2026-07-21T02:44:33Z)
• Rényi exponent landscape of multipartite entanglement in free-fermion systems [51.56484100374058]
  We show that the Rényi tripartite information $I_3() exhibits a qualitatively $exclusion-dependent scaling at small Fermi momentum.<n>A direct consequence is a replica obstruction: $I_m(n)/I_m(1) sim zm-1 to 0$ for all integer $n geq 2$, so the leading von Neumann signal cannot be reconstructed from integer Rényi data.
  arXiv  Detail & Related papers  (2026-03-09T22:27:00Z)
• Approximating the operator norm of local Hamiltonians via few quantum states [53.16156504455106]
  Consider a Hermitian operator $A$ acting on a complex Hilbert space of $2n$.<n>We show that when $A$ has small degree in the Pauli expansion, or in other words, $A$ is a local $n$-qubit Hamiltonian.<n>We show that whenever $A$ is $d$-local, textiti.e., $deg(A)le d$, we have the following discretization-type inequality.
  arXiv  Detail & Related papers  (2025-09-15T14:26:11Z)
• Efficient Continual Finite-Sum Minimization [52.5238287567572]
  We propose a key twist into the finite-sum minimization, dubbed as continual finite-sum minimization. Our approach significantly improves upon the $mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$ requires. We also prove that there is no natural first-order method with $mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$, establishing that the first-order complexity of our method is nearly tight.
  arXiv  Detail & Related papers  (2024-06-07T08:26:31Z)
• Nearly Minimax Optimal Submodular Maximization with Bandit Feedback [12.28389976959093]
  We minimize the learner's regret with respect to an approximation of the maximum $f(S_*)$ with $|S_*| = k$.<n>In this work, we establish the first minimax lower bound for this setting that scales like $tildeOmega(min_L le k(T2/3 + sqrtn choose k - LT)$.<n>For a slightly restricted algorithm class, we prove a stronger regret lower bound of $tildeOmega(min_L
  arXiv  Detail & Related papers  (2023-10-27T20:19:03Z)
• Improved Global Guarantees for the Nonconvex Burer--Monteiro Factorization via Rank Overparameterization [10.787390511207683]
  We consider a twice-differentiable, $L$-smooth, $mu$-strongly convex objective $phimph over an $ntimes n$fracfrac14(L/mu-1)2rstar$. Despite non-locality, local optimization is guaranteed to globally converge from any initial point to the global optimum.
  arXiv  Detail & Related papers  (2022-07-05T03:18:17Z)
• Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
  We study iterative methods based on Krylov subspaces for low-rank approximation under any Schatten-$p$ norm. Our main result is an algorithm that uses only $tildeO(k/sqrtepsilon)$ matrix-vector products.
  arXiv  Detail & Related papers  (2022-02-10T16:10:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.