Séminaire Lotharingien de Combinatoire, 78B.62 (2017), 12 pp.

Dominique Guillot, Apoorva Khare and Bala Rajaratnam

The Critical Exponent: a Novel Graph Invariant

Abstract. A surprising result of FitzGerald and Horn (1977) shows that Ao α := (aijα) is positive semidefinite (p.s.d.) for every entrywise nonnegative n x n p.s.d. matrix A = (aij) if and only if α is a positive integer or α >= n-2. Given a graph G, we consider the refined problem of characterizing the set HG 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 HG. 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.


Received: November 14, 2016. Accepted: February 17, 2017. Final version: April 1, 2017.

The following versions are available: