Title: The smallest graphs for which the inertia bound is not tight
Abstract: Given a simple graph G, a weight matrix W of G is a symmetric matrix such that the ij-th entry of W is zero whenever ij is not an edge of G. The independence number of a graph is the maximum size of a set of pairwise non-adjacent vertices. The inertia bound, or Cvetkovic bound, states that the independence number of a graph is bounded above by the minimum of the number of nonpositive eigenvalues and the number of nonnegative eigenvalues of any weight matrix W of G. The inertia bound is known to be tight for perfect graphs and graphs on 10 or fewer vertices. We will exhibit two graphs on 11 vertices for which the bound is not tight.