Title: Random Pattern-Avoiding Permutations
| Speaker: | Neal Madras |
| Affiliation: | York University |
| Room: | MC 5417 |
Abstract:
A
"pattern
of
length
k"
is
simply
a
permutation
of
{1,..,k}.
This
pattern
is
said
to
be
contained
in
a
permutation
of
{1,...,N}
(for
N>k)
if
there
is
a
subsequence
of
k
elements
of
the
(long)
permutation
that
appears
in
the
same
relative
order
as
the
pattern.
(E.g.
the
pattern
312
is
contained
in
the
permutation
2463175
because
the
latter
contains
the
subsequence
615.)
A
permutation
avoids
the
pattern
P
if
it
does
not
contain
P.
For
a
given
P,
let
AV[N;P]
be
the
set
of
permutations
of
{1,..,N}
that
avoid
P.
The
cardinality
of
AV[N;P]
has
been
extensively
studied
by
combinatorialists.
This
talk
looks
at
properties
of
permutations
drawn
uniformly
at
random
from
AV[N;P]
for
large
N.
When
such
a
permutation
is
plotted
as
a
function
from
{1,..,N}
to
itself,
some
striking
structure
appears.
I
shall
describe
what
is
known
probabilistically
about
such
structure,
including
clustering
and
large
empty
regions
in
the
plot.
I
shall
also
describe
an
attempt
(with
Justin
Troyka)
to
study
these
plots
under
periodic
boundary
conditions,
inspired
by
work
in
statistical
physics.
This
led
us
to
consider
affine
permutations
on
the
integers
with
a
new
boundedness
condition.