Volume 18 (2022) Article 22 pp. 1-22

The (Generalized) Orthogonality Dimension of (Generalized) Kneser Graphs: Bounds and Applications

by Alexander Golovnev and Ishay Haviv

Received: October 1, 2021
Revised: August 21, 2022
Published: December 29, 2022

$ \newcommand{\R}{{\mathbb R}} \newcommand{\Fset}{\mathbb{F}} \newcommand{\NP}{\mathsf{NP}} $

The orthogonality dimension of a graph $G=(V,E)$ over a field $\Fset$ is the smallest integer $t$ for which there exists an assignment of a vector $u_v \in \Fset^t$ with $\langle u_v,u_v \rangle \neq 0$ to every vertex $v \in V$, such that $\langle u_v, u_{w} \rangle = 0$ whenever $v$ and $w$ 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 fixed integer $t$, it is $\NP$-hard to distinguish between the cases that the orthogonality dimension over $\R$ of an input graph is at most $t$ and at least $3t/2-c$. At the heart of the proof lies a geometric result, which might be of independent interest, on a generalization of the orthogonality dimension parameter (where vertices correspond to subspaces rather than vectors) for the family of Kneser graphs. The result is related to a long-standing graph-theoretic conjecture due to Stahl (J. Combin. Theory--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 triangle-free $n$-vertex graphs whose complement has orthogonality dimension over the binary field at most $n^{1-\delta}$ for some constant $\delta > 0$. Our results involve constructions from a family of generalized Kneser graphs (namely, threshold Kneser graphs) and are motivated by the rigidity approach to circuit lower bounds. We use them to answer questions raised by Codenotti, Pudlák, and Resta (Theoret. Comput. Sci., 2000), and in particular, to disprove their Odd Alternating Cycle Conjecture over every finite field.

---------------

A conference version of this paper appeared in the Proceedings of the 36th Computational Complexity Conference, 2021 (CCC'21).

DOI: 10.4086/toc.2022.v018a022

© 2022 Alexander Golovnev and Ishay Haviv
Licensed under a Creative Commons Attribution License (CC-BY)