1 Search Results for "Hitczenko, Pawel"


Document
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-dev.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}
}
  • Refine by Author
  • 1 Hitczenko, Pawel
  • 1 Yaroslavskiy, Aleksandr

  • Refine by Classification
  • 1 Mathematics of computing → Distribution functions
  • 1 Mathematics of computing → Enumeration
  • 1 Mathematics of computing → Generating functions
  • 1 Mathematics of computing → Permutations and combinations

  • Refine by Keyword
  • 1 Tree-like tableaux
  • 1 partially asymmetric simple exclusion process
  • 1 permutation tableaux

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2018

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