Chicago Journal of Theoretical Computer Science

Volume 2022

Article 2

Published by the Department of Computer Science, The University of Chicago.

Approximating the orthogonality dimension of graphs and hypergraphs

Ishay Haviv
The Academic College of Tel Aviv-Yaffo
Tel Aviv, Israel
ishayhav AT mta DOT ac DOT il

December 31, 2022


A $t$-dimensional orthogonal representation of a hypergraph is an assignment of nonzero vectors in $R^t$ to its vertices, such that every hyperedge contains two vertices whose vectors are orthogonal. The orthogonality dimension of a hypergraph $H$, denoted by ${\overline{\xi}}(H)$, is the smallest integer $t$ for which there exists a $t$-dimensional orthogonal representation of $H$. In this paper we study computational aspects of the orthogonality dimension of graphs and hypergraphs. We prove that for every $k \geq 4$, it is $NP$-hard (resp. quasi-$NP$-hard) to distinguish $n$-vertex $k$-uniform hypergraphs $H$ with ${\overline{\xi}}(H) \leq 2$ from those satisfying ${\overline{\xi}}(H) \geq \Omega(\log^\delta n)$ for some constant $\delta>0$ (resp. ${\overline{\xi}}(H) \geq \Omega(\log^{1-o(1)} n)$). For graphs, we relate the $NP$-hardness of approximating the orthogonality dimension to a variant of a long-standing conjecture of Stahl on the multichromatic numbers of Kneser graphs. We also consider the algorithmic problem in which given a graph $G$ with ${\overline{\xi}}(G) \leq 3$ the goal is to find an orthogonal representation of $G$ of as low dimension as possible, and provide a polynomial time approximation algorithm based on semidefinite programming.

Submitted November 14, 2020, revised December 22, 2022, published December 31, 2022.

DOI: 10.4086/cjtcs.2022.002

[] Volume 2022, Article 1
[back] Volume 2022 [back] Published articles
[CJCTS home]