2:30-3:40pm: Poster Session (Algorithms)

Moderator: Michael Albert
(This is 12:30pm US Pacific, 3:30pm US Eastern, 7:30pm GMT, 8:30pm in the UK, 9:30pm CEST, 10:30pm in Israel, 3:30am in China, 5:30am in Sydney, 7:30am in New Zealand)

Authors:

Title: TileScope – an algorithm for enumerating permutation classes (a software demo)

Author: Christian Bean (Université Paris Nord/Reykjavik University)
Joint work with: Jay Pantone (Marquette University), Émile Nadeau (Reykjavik University), Henning Ulfarsson (Reykjavik University)

Abstract: Combinatorial exploration seeks to fully describe the structure of a combinatorial family. The TileScope algorithm is an application of combinatorial exploration to permutation classes. It is capable of finding a combinatorial specification for almost every permutation class that avoid some subset of length 4 patterns, and many more. The goal of this poster/demo is to get you using our algorithm on your computer!

See https://github.com/PermutaTriangle/Tilings.

Video: Bean_video

[Back to the top]

Title: Permutations sortable by two restricted stacks: Catalan and Schröder cases

Author: Giulio Cerbai (University of Firenze, Italy)
Joint work with: Jean-Luc Baril (Université de Bourgogne Franche-Comté, France), Carine Khalil (Université de Bourgogne Franche-Comté, France), Vincent Vajnovszki (Université de Bourgogne Franche-Comté, France)

Abstract: Pattern avoiding machines were introduced in a recent paper by Claesson, Cerbai and Ferrari in attempt to gain a better understanding of permutations sortable using two stacks in series. They consist of two restricted stacks in series, equipped with a right-greedy procedure, where the first stack avoids a fixed pattern, reading the elements from top to bottom; and the second stack avoids the pattern 21 (which is a necessary condition for the machine to sort permutations). The same authors provide a characterization of the patterns for which sortable permutations form a class. They also show that those patterns are enumerated by the Catalan numbers. For specific patterns, as 132 and the decreasing pattern of any length, a geometrical description of sortable permutations is also obtained. Some of these results have been further generalized to Cayley permutations by Cerbai.

In this work we study pattern avoiding machines where the first stack avoids a pair of patterns. For the pair (123,132), we prove that sortable permutations are those avoiding the patterns 2314, 3214, 4213 and the generalized pattern [2413 barred on the second element. We prove that sortable permutations are enumerated by the Catalan numbers by showing that the distribution of the first element is given by the well-known Catalan triangle. By suitably adapting a result for Cayley permutations, we show that three other pairs of patterns are counted by the Catalan numbers, namely (123,213), (132,312) and (231,321). Next we consider the pair (132,231). We show that sortable permutations are those avoiding 1324 and 2314, a set whose enumeration is given by the Schröder numbers. Finally, we discuss some open problems and questions.

Poster: Cerbai_poster

[Back to the top]

Title: Preimages under the Queuesort algorithm

Author: Luca Ferrari (University of Firenze)
Joint work with: Lapo Cioni (University of Firenze)

Abstract: Queuesort is an algorithm which tries to sort an input permutation $\pi$ by using a queue; allowed operations are: pushing an element of $\pi$ into the back of the queue, moving the element in front of the queue into the output, and moving an element of $\pi$ directly into the output, without entering the queue.
Similarly to what has been done for Stacksort (more recently by Defant and less recently by Bousquet-Mélou), we study preimages of permutations under Queuesort. First of all, we give an alternative way of describing the output $q(\pi)$ of Queuesort on input $\pi$. This allows us to provide a recursive characterization of preimages of a given permutation, from which we deduce a recursive procedure to generate them. To prove the above results, it is convenient to factor a permutation $\pi$ as $\pi=M_1 P_1 M_2 P_2 \cdots M_{k-1}P_{k-1}M_k$, where the $M_i$’s are all the maximal nonempty sequences of LTR maxima (except for $M_k$, which can be empty) of $\pi$. Next, we find some enumerative results, concerning the number of preimages of a given permutation. More specifically, if $\pi=M_1 P_1 M_2$, with $|M_2 |=1$, then $|q^{-1}(\pi)|=C_m$, where $m=|M_1 |$ and $C_m$ is the $m$-th Catalan number. Moreover, we also find a general formula for $|q^{-1}(\pi)|$ when $\pi=M_1 P_1 M_2$, from which we deduce that $|q^{-1}(\pi)|$ can be expressed as a linear combination of Catalan numbers. Finally, we find the number of permutations which have only one preimage, which is (essentially) the number of derangements.

Poster: Ferrari_poster

[Back to the top]

Title: On permutations sorted by k passes through a deterministic pop-stack

Author: Yoong Kuan (Andrew) Goh (University of Technology Sydney)

Abstract: A pop stack is a sorting device which operates as follows: at each step one can either push a token from the input stream onto the top of the stack, else pop the entire stack from top to bottom onto the output stream. A deterministic pop stack processes sequences of distinct numbers as follows: if the element on top of the stack is bigger than the next incoming element from the input, push the incoming element onto the stack. Meanwhile, if the incoming element larger than the element on top of the stack, pop the entire contents of the stack (which by construction will be ordered from smallest on top to largest on the bottom) to the output.

A permutation can be sorted by $k$ passes through a deterministic pop stack if after repeating the procedure $k$ times, the sequence is ordered from smallest to largest. In 1981, Avis and Newborn characterised permutations sorted by 1-pass pop stack, initiating the study of pop stack sorting. Pudwell and Smith characterised permutations sorted by 2-pass pop stack, in terms of avoiding a finite set of patterns of a certain type, and enumerated them by giving a bijection to a special family of polynominoes. Claesson and Gu\dh{}mundsson then gave a general enumeration formula for $k$ passes .

In this talk, I will show that $k$-pass deterministic pop-stack sortable permutations are characterised by a finite list of forbidden (usual and barred) patterns for all $k\in \N$. In order to prove this, we realised the current notions of what it means to avoid a set of barred and unbarred patterns would not suffice. Because of this we have introduced a new notion called $PB$-containment. We show that this is exactly the right notion for $k$ pass pop-stack sorting especially when $k > 3$. The proof of our characterisation is in the form of a constructive algorithm, which can be implemented to obtain a finite list of patterns.

Poster: Goh_poster

[Back to the top]

Title: Encoding labelled p-Riordan graphs by words and pattern-avoiding permutations

Author: Kittitat Iamthong (University of Strathclyde)
Joint work with: Ji-Hwan Jung (Seoul National University), Sergey Kitaev (University of Strathclyde)

Abstract: The notion of a p-Riordan graph generalizes that of a Riordan graph, which, in turn, generalizes the notions of a Pascal graph and a Toeplitz graph. In this paper we introduce the notion of a p-Riordan word, and show how to encode p-Riordan graphs by p-Riordan words. For special important cases of Riordan graphs (the case p=2) and oriented Riordan graphs (the case p=3) we provide alternative encodings in terms of pattern-avoiding permutations and certain balanced words, respectively. As a bi-product of our studies, we provide an alternative proof of a known enumerative result on closed walks in the cube.

Poster: Iamthong_poster
Video: Iamthong_video

[Back to the top]

Title: A Complexity Dichotomy for Permutation Pattern Matching on Grid Classes

Author: Michal Opler (Charles University in Prague)
Joint work with: Vít Jelínek (Charles University in Prague), Jakub Pekárek (Charles University in Prague)

Abstract: Permutation Pattern Matching (PPM) is the problem of deciding for a given pair of permutations p and t whether the pattern p is contained in the text t. Bose, Buss and Lubiw showed that PPM is NP-complete. In view of this result, it is natural to ask how the situation changes when we restrict the pattern p to a fixed permutation class C; this is known as the C-Pattern PPM problem. There have been several results in this direction, namely the work of Jelínek and Kynčl who completely resolved the hardness of Av(s)-Pattern PPM, i.e. when the pattern p is s-avoiding for some permutation s.

Grid classes are special kind of permutation classes, consisting of permutations admitting a grid-like decomposition into simpler building blocks. Of particular interest are the so-called monotone grid classes, in which each building block is a monotone sequence. Recently, it has been discovered that grid classes, especially the monotone ones, play a fundamental role in the understanding of the structure of general permutation classes. This motivates us to study the hardness of C-Pattern PPM for a (monotone) grid class C.

We provide a complexity dichotomy for C-Pattern PPM when C is taken to be a monotone grid class. Specifically, we show that the problem is polynomial-time solvable if a certain graph associated with C, called the cell graph, is a forest, and it is NP-complete otherwise. We further generalize our results to grid classes whose blocks belong to classes of bounded grid-width. We show that the C-Pattern PPM for such a grid class C is polynomial-time solvable if the cell graph of C avoids a cycle or a certain special type of path, and it is NP-complete otherwise.

Poster: Opler_poster

[Back to the top]

Back to the Workshop Program