HOME

RESEARCH

TEACHING

PERSONAL


 

Full version of my research statement.

My recent research is mostly dedicated to the subject of pattern avoidance in permutations, also known as the study of "restricted permutations" and "permutations with forbidden subsequences." The interest in this topic is motivated by its relations to well studied combinatorial structures, such as set partitions, Dyck paths, Motzkin paths, plane walks, involutions, as well as many other structures. This research direction is very young, with its roots in the works by Rotem, Rogers, and Knuth in the 1970s and 1980s. However, the first systematic study was not undertaken until the paper by Simion and Schmidt appeared in 1985. Since then more than 400 papers have been written on the topic, as well as the book "Combinatorics of Permutations" by Bona. More information on the subject, in particular, the names of the people involved in the research, can be found on Permutation Patterns Home Page by Atkinson.

One of my most interesting contributions to this field, which belongs to algebraic combinatorics and combinatorics on words, is introducing the partially ordered patterns (POPs), which further generalize the generalized patterns (GPs) introduced by Babson and Steingrimsson. It turns out that POPs not only provide information on multi-avoidance of certain sets of GPs, but also allow to find the exponential generating function (e.g.f.) for the entire distribution of the maximum number of non-overlapping occurrences of a consecutive pattern p, if we only know the e.g.f. for the number of permutations that avoid p. Moreover, as a corollary to a much more general result on POPs, one gets the e.g.f. for the entire distribution of peaks in permutations. Also, POPs give interesting relations to other combinatorial objects, and allow, e.g., to find a combinatorial interpretation to Cartesian products of objects related to restricted permutations. The study of POPs in permutations was extended to that in words in collaboration with Mansour and to compositions in collaboration with Heubach and Mansour.

Some of my other research  interests include counting the number of (vertex) independent sets in certain classes of graphs, as well as some other problems related to graph theory. In particular, I am interested in applications of graphs in combinatorics on words problems, as well as in the growth of free spectrum algebraic problems.

Full version of my research statement.