The Independence Number of the Orthogonality Graph in Dimension $2^k$

Abstract

We determine the independence number of the orthogonality graph on $2^k$-dimensional hypercubes. This answers a question by Galliard from 2001 which is motivated by a problem in quantum information theory. Our method is a modification of a rank argument due to Frankl who showed the analogous result for $4p^k$-dimensional hypercubes, where $p$ is an odd prime.

3 pages, accepted by Combinatorica, fixed a minor typo spotted by Peter Sin

References in corpus (3)

• The cost of exactly simulating quantum entanglement with classical communication
• A note on the stability number of an orthogonality graph
• The Impossibility of Pseudo-Telepathy Without Quantum Entanglement

Cited by in corpus (1)

• Graph-theoretic approach to Bell experiments with low detection efficiency