文章基本信息

标题：On Minrank and the Lovász Theta Function
本地全文：下载
作者：Ishay Haviv
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2018
卷号：116
页码：1-15
DOI：10.4230/LIPIcs.APPROX-RANDOM.2018.13
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Two classical upper bounds on the Shannon capacity of graphs are the theta-function due to Lovász and the minrank parameter due to Haemers. We provide several explicit constructions of n-vertex graphs with a constant theta-function and minrank at least n^delta for a constant delta>0 (over various prime order fields). This implies a limitation on the theta-function-based algorithmic approach to approximating the minrank parameter of graphs. The proofs involve linear spaces of multivariate polynomials and the method of higher incidence matrices.
关键词：Minrank; Theta Function; Shannon capacity; Multivariate polynomials; Higher incidence matrices