Research

The graph on the right is the Paley graph on 17 vertices. The different colors denote a 17-cycle. Each edge of Paley 17 is in exactly one of the four 17-cycles. Paley 17 has many cool properties which make it a very interesting graph. It is a strongly regular graph, self-complimentary, arc-transitive, and pseudo random. It is the largest graph which doesn't have a 4-clique or its complement as induced subgraphs.

My most recent paper focuses on the Cvetkovic bound or inertia bound. What is being bound? An independent set in a graph $G$ is a subset of its vertices which are pair-wise non-adjacent. In other words a subset $B$ of the vertices is independent if there are no edges between any of the vertices in $B$. An example of an independent set in Paley 17 is the set $\{0,7,10\}$. The independence number of a graph $G$ is the size of the largest independent set and is denoted by $\alpha(G)$. Since Paley 17 doesn't have an independent set of size 4, its independence number is 3. Paley 17 is $\alpha$-critical because deleting any edge increases the independence number from 3 to 4.

What does inertia have to do with it? The inertia of a symmetric matrix $A$ is an ordered triple $(n_+,n_-,n_0)$ where $n_+$ and $n_-$ represent the number of positive and negative eigenvalues of $A$ and $n_0$ is the algebraic multiplicity of zero as an eigenvalue of $A$. What do the matrices have to do with the graph? We look at the weight matrices of the graph. A weight matrix $W$ of a graph $G$ is a symmetric matrix where $w_{ij}=0$ if $ij$ is not an edge of $G$. Weight matrices are similar to weighted adjacency matrices where the weight on an edge may be zero.

Inertia bound: For any weight matrix $W$ of a graph $G$ with inertia $(n_+,n_-,n_0)$, $$\alpha(G)\leq n_0 +\min\{n_+,n_-\}.$$

One proof of the inertia bound, relies on the interlacing theorem for symmetric matrices. The key idea is that an independent set in a graph corresponds to a zero principal submatrix in the weight matrix.

Whenever you are introduced to an inequality or bound, one of the first questions should be, "When is the bound tight?" In other words, when is the inequality an equality. Chris Godsil noted that all perfect graphs are inertia tight. It turned out to be quite difficult to find an example where the inertia bound was not tight. In fact, it was shown that all graphs on 10 or fewer vertices are inertia tight.

© 2016 John Sinkovic
Template design by Andreas Viklund