H. Tracy Hall visits ISU to offer first public presentation of Proof of Maehara's 20-year-old Conjecture

H. Tracy Hall, visiting scholar with Brigham Young University, visited campus in October to offer the first public presenation proving Maehara's 20-year-old conjecture.

This particular presentation was a few years in the making.

An AIM workshop focused on minimim rank back in 2006 organized by Leslie Hogben, Richard Brualdi and Bryan Shader introduced a number of problems, including the Delta conjecture.

Maehara's Delta conjecture appeared in L. Lovasz, M. Saks and A. Schrijver. Orthogonal representations and connectivity of graphs. Linear Algebra and its Applications 114/115: 439--454, 1989.

Workshop attendee Wayne Barrett took the problems back to BYU where colleague Tracy Hall found them facinating; his interest led Hogben to invite him to participate in AIM SQuaRE, a small research group the met over the next three years. Visits to ISU to work on similar research followed, and in 2009 Hall spent two weeks on campus as a research visitor.

Abstract:

A faithful orthogonal representation of a simple graph G assigns a vector to each vertex in such a way that vectors are orthogonal exactly when vertices are nonadjacent. The minimum dimension for which such a representation exists is another way of stating the minimum semidefi nite rank of G. Maehara conjectured in 1987 that a faithful orthogonal representation in dimension |G | - (G) should exist, where (G) is the minimum degree of the graph. Related conjectures have more recently surfaced in combinatorial matrix theory, some of them involving a matrix condition called the Strong Arnol’d Hypothesis. I will present a construction that implies Maehara’s Conjecture and its generalizations.

Call a symmetric matrix M upper-generic if, in each column separately, the diagonal entry is non-zero and the zeros above the diagonal belong to a linearly independent set of rows of M. (Permutation similar to upper-generic strictly implies Strong Arnol'd.) Call a vertex ordering of a graph G greedy when at each step it adds as many induced edges as locally possible, and define the greedegree of G to be the maximum, over greedy orderings of G, of the degree of the final vertex. The construction produces a faithful orthogonal representation of G, in dimension |G| minus the greedegree of G, whose Gram matrix is upper-generic.