While the Size of Subgraphs Grows
| Speaker: | Jane Gao |
|---|---|
| Affiliation: | University of Waterloo |
| Room: | Mathematics and Computer Building (MC) 5136B |
Abstract:
Consider
the
random
graph
process
starting
from
an
empty
graph
on
n
vertices,
with
one
random
edge
being
placed
in
each
step.
For
a
given
graph
H,
at
which
step
of
the
process
will
H
appear
as
a
subgraph?
For
H
with
a
fixed
size,
say
a
triangle,
roughly
speaking,
this
happens
when
the
expected
number
of
the
copies
of
H
becomes
at
least
one.
However,
this
is
no
longer
true
when
H
has
a
growing
size
as
n,
e.g.
if
H
is
a
Hamilton
cycle,
due
to
a
heavy
correlation
between
the
copies
of
H
in
the
random
graph.
Dealing
with
heavy
correlations
is
a
big
challenge
when
studying
large
subgraphs
or
structures
in
random
objects.
Such
heavy
correlations
sometimes
result
in
surprising
and
anti-intuitive
phenomena.
I
will
survey
the
literature
on
properties
of
large
subgraphs
in
several
random
graph
models;
particularly
on
their
appearance
thresholds
and
the
distributions
of
their
counts.
As
a
particular
example,
we
will
study
the
distribution
of
the
number
of
matchings
of
size
t
in
G(n,p),
when
t
grows
from
one
to
n/2.
We
show
that
there
is
exactly
one
transition
of
the
limiting
distribution
as
t
grows,
and
we
determine
exactly
when
this
transition
takes
place.
This
talk
contains
joint
work
with
Cris
Sato.