# The $k$-Independence Number

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ć'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ć 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\ge 3$ is still an open problem. In this talk, we present the best polynomial for the case $k=3.$