Youming Qiao, University of Technology, Sydney

Abstract

In this talk, we examine some connections between graphs and matrix spaces (linear spaces of matrices). To begin, certain matrix spaces arise naturally from graphs, a construction that dates to the works of Tutte, Edmonds, and Lovász on perfect matchings. Their works established a link between perfect matchings and full-rank matrices. Extending from there, we first show more correspondences between graph structures and matrix space structures, such as independent sets and totally-isotropic spaces, graph connectivity and orthogonal decompositions, and isomorphism notions.

These correspondences between structures also translate to graph-inspired questions and techniques for matrix spaces. We will give a sample of them, such as alternating paths, independence polynomials, Turán and Ramsey type questions, (as time permits :)) expanders (spectral or combinatorial), and threshold phenomena. Many of these techniques and results are motivated by and find applications in other areas, such as invariant theory, group theory, quantum information, and geometry.

Based on joint works with Avi Wigderson, Yuval Wigderson, Gábor Ivanyos, Yinan Li, Chuanqi Zhang, Markus Bläser.

See: https://sites.google.com/view/rutgersdmseminar