Speakers:
Ian
Payne
-
Pure
Mathematics
Georg
Osang
-
Combinatorics
&
Optimization
"The Payne Conjecture"
This
is
a
collaborative
colloquium
with
graduate
students
from
the
Pure
Math
and
C&O
departments.
Our
first
speaker,
Ian
Payne,
will
introduce
the
list
homomorphism
problem,
which
he
recently
showed
was
NP-complete
for
even
cycles
of
length
at
least
six.
While
attempting
to
reduce
the
case
for
graphs
with
even
girth
to
the
case
for
even
cycles,
Ian
conjectured
that
every
graph
with
girth
eight
would
contain
at
least
one
pair
of
vertices
at
distance
four
that
lie
on
a
unique
cycle.
During
his
talk
Ian
will
explain
how
this
conjecture
would
imply
that
list
homomorphism
is
NP-complete
for
graphs
with
girth
eight.
At
a
recent
pub
night,
Ian
shared
his
conjecture
with
some
of
the
C&O
grads.
Our
second
speaker,
Georg
Osang,
immediately
began
constructing
a
counterexample.
After
some
discussion
Georg
realized
that
the
well-known
Tutte-Coxeter
is
a
minimal
counterexample.
During
his
talk
Georg
will
describe
the
Tutte-Coxeter
graph
and
explain
how
it
disproves
the
Payne
conjecture.
Following
the
colloquium
there
will
be
a
social
event
at
the
Grad
House.