The critical exponent: a novel graph invariant

A surprising result of FitzGerald and Horn (1977) shows that $A^{circ alpha} := (a_{ij}^alpha)$ is positive semidefinite (p.s.d.) for every entrywise nonnegative $n times n$ p.s.d. matrix $A = (a_{ij})$ if and only if $alpha$ is a positive integer or $alpha geq n-2$. Given a graph $G$, we consider the refined problem of characterizing the set $mathcal{H}_G$ of entrywise powers preserving positivity for matrices with a zero pattern encoded by $G$. Using algebraic and combinatorial methods, we study how the geometry of $G$ influences the set $mathcal{H}_G$. Our treatment provides new and exciting connections between combinatorics and analysis, and leads us to introduce and compute a new graph invariant called the critical exponent.