Connections Between Matrix Spaces and Graphs

Youming Qiao develops connections between graphs and linear spaces of matrices. Tutte and Lovász linked graph perfect matchings to full-rank matrices; further correspondences relate independent sets to totally isotropic spaces, connectivity to orthogonal decompositions, and graph isomorphism to matrix-space isomorphism. These connections extend graph-theoretic questions and techniques to matrix spaces, including alternating paths, independence polynomials, Turán and Ramsey problems, expanders, and threshold phenomena. The methods connect to invariant theory, group theory, quantum information, and geometry. Based on joint work with Avi Wigderson, Yuval Wigderson, Gábor Ivanyos, Yinan Li, Chuanqi Zhang, and Markus Bläser.