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 Steingrímsson. 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.