Friday, May 6, 2011 3:30 pm
-
4:30 pm
EDT (GMT -04:00)
Zarankiewicz' Conjecture is finite
| Speaker: | Bruce Richter |
|---|---|
| Affiliation: | University of Waterloo |
| Room: | Mathematics & Computer Building (MC) 5158 |
Abstract:
Zarankiewicz' Conjecture states that the crossing number of the complete bipartite graph K(m,n) is [m/2] [(m-1)/2)] [n/2] [(n-1)/2]. To date, this has been proved only for n≤5 (Kleitman in 1971) and a few other values. The smallest open cases are (m,n) = (7,11) and (9,9).
Woodall
wondered
if
the
proof
of
Zarankiewicz'
Conjecture
for
a
finite
number
of
values
of
n
(when
m=7)
would
suffice
to
prove
the
conjecture
for
m=7.
For
each
m,
we
exhibit
a
number
N(m)
so
that,
if
Zarankiewicz'
Conjecture
is
true
for
K(m,n)
whenever
n≤N(m),
then
it
is
true
for
all
n.
This
is
joint
work
with
Robin
Christian
and
Gelasio
Salazar.