License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2020.8
URN: urn:nbn:de:0030-drops-116932
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11693/
Bei, Xiaohui ;
Chen, Shiteng ;
Guan, Ji ;
Qiao, Youming ;
Sun, Xiaoming
From Independent Sets and Vertex Colorings to Isotropic Spaces and Isotropic Decompositions: Another Bridge Between Graphs and Alternating Matrix Spaces
Abstract
In the 1970’s, Lovász built a bridge between graphs and alternating matrix spaces, in the context of perfect matchings (FCT 1979). A similar connection between bipartite graphs and matrix spaces plays a key role in the recent resolutions of the non-commutative rank problem (Garg-Gurvits-Oliveira-Wigderson, FOCS 2016; Ivanyos-Qiao-Subrahmanyam, ITCS 2017). In this paper, we lay the foundation for another bridge between graphs and alternating matrix spaces, in the context of independent sets and vertex colorings. The corresponding structures in alternating matrix spaces are isotropic spaces and isotropic decompositions, both useful structures in group theory and manifold theory.
We first show that the maximum independent set problem and the vertex c-coloring problem reduce to the maximum isotropic space problem and the isotropic c-decomposition problem, respectively. Next, we show that several topics and results about independent sets and vertex colorings have natural correspondences for isotropic spaces and decompositions. These include algorithmic problems, such as the maximum independent set problem for bipartite graphs, and exact exponential-time algorithms for the chromatic number, as well as mathematical questions, such as the number of maximal independent sets, and the relation between the maximum degree and the chromatic number. These connections lead to new interactions between graph theory and algebra. Some results have concrete applications to group theory and manifold theory, and we initiate a variant of these structures in the context of quantum information theory. Finally, we propose several open questions for further exploration.
(Dedicated to the memory of Ker-I Ko)
BibTeX - Entry
@InProceedings{bei_et_al:LIPIcs:2020:11693,
author = {Xiaohui Bei and Shiteng Chen and Ji Guan and Youming Qiao and Xiaoming Sun},
title = {{From Independent Sets and Vertex Colorings to Isotropic Spaces and Isotropic Decompositions: Another Bridge Between Graphs and Alternating Matrix Spaces}},
booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
pages = {8:1--8:48},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-134-4},
ISSN = {1868-8969},
year = {2020},
volume = {151},
editor = {Thomas Vidick},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11693},
URN = {urn:nbn:de:0030-drops-116932},
doi = {10.4230/LIPIcs.ITCS.2020.8},
annote = {Keywords: independent set, vertex coloring, graphs, matrix spaces, isotropic subspace}
}
|
Keywords: |
|
independent set, vertex coloring, graphs, matrix spaces, isotropic subspace |
|
Collection: |
|
11th Innovations in Theoretical Computer Science Conference (ITCS 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
06.01.2020 |
