Friday, October 30, 2015 3:30 pm
-
3:30 pm
EDT (GMT -04:00)
Title: Improved Cheeger's inequalities
Speaker: | Lap Chi Lau |
Affiliation: | University of Waterloo |
Room: | MC 5501 |
Abstract:
Cheeger's
inequality
is
a
fundamental
result
in
spectral
graph
theory
relating
the
second
eigenvalue
to
graph
expansion.
We
present
two
generalizations
of
Cheeger's
inequality.
The
first
generalization
uses
more
spectral
information
(the
second
eigenvalue
and
the
k-th
eigenvalue)
to
give
an
improved
bound
on
the
graph
expansion.
The
second
generalization
uses
more
combinatorial
information
(the
edge
expansion
and
the
vertex
expansion)
to
give
an
improved
bound
on
the
second
eigenvalue.
We
discuss
how
these
results
provide
better
theoretical
explanations
of
the
empirical
success
of
spectral
partitioning
algorithms.
We
also
mention
some
similar
results
for
the
analysis
of
random
walks.