Fetching the paper…

Reading the bibliography…

Lattice Path Matroids: Negative Correlation and Fast Mixing · Around

2015

Lattice Path Matroids: Negative Correlation and Fast Mixing

Cohen, Emma, Tetali, Prasad, Yeliussizov, Damir

Original
PDF
Post on X

Understand

Catalan numbers arise in many enumerative contexts as the counting sequence of combinatorial structures.

In this work, we consider natural Markov chains on some of the realizations of the Catalan sequence.
While our main result is in deriving an $O(n^2 \log n)$ bound on the mixing time in $L_2$ (and hence total variation) distance for the random transposition chain on Dyck paths, we raise several open questions, including the optimality of the above bound.
The novelty in our proof is in establishing a certain negative correlation property among random bases of lattice path matroids, including the so-called Catalan matroid which can be defined using Dyck paths.

Built on

Time to reach stationarity in the Bernoulli–Laplace diffusion model
P. Diaconis and M. Shahshahani · 1987
Earlier work this paper cites.
Balanced matroids
T. Feder and M. Mihail · 1992
Earlier work this paper cites.
Triangulating the circle, at random
D. Aldous · 1994
Earlier work this paper cites.
Logarithmic Sobolev inequalities for finite Markov chains
P. Diaconis and L. Saloff-Coste · 1996
Earlier work this paper cites.
On the mixing rate of the triangulation walk
M. S. Molloy, B. Reed, and W. Steiger · 1998
Earlier work this paper cites.
On the mixing time of the triangulation walk and other Catalan structures
L. McShine and P. Tetali · 1999
Earlier work this paper cites.

Similar

Rapid mixing of some linear matroids and other combinatorial objects
M. Sohoni · 1999
Cited alongside, same era.
Spectral gap and log-Sobolev constant for balanced matroids
M. Jerrum and J.-B. Son · 2002
Cited alongside, same era.
The Narayana distribution
R. A. Sulanke · 2002
Cited alongside, same era.
The Catalan matroid
F. Ardila · 2003
Cited alongside, same era.
Elementary bounds on Poincaré and log-Sobolev constants for decomposable Markov chains
M. Jerrum, J.-B. Son, P. Tetali, and E. Vigoda · 2004
Cited alongside, same era.

Then

Mixing times of lozenge tiling and card shuffling Markov chains
Original
D. B. Wilson · 2004
Later among the works it cites.
Univariate discrete distributions
N. L. Johnson, A. W. Kemp, and S. Kotz · 2005
Later among the works it cites.
Lattice path matroids: structural properties
J. E. Bonin and A. de Mier · 2006
Later among the works it cites.
Rayleigh matroids
Y. Choe and D. G. Wagner · 2006
Later among the works it cites.
Random transpositions on cyclic permutations of lattice paths
P. Caputo, R. Restrepo, and P. Tetali · 2010
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…