Mathematics Colloquium: Combinatorial matrix theory, the Delta Theorem, and orthogonal representations

Speaker: H. Tracy Hall, Hall Labs, LLC

Title: Combinatorial matrix theory, the Delta Theorem, and orthogonal representations

Abstract:  A real symmetric matrix has an all-real spectrum, and the nullity of the matrix is the same as the multiplicity of zero as an eigenvalue.  A central problem of combinatorial matrix theory called the Inverse Eigenvalue Problem for a Graph (IEP-G) asks for every possible spectrum of such a matrix when all that is known is the pattern of non-zero off-diagonal entries, as described by a graph (or network) $G$.  A major subproblem asks only for the maximum possible nullity, denoted $\mathrm{M}(G).$
   
The question is a difficult one and the subject of ongoing active investigation by a thriving and inclusive research community.  It has inspired graph theory questions related to upper or lower combinatorial bounds, including for example a conjectured inequality, called the ``Delta Conjecture'', of a lower bound
    \[
    \delta(G) \le \mathrm{M}(G),
    \]
    where $\delta(G)$ is the smallest degree of any vertex of $G$.
I will present a sketch of how I was able to prove the Delta Theorem using a geometric construction called an orthogonal graph representation, a type of vertex ordering called a Maximum Cardinality Search (MCS) or ``greedy'' ordering, and a construction that I call a ``hanging garden diagram''.

Time:  Friday, February 6, 3:30pm – 4:30pm

Place:  Exploratory Hall, room 4106 or Zoom