DROPS

Document

DOI: 10.4230/LIPIcs.AofA.2018.28

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

Authors: Pawel Hitczenko and Aleksandr Yaroslavskiy

Published in: LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)

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.

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{hitczenko_et_al:LIPIcs.AofA.2018.28,
  author =	{Hitczenko, Pawel and Yaroslavskiy, Aleksandr},
  title =	{{Distribution of the Number of Corners in Tree-like and Permutation Tableaux}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  pages =	{28:1--28:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-078-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{110},
  editor =	{Fill, James Allen and Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.28},
  URN =		{urn:nbn:de:0030-drops-89219},
  doi =		{10.4230/LIPIcs.AofA.2018.28},
  annote =	{Keywords: Tree-like tableaux, permutation tableaux, partially asymmetric simple exclusion process}
}

Search Results

Documents authored by Hitczenko, Pawel

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

Abstract

Cite as

Thanks for your feedback!

Could not send message