Theory of Computing
-------------------
Title : The (Generalized) Orthogonality Dimension of (Generalized) Kneser Graphs: Bounds and Applications
Authors : Alexander Golovnev and Ishay Haviv
Volume : 18
Number : 22
Pages : 1-22
URL : https://theoryofcomputing.org/articles/v018a022
Abstract
--------
The _orthogonality dimension_ of a graph $G=(V,E)$ over a field
$\F$ is the smallest integer $t$ for which there exists an
assignment of a vector $u_v \in \F^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, Pudlak, 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).