1pm-2:10pm (US Central): Poster Session (Patterns and Other Combinatorial Objects)

Moderator: Miklos Bona
(This is 11am US Pacific, 2pm US Eastern, 6pm GMT, 7pm in the UK, 8pm CEST, 9pm in Israel, 2am in China, 4am in Sydney, 6am in New Zealand)

Authors:

Title: K block set partition patterns and statistics

Author: Amrita Acharyya (University of Toledo)
Joint work with: Robinson Paul Czajkowski (University of Toledo), Allen Richard Williams (University of Toledo)

Abstract: A set partition σ of [n] = {1,··· ,n} contains another set partition ω if a standardized restriction of σ to a subset S ⊆ [n] is equivalent to ω. Otherwise, σ avoids ω. Sagan and Goyt have determined the cardinality of the avoidance classes for all sets of patterns on partitions of [3]. Additionally, there is a bijection between the set partitions and restricted growth functions (RGFs). Wachs and White defined four fundamental statistics on those RGFs. Sagan, Dahlberg, Dorward, Gerhard, Grubb, Purcell, and Reppuhn consider the distributions of these statistics over various avoidance classes and they obtained four variate analogues of the previously cited cardinality results. They did the first thorough study of these distributions. The analogues of their many results follows for set partitions with exactly k blocks for a specified positive integer k. These analogues are discussed in this work. Also we discussed a minor variation of the four fundamental statistics on those RGFs defined by Wachs and White. We found analogues of their many results follows for that variation and the specialization of them with k blocks as well.

Poster: Acharyya_poster

[Back to the top]

Title: Enumerative combinatorics of the matching pattern poset

Author: Matteo Cervetti (University of Trento)
Joint work with: Luca Ferrari (University of Firenze)

Abstract: A matching of the set [2n] = {1, 2, …, 2n} is a partition of [2n] into blocks with two elements, i.e. a graph on [2n] such that every vertex has degree one. Given two matchings σ and τ , we say that σ is a pattern of τ when σ can be obtained from τ by deleting some of its edges and consistently relabeling the remaining vertices. This is a partial order relation, turning the set of all matchings into a poset, called the matching pattern poset. Here we continue the study of classes of pattern avoiding matchings initiated by Bloom and Elizalde (2012), Chen, Deng Du, Stanley and Yan (2007), Jelinek and Mansour (2010). In particular, we work out a recursive formula to count matchings avoiding the juxtaposition of two smaller matchings; this allows us to enumerate two new classes of pattern avoiding matchings, namely matchings avoiding 12123434 and matchings avoiding 1212345345 (this notation means that the two vertices of each edge of the matching are the positions of two equal letters). Moreover, we describe a recursive formula for the generating function of matchings avoiding the lifting of a given pattern τ and two additional patterns, namely 123132 and 123213. From here, we are able to find the generating function of matchings avoiding the three patterns 123231, 123132, 123213. Finally, we introduce the notion of unlabeled pattern, which provides a natural combinatorial way to collect patterns; using unlabeled patterns, we determine closed form expressions for the number of matchings avoiding the set of patterns {112323, 123231, 123312, 121233, 121332, 122313} and the set of patterns {121323, 123213, 123132} (in the latter case, we exploit a nice bijection with ternary trees). We conclude by presenting some starting results concerning the structure of intervals in the matching pattern poset.

Poster: Cervetti_poster

[Back to the top]

Title: Pattern distribution in faro words and permutations

Author: Sergey Kirgizov (LIB, Univ. Bourgogne Franche-Comté, France)
Joint work with: Jean-Luc Baril (LIB, Univ. Bourgogne Franche-Comté, France)

Abstract: The faro shuffle is a well known technique to shuffle a deck of cards, where the deck is split in two at the middle, and the cards from the two halves are interlaced by taking alternatively the bottoms of packets. For two k-ary words u and v such that 0≤|u|−|v|≤1, the faro shuffle of u and v is the k-ary word of length |u|+|v| obtained by interlacing the letters of u and v as follows: u₁v₁u₂v₂u₃v₃… Let S(n,k) be the set of n-length faro shuffles of two non-decreasing k-ary words and denote by Pₙ the set of permutations in S(n,n) which we call faro permutations. For instance, S(4,2) = {1111, 1112, 1121, 1122, 1212, 1222, 2121, 2122, 2222} and P₃={123, 132, 213}.

We focus on the distribution and the popularity of consecutive patterns of length at most three in faro words and permutations. Our method consists in showing how patterns are getting transferred from faro words and permutations to lattice paths, which settles us in a more suitable ground in order to provide generating functions.

More precisely, we present a constructive bijection between S(n,k) and the set of dispersed Dyck paths of length n+2k−2 having k−1 peaks. For any consecutive pattern of length at most three σ, the bijection transports the statistic of the number of occurrences of σ to a related statistic on paths. Using the bijection, we derive enumerating results about the patterns on S(n,k), among them we give the trivariate generating function enumerating words in S(n,k) with respect to the length, the arity, and the number of descents. A counterpart study for faro permutations is also presented.

Poster: Kirgizov_poster
Video: Kirgizov_video

[Back to the top]

Title: An expression for the Möbius function, μ[σ,π], of the permutation pattern poset based on intervals in π

Author: David Marchant (The Open University)

Abstract: A balloon permutation is formed from the merge of two permutations, α and β, and has the property that β occurs as an interval in the balloon permutation. Every permutation π with length > 1 can be described as a balloon permutation by choosing an arbitrary interval strictly contained in π, and then defining that interval to be β.

If we have two permutations, σ and π, with σ < π, then we find an expression for the Möbius function of the interval [σ,π]. Our technique is to treat the upper bound, π, as a balloon permutation constructed from some α and β, and then show that μ[σ,π] can be written as a sum over a set of permutations, all of which contain β as an interval, plus a correction factor.

We show that for certain types of balloon permutation (“wedge permutations”) the correction factor is always zero. We also show that any permutation can be treated as a wedge permutation by restricting the choice of the interval used for β. Where the length of α or β is 1, our expression corresponds to existing results.

We also show that the principal Möbius function, μ[1,π], of a wedge permutation is always a multiple of the principal Möbius function of β.

Poster: Marchant_poster

[Back to the top]

Title: Mod k alternating permutations in Sn(132)

Author: Dun Qiu (Beijing Jiaotong University)

Abstract: We study pattern avoidance problems in parity alternating permutations and mod k alternating permutations in Sn(132), answering a question of Ran Pan (Project P Problem 10). We compute the generating function of parity alternating permutations avoiding 132 and enumerate the coefficients. Then we study mod k alternating permutations avoiding 132 and compute the generating functions. We also define parity alternating circular permutation and study pattern avoidance in parity alternating circular permutations.

Poster: Qiu_poster

[Back to the top]

Title: Inversion sequences avoiding pairs of patterns

Author: Chunyan Yan (Jimei University)
Joint work with: Zhicong Lin (Shandong University)

Abstract: The enumeration of inversion sequences avoiding a single pattern was initiated by Corteel–Martinez–Savage–Weselcouch and Mansour–Shattuck independently. Their work has sparked various investigations of generalized patterns in inversion sequences, including patterns of relation triples by Martinez and Savage, consecutive patterns by Auli and Elizalde, and vincular patterns by Lin and Yan.

In this paper, we carried out the systematic study of inversion sequences avoiding two patterns of length $3$. Our enumerative results establish further connections to the OEIS sequences and some classical combinatorial objects, such as restricted permutations, weighted ordered trees and set partitions.

Since patterns of relation triples are some special multiple patterns of length $3$, our results complement the work by Martinez and Savage. In particular, one of their conjectures regarding the enumeration of $(021,120)$-avoiding inversion sequences is solved.

Poster: Yan_poster

[Back to the top]

Back to the Workshop Program