4
$\begingroup$

Let us consider the complement of the Kneser graph with parameters $n$ and $n/4$. The vertex set of our graph $K$ is the set $\binom{[n]}{n/4}$ of $n/4$-subsets of $[n]$, and two vertices are joined by an undirected edge if and only if the two corresponding subsets of $[n]$ intersect.

The orthogonality dimension of $K$ is the smallest $d$ such that every vertex of $K$ can be mapped to a non-zero vector in $\mathbb{R}^d$ with the following property: every non-adjacent pair of vertices must be assigned orthogonal vectors. In other words, we want to assign vectors from $\mathbb{R}^d$ to $n/4$-subsets of $[n]$ such that every disjoint pair of sets have orthogonal vectors.

It is easy to see that the orthogonality dimension of $K$ is $\leq n/2+2$ by assigning to a set $A\subseteq[n]$ the standard basis vector $e_i$ with $i=\min\{\min(A),n/2+2\}$ (see, e.g., Section 3.3.2 in Matoušek). It was also recently shown by Ishay Haviv (Theorem 1.2 in Haviv) that this bound is tight.

The faithful orthogonality dimension (see, e.g., Lovász) of $K$ is the smallest $d$ such that every vertex of $K$ can be mapped to a non-zero vector in $\mathbb{R}^d$ such that two vectors are orthogonal if and only if the corresponding vertices are non-adjacent. The upper bound above does not apply in this setting (the lower bound still clearly holds). A trivial upper bound of $n$ can be achieved by assigning the $0/1$ indicator vector to every subset of size $n/4$.

My question is whether the faithful orthogonality dimension of $K$ is less than $n$.

$\endgroup$

0

You must log in to answer this question.