Seminar Details
Connections Between Graphs and Matrix Spaces
- Start Date: April 7, 2025
- Event Start Time: 2:00 PM
- Event End Time: 3:00 PM
- Seminar Series: Rutgers Discrete Mathematics Seminar
- Presenter(s): Youming Qiao - University of Technology, Sydney
- Event Location: Conference Room 705 | Rutgers University | Hill Center | 110 Frelinghuysen Rd
- Event Additional Info: <p>See: <a href="https://sites.google.com/view/rutgersdmseminar">https://sites.google.com/view/rutgersdmseminar</a></p>
- Presentation Type: Stand Alone Presentation
- 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.