Connections Between Matrix Spaces and Graphs

In 2021 Avi gave a talk titled “Linear spaces of matrices” (see https://www.youtube.com/watch?v=H1H0OkZfZXw). As shown there, the study of linear spaces of matrices (which we call matrix spaces) arises naturally (and independently) in many different areas of mathematics and computer science.

In this talk we examine connections between graphs and matrix spaces. To begin, certain matrix spaces arise naturally from graphs, a construction that dates back to the works of Tutte 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 such 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 connections lead us to wonder whether graph-theoretic questions and techniques can be extended to matrix spaces. We demonstrate that this is possible in many cases—sometimes in hindsight—such as alternating paths, independence polynomials, Turán and Ramsey type questions, expanders (spectral or combinatorial), and threshold phenomena. Moreover, 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.