CSpace  > 中国科学院计算技术研究所期刊论文  > 英文
FROM INDEPENDENT SETS AND VERTEX COLORINGS TO ISOTROPIC SPACES AND ISOTROPIC DECOMPOSITIONS: ANOTHER BRIDGE BETWEEN GRAPHS AND ALTERNATING MATRIX SPACES
Bei, Xiaohui1; Chen, Shiteng2; Guan, Ji2; Qiao, Youming3; Sun, Xiaoming4,5
2021
发表期刊SIAM JOURNAL ON COMPUTING
ISSN0097-5397
卷号50期号:3页码:924-971
摘要In the 1970s, Lovasz built a bridge between graphs and alternating matrix spaces, in the context of perfect matchings [Proceedings of FCT, 1979, pp. 565-574]. A similar connection between bipartite graphs and matrix spaces plays a key role in the recent resolutions of the noncommutative rank problem [A. Garg et al., Proceedings of FOCS, 2016, pp. 109-117; G. Ivanyos, Y. Qiao, and K. V. Subrahmanyam, Comput. Complexity, 26 (2017), pp. 717-763]. 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.
关键词independent set vertex coloring alternating matrix spaces isotropic space isotropic decomposition exact exponential algorithms
DOI10.1137/19M1299128
收录类别SCI
语种英语
资助项目National Key R\&D Program of China[2018YFA0306701] ; National Natural Science Foundation of China[61832015] ; National Natural Science Foundation of China[61702489] ; National Natural Science Foundation of China[61832003] ; Key Research Program of Frontier Sciences, CAS[QYZDJ-SSW-SYS003] ; Australian Research Council[DE150100720] ; Australian Research Council[DP200100950] ; Strategic Priority Research Program of Chinese Academy of Sciences[XDB28000000] ; K. C. Wong Education Foundation
WOS研究方向Computer Science ; Mathematics
WOS类目Computer Science, Theory & Methods ; Mathematics, Applied
WOS记录号WOS:000674143400019
出版者SIAM PUBLICATIONS
引用统计
被引频次:6[WOS]   [WOS记录]     [WOS相关记录]
文献类型期刊论文
条目标识符http://119.78.100.204/handle/2XEOYT63/17325
专题中国科学院计算技术研究所期刊论文_英文
通讯作者Bei, Xiaohui
作者单位1.Nanyang Technol Univ, Sch Phys & Math Sci, Singapore 637371, Singapore
2.Chinese Acad Sci, Inst Software, State Key Lab Comp Sci, Beijing, Peoples R China
3.Univ Technol Sydney, Ctr Quantum Software & Informat, Parramatta, NSW 2150, Australia
4.Chinese Acad Sci, Inst Comp Technol, Beijing, Peoples R China
5.Univ Chinese Acad Sci, Beijing, Peoples R China
推荐引用方式
GB/T 7714
Bei, Xiaohui,Chen, Shiteng,Guan, Ji,et al. FROM INDEPENDENT SETS AND VERTEX COLORINGS TO ISOTROPIC SPACES AND ISOTROPIC DECOMPOSITIONS: ANOTHER BRIDGE BETWEEN GRAPHS AND ALTERNATING MATRIX SPACES[J]. SIAM JOURNAL ON COMPUTING,2021,50(3):924-971.
APA Bei, Xiaohui,Chen, Shiteng,Guan, Ji,Qiao, Youming,&Sun, Xiaoming.(2021).FROM INDEPENDENT SETS AND VERTEX COLORINGS TO ISOTROPIC SPACES AND ISOTROPIC DECOMPOSITIONS: ANOTHER BRIDGE BETWEEN GRAPHS AND ALTERNATING MATRIX SPACES.SIAM JOURNAL ON COMPUTING,50(3),924-971.
MLA Bei, Xiaohui,et al."FROM INDEPENDENT SETS AND VERTEX COLORINGS TO ISOTROPIC SPACES AND ISOTROPIC DECOMPOSITIONS: ANOTHER BRIDGE BETWEEN GRAPHS AND ALTERNATING MATRIX SPACES".SIAM JOURNAL ON COMPUTING 50.3(2021):924-971.
条目包含的文件
条目无相关文件。
个性服务
推荐该条目
保存到收藏夹
查看访问统计
导出为Endnote文件
谷歌学术
谷歌学术中相似的文章
[Bei, Xiaohui]的文章
[Chen, Shiteng]的文章
[Guan, Ji]的文章
百度学术
百度学术中相似的文章
[Bei, Xiaohui]的文章
[Chen, Shiteng]的文章
[Guan, Ji]的文章
必应学术
必应学术中相似的文章
[Bei, Xiaohui]的文章
[Chen, Shiteng]的文章
[Guan, Ji]的文章
相关权益政策
暂无数据
收藏/分享
所有评论 (0)
暂无评论
 

除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。