Algebraic Graph Theory Seminar - Lord Kavi

Monday, July 5, 2021 11:30 am - 11:30 am EDT (GMT -04:00)

Title: The $k$-Independence Number

Speaker: Lord Kavi
Affiliation: University of Ottawa
Zoom: Contact Soffia Arnadottir


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.$