Title: On the edit distance of powers of cycles
| Speaker: | Ryan Martin |
| Affiliation: | Iowa State University |
| Room: | MC 5479 |
Abstract:
The
edit
distance
between
two
graphs
on
the
same
labeled
vertex
set
is
defined
to
be
the
size
of
the
symmetric
difference
of
the
edge
sets,
divided
by
${n\choose\lfloor
n/2\rfloor}$.
The
edit
distance
function
of
a
hereditary
property
$\mathcal{H}$
is
a
function
of
$p\in[0,1]$
that
measures,
in
the
limit,
the
maximum
normalized
edit
distance
between
a
graph
of
density
$p$
and
$\mathcal{H}$.
It
is
also,
again
in
the
limit,
the
edit
distance
of
the
Erd\H{o}s-R\'{e}nyi
random
graph
$G(n,
p)$
from
$\mathcal{H}$.
In
this
talk,
we
address
the
edit
distance
function
for
${\rm
Forb}(H)$,
where
$H=C^t_h$,
the
$t^{\rm
th}$
power
of
the
cycle
of
length
$h$.
For
$h\ge
2t(t
+
1)
+
1$
and
$h$
not
divisible
by
$t
+
1$,
we
determine
the
function
for
all
values
of
$p$.
For
$h
\ge
2t(t
+
1)
+
1$
and
$h$
divisible
by
$t
+
1$,
the
function
is
obtained
for
all
but
small
values
of
$p$.
We
also
obtain
some
results
for
smaller
values
of
$h$.
The
proof
methods
involve
a
weighted
version
of
P\'{o}sa's
classic
argument
on
Hamilton
cycles.
This
weighted
version
has
complications
that
do
not
occur
in
the
unweighted
case.
This
is
joint
work
with
Zhanar
Berikkyzy
and
Chelsea
Peck.