2018/11/28 by Ishay Haviv, Haviv, Ishay · 2 citations
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Graph theory and applications #Information Theory (cs.IT) #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1811.11488
openalex publication_date 2018/11/28 · openalex created_date 2022/08/01 · openalex updated_date 2026/07/28
An orthogonal representation of a graph is an assignment of nonzero real\nvectors to its vertices such that distinct non-adjacent vertices are assigned\nto orthogonal vectors. We prove general lower bounds on the dimension of\northogonal representations of graphs using the Borsuk-Ulam theorem from\nalgebraic topology. Our bounds strengthen the Kneser conjecture, proved by\nLov 'asz in 1978, and some of its extensions due to B 'ar 'any, Schrijver,\nDol'nikov, and Kriz. As applications, we determine the integrality gap of\nfractional upper bounds on the Shannon capacity of graphs and the quantum\none-round communication complexity of certain promise equality problems.\n