Additive Number Theory, Graphs and Matroids
| Speaker: | Ahmad Abdi |
|---|---|
| Affiliation: | University of Waterloo |
| Room: | Mathematics and Computer Building (MC) 6486 |
Abstract:
Cauchy
in
1813
and
Davenport
in
1935
proved
the
following
fundamental
result
in
Additive
Number
Theory:
given
prime
p
and
two
subsets
A
and
B
of
Z_p,
the
number
of
elements
produced
as
a
sum
of
an
element
from
A
and
an
element
from
B
is
at
least
the
minimum
of
p
and
|A|+|B|-1.
In
1990,
Bialostocki
and
Dierker
added
a
graph
theoretic
flavour
to
the
field
by
showing
the
following:
in
a
complete
graph
on
p+1
vertices
where
each
edge
has
a
weight
in
Z_p,
there
is
always
a
zero-sum
spanning
tree.
In
this
talk,
I
will
give
an
overview
of
these
results,
and
bring
to
your
attention
a
beautiful
conjecture
of
Schrijver
and
Seymour
that
ties
together
these
two
results,
along
with
many
other
results
of
Kneser,
Erdos-Ginzburg-Ziv,
Grynkiewicz,
Furedi
and
Kleitman,
etc.
Vaguely
speaking,
the
conjecture
provides
a
lower
bound
on
the
number
of
bases
of
different
weights
in
a
matroid,
given
an
arbitrary
weighting
of
its
edges
from
an
arbitrary
abelian
group.
I
will
also
discuss
a
major
recent
work
of
DeVos,
Goddyn
and
Mohar,
where
they
prove
the
conjecture
for
a
special
class
of
matroids.