Advanced search
Publication Cover
Experimental Mathematics Volume 26, 2017 - Issue 1
Submit an article Journal homepage
118
Views
4
CrossRef citations to date
0
Altmetric
Original Articles

Spectral Gap for Random-to-Random Shuffling on Linear Extensions

Arvind AyyerDepartment of Mathematics, Indian Institute of Science, Bangalore, India
,
Anne SchillingDepartment of Mathematics, UC Davis, Davis, CA, USACorrespondence[email protected]
&
Nicolas M. ThiéryLaboratoire de Recherche en Informatique, Univ Paris-Sud, CNRS, Orsay, France
Pages 22-30 | Published online: 05 Jul 2016

References

  • [Ayyer et al. 14] Arvind Ayyer, Steven Klee, and Anne Schilling. “Combinatorial Markov Chains on Linear Extensions.” J. Algebraic Combin. 39:4 (2014), 853–881.
  • [Bubley and Dyer 99] Russ Bubley and Martin Dyer. “Fast+er Random Generation of Linear Extensions.” Discrete Math. 201:1–3 (1999), 81–88.
  • [Caputo et al. 10] Pietro Caputo, Thomas M. Liggett, and Thomas Richthammer. “Proof of Aldous’ Spectral Gap Conjecture.” J. Am. Math. Soc. 23:3 (2010), 831–851.
  • [Dancis and Davis 87] Jerome Dancis and Chandler Davis. “An Interlacing Theorem for Eigenvalues of Selfadjoint Operators.” Linear Algebra Appl. 88/89 (1987), 117–122.
  • [Diaconis 03] Persi Diaconis. “Mathematical Developments from the Analysis of Riffle Shuffling.” In Groups, Combinatorics & Geometry (Durham, 2001), edited by A. A. Ivanov et al., pp. 73–97. River Edge, NJ: World Science Publisher, 2003.
  • [Dieker and Saliola 14] A. B. Dieker and Franco Saliola. “Spectral Analysis of Random-to-Random Markov Chains.” In preparation, 2014.
  • [Diaconis and Saloff-Coste 95] P. Diaconis and L. Saloff-Coste. “Random Walks on Finite Groups: A Survey of Analytic Techniques.” In Probability Measures on Groups and Related Structures, XI (Oberwolfach, 1994), edited by Herbert Heyer, pp. 44–75. River Edge, NJ: World Science Publisher, 1995.
  • [Levin et al. 09], David A. Levin, Yuval Peres, and Elizabeth L. Wilmer. Markov Chains and Mixing Times. Providence, RI: American Mathematical Society, 2009. With a chapter by James G. Propp and David B. Wilson.
  • [Morris and Qin 14] Ben Morris and Chuan Qin. “Improved Bounds for the Mixing Time of the Random-to-Random Insertion Shuffle.” Preprint, arXiv:1412.0070, 2014.
  • [Reyes 02] Jay-Calvin Uyemura Reyes. “Random Walk, Semi-Direct Products, and Card Shuffling.” Thesis (Ph.D.), Stanford University, ProQuest LLC, Ann Arbor, MI, 2002.
  • [Stein et al. 13] W. A. Stein et al. “Sage Mathematics Software (Version 5.9).” The Sage Development Team. Available online (http://www.sagemath.org), 2013.
  • [Sagan 01] Bruce E. Sagan. The Symmetric Group, Volume 203 of Graduate Texts in Mathematics, Second edition. New York, NY: Springer-Verlag, 2001. Representations, combinatorial algorithms, and symmetric functions.
  • [The Sage-Combinat community 08] The Sage-Combinat Community. “Sage-Combinat: Enhancing Sage as a Toolbox for Computer Exploration in Algebraic Combinatorics.” Available online (http://combinat.sagemath.org), 2008.
  • [Saloff-Coste and Zúñiga 08] L. Saloff-Coste and J. Zúñiga. “Refined Estimates for Some Basic Random Walks on the Symmetric and Alternating Groups.” ALEA Lat. Am. J. Probab. Math. Stat. 4 (2009), 359–392.
  • [Stanley 09] Richard P. Stanley. “Promotion and Evacuation.” Electron. J. Combin. 16:2, Special volume in honor of Anders Bjorner (2009), Research Paper 9, 24.
  • [Subag 13] Eliran Subag. “A Lower Bound for the Mixing Time of the Random-to-Random Insertions Shuffle.” Electron. J. Probab. 18:20 (2013), 20.
  • [Wilkinson 65] J. H. Wilkinson. The Algebraic Eigenvalue Problem. Oxford: Clarendon Press, 1965.

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Order Reprints Request Corporate Permissions

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

Request Academic Permissions

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.

Related research

People also read lists articles that other readers of this article have read.

Recommended articles lists articles that we recommend and is powered by our AI driven recommendation engine.

Cited by lists all citing articles based on Crossref citations.
Articles with the Crossref icon will open in a new tab.