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 α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 αk, the polynomial p(x)=x gives the standard Hoffman bound for the independence number α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≥3 is still an open problem. In this talk, we present the best polynomial for the case k=3.