LIPIcs.AofA.2018.28.pdf
- Filesize: 415 kB
- 13 pages
Document
Distribution of the Number of Corners in Tree-like and Permutation Tableaux
Authors
-
Part of:
Volume:
29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-06-18
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
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)
0PDF Downloads
References
-
J.-C. Aval, A. Boussicault, and P. Nadeau. Tree-like tableaux. Electron. J. Combin., 20(4):Paper 34, 24, 2013.
-
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.
- 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.
-
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.
- 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.
- 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.
- 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.
- 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.
- 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.
-
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.
- 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.
-
P. Hitczenko and A. Lohss. Corners in tree-like tableaux. Electron. J. Combin., 23(4):Paper 4.26, 18, 2016.
-
P. Laborde-Zubieta. Occupied corners in tree-like tableaux. Sém. Lothar. Combin., 74:Art. B74b, 14, [2015-2017].
- 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.
- 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.