[latexpage]

Let $V$ denote the subset of the hypercube $\{-1,1\}^n$ consisting of strings $(x_1,\dots,x_n)$   that satisfy $\sum_{i=1}^k x_i \ge 0$ for  $k=1,\dots, n$.

Consider the  random transposition walk on   $V$. That is, at each step choose $i,j \in \{1,\dots,n\}$ uniformly at random ($i=j$ is allowed), and  if swapping $x_i$ and $x_j$  yields a  sequence in $V$, then perform this swap, otherwise do nothing.   What is the order of magnitude of  mixing time of this chain? A natural conjecture is that it is $\Theta(n \log n)$.  A lower bound of that order should not be hard to prove, although the best published bound we are aware of is of order  $n$, see [1], section 4. The best available upper bound, proved in [1], see also [2], is $O(n^2 \log n)$.  The proof is quite ingenious. 

REFERENCES

[1] Cohen, Emma, Prasad Tetali, and Damir Yeliussizov. "Lattice path matroids: negative correlation and fast mixing."   Link >>

[2] Cohen, Emma. "Problems in catalan mixing and matchings in regular hypergraphs." PhD diss., Georgia Institute of Technology, 2016.  Link >>