License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.AofA.2018.28
URN: urn:nbn:de:0030-drops-89219
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8921/
Go to the corresponding LIPIcs Volume Portal

Hitczenko, Pawel ; Yaroslavskiy, Aleksandr

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

pdf-format:
LIPIcs-AofA-2018-28.pdf (0.4 MB)

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.

BibTeX - Entry

@InProceedings{hitczenko_et_al:LIPIcs:2018:8921,
  author =	{Pawel Hitczenko and Aleksandr Yaroslavskiy},
  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 =	{James Allen Fill and Mark Daniel Ward},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8921},
  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}
}

Keywords: Tree-like tableaux, permutation tableaux, partially asymmetric simple exclusion process
Collection: 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)
Issue Date: 2018
Date of publication: 18.06.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI