2019/04/08 by Xiaohui Bei, Shiteng Chen, Bei, Xiaohui +7 · 3 citations
Computer Science · Mathematics · #Graph Labeling and Dimension Problems #Advanced Graph Theory Research #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.1904.03950
In the 1970's, Lov 'asz built a bridge between graphs and alternating matrix\nspaces, in the context of perfect matchings (FCT 1979). A similar connection\nbetween bipartite graphs and matrix spaces plays a key role in the recent\nresolutions of the non-commutative rank problem\n(Garg-Gurvits-Oliveira-Wigderson, FOCS 2016; Ivanyos-Qiao-Subrahmanyam, ITCS\n2017). In this paper, we lay the foundation for another bridge between graphs\nand alternating matrix spaces, in the context of independent sets and vertex\ncolorings. The corresponding structures in alternating matrix spaces are\nisotropic spaces and isotropic decompositions, both useful structures in group\ntheory and manifold theory.\n We first show that the maximum independent set problem and the vertex\nc-coloring problem reduce to the maximum isotropic space problem and the\nisotropic c-decomposition problem, respectively. Next, we show that several\ntopics and results about independent sets and vertex colorings have natural\ncorrespondences for isotropic spaces and decompositions. These include\nalgorithmic problems, such as the maximum independent set problem for bipartite\ngraphs, and exact exponential-time algorithms for the chromatic number, as well\nas mathematical questions, such as the number of maximal independent sets, and\nthe relation between the maximum degree and the chromatic number. These\nconnections lead to new interactions between graph theory and algebra. Some\nresults have concrete applications to group theory and manifold theory, and we\ninitiate a variant of these structures in the context of quantum information\ntheory. Finally, we propose several open questions for further exploration.\n This paper is dedicated to the memory of Ker-I Ko.\n