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 multiavoidance 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 nonoverlapping 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.
