2:30-3:40pm (US Central): Poster Session (Nonclassical Pattern Avoidance)

Moderator: Megan Martinez
(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)


Title: Counting king permutations on the cylinder

Author: Eli Bagno (Jerusalem College of Technology)
Joint work with: Estrella Eisenberg (Jerusalem College of Technology), Shulamit Reches (Jerusalem College of Technology), Moriah Sigron (Jerusalem College of Technology)

Abstract: A permutation $\sigma=[\sigma_1,\dots,\sigma_n] \in S_n$ is called a cylindrical king permutation if $ |\sigma_i-\sigma_{i+1}|>1$ for each $1\leq i \leq n-1$ and $|\sigma_1-\sigma_n|>1$. The name comes from the the way one can see these permutations as describing locations of $n$ kings on a chessboard of order $n\times n$ in such a way that (each row and each column contains exactly one king and) no two kings are attacking each other, with the additional condition that a king can move off a certain row and reappear at the beginning of that row.

In the paper “On the poset of non-attacking king permutations”, published recently in the European Journal of Combinatorics, we dealt with the more general set of ‘king permutations’ i.e. the ones which satisfy only the first of the two conditions above. This set constitutes a poest under the well known containment relation on permutations.

In this work we focus on the cylindrical king permutation. We have enumerative as well structural properties of this sub-poset.

We present some results regarding the distribution of the cylindrical king permutations, including some interesting recursions. We also prove that their asymptotic proportion in the set of the ‘king permutations’ is $1$.

We investigate the poset of these king permutations and its structure, starting with the building blocks which happen to be the cylindrical king permutations of order $5$.

In addition, we examine those cylindrical king permutations whose downset is as large as possible in the upper ranks. We use a modification of Manhattan distance of the plot of a permutation and some of its applications to the cylindrical context to find a criterion for such a permutation to be $k-$ prolific. One of our main results is that the maximal gap between two permutations in the poset of cylindrical permutations is $4$.

Poster: Bagno_poster

[Back to the top]

Title: On permutation patterns with constrained gap sizes

Author: Stoyan Dimitrov (University of Illinois at Chicago)

Abstract: We consider avoidance of permutation patterns with designated gap sizes between pairs of consecutive letters. We call the patterns having such constraints distant patterns (DPs) and we show their relation to other pattern notions investigated in the past. New results on DPs with 2 and 3 letters are obtained including a generating function found using the block-decomposition method in a non-trivial way. Furthermore, we prove two conjectures of Kuszmaul using a DP interpretation and we give that perspective to four of the other conjectures listed there. DPs with tight gap constraints are also considered in order to deduce a somewhat surprising relation between the sets of permutations avoiding the classical patterns 123 and 132. In addition, interesting Stanley-Wilf analogues for DPs are discussed, as well as some open questions.

Poster: Dimitrov_poster

[Back to the top]

Title: 2-avoidance classes

Author: Murray Elder (University of Technology Sydney)
Joint work with: Yoong Kuan Goh (University of Technology Sydney)

Abstract: We introduce a (new?) notion of 2-avoidance, motivated by the study of permutations that can be sorted by $k$ pop stacks in series. We pose some open questions about the existence of 2-avoidance classes with growth rate strictly between exponential and factorial.

Poster: Elder_poster
Video: Elder_video
Note: The video is available in interactive mode here!

[Back to the top]

Title: Enumerating Symmetric and Asymmetric Peaks in Dyck paths

Authors: Rigoberto Florez (The Citadel) and Jose Luis Ramirez (Universidad Nacional de Colombia)

Abstract: In 2018, Asakly –in Enumerating symmetric and non-symmetric peaks in word– studied symmetric peaks and asymmetric peaks for k-ary words. In this poster we study an adaptation of these two concepts to the Dyck words on the alphabet {X,Y}. We say that a peak is symmetric if the maximal pyramid having the peak is not preceded by X and not followed by X. A peak is asymmetric if the maximal pyramid having the peak is either preceded by X or followed by X. In this poster we give recursive relations, generating functions, as well as closed formulas to count the total number of symmetric and asymmetric peaks, and to compute the symmetric weights.

Poster: Florez_Ramirez_poster
Video: Florez_Ramirez_video

[Back to the top]

Title: On k-11-representable graphs

Author: Sergey Kitaev (University of Strathclyde)
Joint work with: Gi-Sang Cheon (Sungkyunkwan University), Jinha Kim (Technion – Israel Institute of Technology), Minki Kim (Technion – Israel Institute of Technology), Artem Pyatkin (Sobolev Institute of Mathematics)

Abstract: Distinct letters x and y alternate in a word w if after deleting in w all letters but the copies of x and y we either obtain a word of the form xyxy… (of even or odd length) or a word of the form yxyx… (of even or odd length). A simple graph G=(V,E) is word-representable if there exists a word w over the alphabet V such that letters x and y alternate in w if and only if xy is an edge in E. Thus, edges of G are defined by avoiding the consecutive pattern 11 in a word representing G, that is, by avoiding xx and yy.

In 2017, Jeff Remmel introduced the notion of a k-11-represent-able graph for a non-negative integer k, which generalizes the notion of a word-representable graph. Under this representation, edges of G are defined by containing at most k occurrences of the consecutive pattern 11 in a word representing G. Thus, word-representable graphs are precisely 0-11-representable graphs. Our key result in this paper is showing that every graph is 2-11-represent-able by a concatenation of permutations, which is rather surprising taking into account that concatenation of permutations has limited power in the case of 0-11-representation. Also, we show that the class of word-representable graphs, studied intensively in the literature, is contained strictly in the class of 1-11-representable graphs. Another result that we prove is the fact that the class of interval graphs is precisely the class of 1-11-representable graphs that can be represented by uniform words containing two copies of each letter. This result can be compared with the known fact that the class of circle graphs is precisely the class of 0-11-representable graphs that can be represented by uniform words containing two copies of each letter.

Poster: Kitaev_poster1
Video: Kitaev_video1

[Back to the top]

Title: On partially ordered patterns of length 4 and 5 in permutations

Author: Sergey Kitaev (University of Strathclyde)
Joint work with: Alice L.L. Gao (Northwestern Polytechnical University)

Abstract: Partially ordered patterns (POPs) generalize the notion of classical patterns studied widely in the literature in the context of permutations, words, compositions and partitions. In an occurrence of a POP, the relative order of some of the elements is not important. Thus, any POP of length k is defined by a partially ordered set on k elements, and classical patterns correspond to k-element chains. The notion of a POP provides a convenient language to deal with larger sets of permutation patterns.

This paper contributes to a long line of research on classical permutation patterns of length 4 and 5, and beyond, by conducting a systematic search of connections between sequences in the Online Encyclopedia of Integer Sequences (OEIS) and permutations avoiding POPs of length 4 and 5. As the result, we (i) obtain 13 new enumerative results for classical patterns of length 4 and 5, and a number of results for patterns of arbitrary length, (ii) collect under one roof many sporadic results in the literature related to avoidance of patterns of length 4 and 5, and (iii) conjecture 6 connections to the OEIS. Among the most intriguing bijective questions we state, 7 are related to explaining Wilf-equivalence of various sets of patterns, e.g. 5 or 8 patterns of length 4, and 2 or 6 patterns of length 5.

Poster: Kitaev_poster2
Video: Kitaev_video2

[Back to the top]

Title: Distributions of mesh patterns of short lengths

Author: Philip Biao Zhang (Tianjin Normal University)
Joint work with: Sergey Kitaev (University of Strathclyde)

Abstract: A systematic study of avoidance of mesh patterns of length 2 was conducted by Hilmarsson et al., where 25 out of 65 non-equivalent cases were solved. In this paper, we give 27 distribution results for these patterns including 14 distributions for which avoidance was not known. Moreover, for the unsolved cases, we prove an equidistribution result (out of 6 equidistribution results we prove in total), and conjecture 6 more equidistributions. Finally, we find seemingly unknown distribution of the well known permutation statistic “strict fixed point”, which plays a key role in many of our enumerative results. This paper is the first systematic study of distributions of mesh patterns. Our techniques to obtain the results include, but are not limited to, obtaining functional relations for generating functions, and finding recurrence relations and bijections.

Poster: Zhang_poster

[Back to the top]

Back to the Workshop Program