Abstract
The orthogonality dimension of a graph G = (V,E) over a field ? is the smallest integer t for which there exists an assignment of a vector u_v ∈ ?^t with ⟨ u_v,u_v ⟩ ≠ 0 to every vertex v ∈ V, such that ⟨ u_v, u_{v'} ⟩ = 0 whenever v and v' are adjacent vertices in G. The study of the orthogonality dimension of graphs is motivated by various applications in information theory and in theoretical computer science. The contribution of the present work is twofold.
First, we prove that there exists a constant c such that for every sufficiently large integer t, it is NPhard to decide whether the orthogonality dimension of an input graph over ℝ is at most t or at least 3t/2c. At the heart of the proof lies a geometric result, which might be of independent interest, on a generalization of the orthogonality dimension parameter for the family of Kneser graphs, analogously to a longstanding conjecture of Stahl (J. Comb. Theo. Ser. B, 1976).
Second, we study the smallest possible orthogonality dimension over finite fields of the complement of graphs that do not contain certain fixed subgraphs. In particular, we provide an explicit construction of trianglefree nvertex graphs whose complement has orthogonality dimension over the binary field at most n^{1δ} for some constant δ > 0. Our results involve constructions from the family of generalized Kneser graphs and they are motivated by the rigidity approach to circuit lower bounds. We use them to answer a couple of questions raised by Codenotti, Pudlák, and Resta (Theor. Comput. Sci., 2000), and in particular, to disprove their Odd Alternating Cycle Conjecture over every finite field.
BibTeX  Entry
@InProceedings{golovnev_et_al:LIPIcs.CCC.2021.8,
author = {Golovnev, Alexander and Haviv, Ishay},
title = {{The (Generalized) Orthogonality Dimension of (Generalized) Kneser Graphs: Bounds and Applications}},
booktitle = {36th Computational Complexity Conference (CCC 2021)},
pages = {8:18:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771931},
ISSN = {18688969},
year = {2021},
volume = {200},
editor = {Kabanets, Valentine},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14282},
URN = {urn:nbn:de:0030drops142829},
doi = {10.4230/LIPIcs.CCC.2021.8},
annote = {Keywords: Orthogonality dimension, minrank, rigidity, hardness of approximation, circuit complexity, chromatic number, Kneser graphs}
}
Keywords: 

Orthogonality dimension, minrank, rigidity, hardness of approximation, circuit complexity, chromatic number, Kneser graphs 
Collection: 

36th Computational Complexity Conference (CCC 2021) 
Issue Date: 

2021 
Date of publication: 

08.07.2021 