Title: The $k$-Independence Number
| Speaker: | Lord Kavi |
| Affiliation: | University of Ottawa |
| Zoom: | Contact Soffia Arnadottir |
Abstract:
An
independent
set,
also
known
as
a
stable
set
or
coclique,
in
a
graph
is
a
set
of
vertices,
no
two
of
which
are
adjacent.
The
size
of
a
largest
independent
set
is
called
the
independence
number.
Two
classical
eigenvalue
bounds
on
the
independence
number,
proved
using
eigenvalue
interlacing
are
the
Hoffman's
ratio
bound
and
the
Cvetkovi\'{c}'s
inertia
bound.
There
are
a
number
of
generalizations
of
the
notion
of
independence
set
of
a
graph;
of
interest
to
us
is
the
following.
A
$k$-independent
set
in
a
graph
is
a
set
of
vertices
such
that
any
two
vertices
in
the
set
are
at
distance
at
least
$k+1$
in
the
graph.
The
$k$-independence
number
of
a
graph,
denoted
$\alpha_k$,
is
the
size
of
a
largest
$k$-independent
set
in
the
graph.
Using
interlacing,
Abiad
et
al
generalized
the
Hoffman
and
Cvetkovi\'{c}
spectral
bounds
on
$k$-independence,
which
involves
taking
polynomials
of
degree
at
most
$k$.
A
good
bound
therefore
depends
on
making
the
right
choice
of
a
polynomial.
For
the
generalized
Hoffman
bound
for
$\alpha_k$,
the
polynomial
$p(x)=x$
gives
the
standard
Hoffman
bound
for
the
independence
number
$\alpha_1$.
Abiad
et
al
also
gave
the
right
choice
of
polynomial
for
$k=2$
and
proposed
a
polynomial
for
a
general
$k$.
This
polynomial,
however,
is
often
not
the
best
choice.
Finding
an
appropriate
polynomial
that
yields
the
best
bound
possible
for
any
$k\geq
3$
is
still
an
open
problem.
In
this
talk,
we
present
the
best
polynomial
for
the
case
$k=3.$