DIMACS logo

Pavel Paták

REU 2009

Hello, welcome to my REU page. My name is Pavel Paták and I'm a student of the Faculty of Maths and Physics of Charles University in Prague. I'm interested in combinatorics, logic, algebra, discrete geometry, topology and computer sciences.

I am here with a group of Czech people, our advisor is Aaron D. Jaggard. The other members of our research group are Ondra Bílka, Jozef Jirásek, Pavel Klavík, Jan Volec, Zuzka Safernová and Martin Tancer.

Pattern Avoidance and Parallels Between Families of Permutations

The main goal of our project is to decide wheter the fact that two patterns are I-equivalent implies that they are also S-equivalent.

Pattern avoidance

A permutation on n vertices is simple a bijection of {1,2,3,..,n} to {1,2,3,...n}. We will write the permutation 1-->2, 2-->4, 3-->5, 4-->1 and 5-->3 as follows: 24513. (The first number saying what is one mapped to etc.)

We say that a permutation avoids a pattern 231. If we can't find numbers with the same ordering relations as 231 in our permutation notation. For illustration 24513 contains 231, because the numbers 241 have the same ordering relations as 231. But the permuation 24513 avoids 321, for example.

Pattern equivalences

We say that two patterns A and B are S-equivalent, iff for each positive integer n, the number of permutations on n vertices avoiding A is the same as the number of permutations avoiding B.

We say that a permutation is an involution, iff it is its own inverse. (Which holds true if and only if the permutation contains cycles of length 2 and 1 only.)

We say that two patterns A and B are I-equivalent, iff for each positive integer n, the number of involutions on n vertices avoiding A is the same as the number of involutions avoiding B.

Goal

It is know that if two patterns are S-equivalent, they don't need to be I-equivalent. The classical example is 123 and 321. But it is not known wheter if I-equivalence implies S-equivalence. Our goal is to decide this open question.

The broad questions motivating this project involve parallels between different classes of permutations.

References:

A.D. Jaggard, Prefix Exchanging and Pattern Avoidance by Involutions, Electron. J. Combin. 9(2003), P.R16 (link)
A.D. Jaggard, J.J Marincel, Generating Tree Isomorphisms for Pattern - Avoiding Involutions, Preprint (link)
W. M. B. Dukes, Vit Jelinek, Toufik Mansour, Astrid Reifegerste, New Equivalences for Pattern Avoiding Involutions, Preprint: Arxiv:0708.1357v3 (link)
Z.Stankova, J.West, A New Class of Wilf-Equivalent Permutations, J. Algebr. Combin. 15(3), 2002 (link)