Approximating the Orthogonality Dimension of Graphs and Hypergraphs

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.