#

### 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*
#### Abstract

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.

- The article:
**PDF** (364 KB)
- Source material: ZIP (72 KB)
**BibTeX** entry for this
article (282 bytes)

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

Volume 2022, Article 1

Volume 2022
Published articles