Speaker
Description
Given a graph $G$ on $n$ vertices, $\mathcal{S}(G)$ is the set of symmetric $n\times n$ matrices with the same off-diagonal zero pattern as the adjacency matrix $A(G)$. We say that a graph $G$ has $q(G)=2$ if there is a matrix $M\in \mathcal{S}(G)$ with exactly $2$ distinct eigenvalues. This is equivalent to the existence of an orthogonal matrix $M\in\mathcal{S}(G)$. We are interested in understanding the graphs $G$ for which $q(G)=2$ (or equivalently, the zero-nonzero patterns of symmetric orthogonal matrices).
In this talk, we focus on the following conjecture: if the complement of $G$ has at most $n-3$ edges, then $q(G)=2$. This conjecture has been resolved for graphs with bipartite complement, and verified in some cases where the complement of $G$ is not bipartite. We report on this ongoing project.