On Rounding on the Hypersimplex

We study correlated rounding on the hypersimplex, the base polytope of the uniform matroid. For each point $x$ in the hypersimplex, the goal is to sample a $k$-subset $A(x)$ with marginals $x$, while coupling the samples for all choices of $x$ so that nearby inputs produce nearby sets. We give conditional constant-stretch results for the natural maximum-entropy sequential scheme, based on a conjectured spectral property of the covariance matrix of the maximum-entropy distribution over $k$-subsets; this conjecture has been extensively tested numerically. Under this property, the scheme samples the maximum-entropy $k$-subset distribution with prescribed marginals using a common random ordering and common uniform thresholds. For every $x,y\in [0,1{]}^n$ with ${\sum }_i{x}_i={\sum }_i{y}_i=k$, it satisfies $$\mathbb{E}\text{\hspace{0.17em}⁣}[\mathrm{\mid }A(x)\mathrm{△}A(y)\mathrm{\mid }]\le 6\mathrm{\parallel }x-y{\mathrm{\parallel }}_1\mathrm{.}$$ Thus, conditional on the spectral hypothesis, the previous $O(\log k)$ bound for hypersimplex correlated rounding would improve to a constant and the open question raised by Naor, Raju, Shetty, Srinivasan, Valieva, and Wajc would have a positive answer. By adding dummy coordinates, the same conditional result gives stretch at most $12$ for the at-most-$k$ polytope.