# Approximating the Orthogonality Dimension of Graphs and Hypergraphs

arXiv: https://arxiv.org/abs/1906.05005 · HTML: https://mlsanity.com/paper/1906.05005/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Jun 2019.

## Built on by (most cited first, 1 of 1)

- [New Hardness Results for Low-Rank Matrix Completion](https://mlsanity.com/paper/2506.18440/) (2025)

## Abstract (arXiv)

A t-dimensional orthogonal representation of a hypergraph is an assignment of nonzero vectors in ℝt to its vertices, such that every hyperedge contains two vertices whose vectors are orthogonal. The orthogonality dimension of a hypergraph H, denoted by overlinexi(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 ≥ 4, it is mathsfNP-hard (resp. quasi-mathsfNP-hard) to distinguish n-vertex k-uniform hypergraphs H with overlinexi(H) ≤ 2 from those satisfying overlinexi(H) ≥ Omega(logδ n) for some constant δ>0 (resp. overlinexi(H) ≥ Omega(log1-o(1) n)). For graphs, we relate the mathsfNP-hardness of approximating the orthogonality dimension to a variant of a long-standing conjecture of Stahl. We also consider the algorithmic problem in which given a graph G with overlinexi(G) ≤ 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.