Distribution of the Number of Corners in Tree-like and Permutation Tableaux

Authors Pawel Hitczenko, Aleksandr Yaroslavskiy



PDF
Thumbnail PDF

File

LIPIcs.AofA.2018.28.pdf
  • Filesize: 415 kB
  • 13 pages

Document Identifiers

Author Details

Pawel Hitczenko
  • Department of Mathematics, Drexel University, Philadelphia, PA 19104, USA
Aleksandr Yaroslavskiy
  • Department of Mathematics, Drexel University, Philadelphia, PA 19104, USA

Cite AsGet BibTex

Pawel Hitczenko and Aleksandr Yaroslavskiy. Distribution of the Number of Corners in Tree-like and Permutation Tableaux. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 28:1-28:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.AofA.2018.28

Abstract

In this abstract, we study tree-like tableaux and some of their probabilistic properties. Tree-like tableaux are in bijection with other combinatorial structures, including permutation tableaux, and have a connection to the partially asymmetric simple exclusion process (PASEP), an important model of interacting particles system. In particular, in the context of tree-like tableaux, a corner corresponds to a node occupied by a particle that could jump to the right while inner corners indicate a particle with an empty node to its left. Thus, the total number of corners represents the number of nodes at which PASEP can move, i.e., the total current activity of the system. As the number of inner corners and regular corners is connected, we limit our discussion to just regular corners and show that, asymptotically, the number of corners in a tableaux of length n is normally distributed. Furthermore, since the number of corners in tree-like tableaux are closely related to the number of corners in permutation tableaux, we will discuss the corners in the context of the latter tableaux.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Permutations and combinations
  • Mathematics of computing → Enumeration
  • Mathematics of computing → Generating functions
  • Mathematics of computing → Distribution functions
Keywords
  • Tree-like tableaux
  • permutation tableaux
  • partially asymmetric simple exclusion process

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. J.-C. Aval, A. Boussicault, and P. Nadeau. Tree-like tableaux. Electron. J. Combin., 20(4):Paper 34, 24, 2013. Google Scholar
  2. P. Billingsley. Probability and measure. Wiley Series in Probability and Mathematical Statistics. John Wiley &Sons, Inc., New York, third edition, 1995. A Wiley-Interscience Publication. Google Scholar
  3. A. Burstein. On some properties of permutation tableaux. Ann. Comb., 11(3-4):355-368, 2007. URL: http://dx.doi.org/10.1007/s00026-007-0323-0.
  4. S. Corteel and P. Hitczenko. Expected values of statistics on permutation tableaux. In 2007 Conference on Analysis of Algorithms, AofA 07, Discrete Math. Theor. Comput. Sci. Proc., AH, pages 325-339. Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2007. Google Scholar
  5. S. Corteel and P. Nadeau. Bijections for permutation tableaux. European J. Combin., 30(1):295-310, 2009. URL: http://dx.doi.org/10.1016/j.ejc.2007.12.007.
  6. S. Corteel and L. K. Williams. Tableaux combinatorics for the asymmetric exclusion process. Adv. in Appl. Math., 39(3):293-310, 2007. URL: http://dx.doi.org/10.1016/j.aam.2006.08.002.
  7. M. Depken and R. B. Stinchcombe. Exact joint density-current probability function for the asymmetric exclusion process. Phys. Rev. Lett., 93(2):040602, 2004. URL: http://dx.doi.org/10.1016/j.jcta.2006.04.001.
  8. M. Depken and R. B. Stinchcombe. Exact probability function for bulk density and current in the asymmetric exclusion process. Phys. Rev., 71(3):036120, 2005. URL: http://dx.doi.org/10.1016/j.jcta.2006.04.001.
  9. B. Derrida, M. R. Evans, V. Hakim, and V. Pasquier. Exact solution of a 1D asymmetric exclusion model using a matrix formulation. J. Phys. A, 26(7):1493-1517, 1993. URL: http://stacks.iop.org/0305-4470/26/1493.
  10. A. L. L. Gao, E. X. L. Gao, P. Laborde-Zubieta, and B. Y. Sun. Enumeration of corners in tree-like tableaux. Discrete Math. Theor. Comput. Sci., 18(3):Paper No. 17, 26, 2016. Google Scholar
  11. P. Hitczenko and S. Janson. Asymptotic normality of statistics on permutation tableaux. In Algorithmic probability and combinatorics, volume 520 of Contemp. Math., pages 83-104. Amer. Math. Soc., Providence, RI, 2010. URL: http://dx.doi.org/10.1090/conm/520/10255.
  12. P. Hitczenko and A. Lohss. Corners in tree-like tableaux. Electron. J. Combin., 23(4):Paper 4.26, 18, 2016. Google Scholar
  13. P. Laborde-Zubieta. Occupied corners in tree-like tableaux. Sém. Lothar. Combin., 74:Art. B74b, 14, [2015-2017]. Google Scholar
  14. E. Steingrímsson and L. K. Williams. Permutation tableaux and permutation patterns. J. Combin. Theory Ser. A, 114(2):211-234, 2007. URL: http://dx.doi.org/10.1016/j.jcta.2006.04.001.
  15. R. B. Stinchcombe and S. L. A. de Quieros. Statistics of current activity fluctuations in asymmetric flow with exclusion. Phys. Rev. E, 85(4):041111, 2012. URL: http://dx.doi.org/10.1016/j.jcta.2006.04.001.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail