Minimum-rank parameters of complements of threshold Kneser graphs

Abstract

Let $J_{\ge s}(n,k)$ be the graph whose vertices are the $k$-subsets of $[n]$, with two distinct vertices adjacent whenever their intersection has size at least $s$. Equivalently, $J_{\ge s}(n,k)$ is the complement of a threshold Kneser graph. We determine both the symmetric minimum rank over an arbitrary infinite field and the real positive semidefinite minimum rank of this family. Specifically, for $k\ge 2$, $1\le s\le k-1$, and $n\ge 2k-s$, we prove $${\mathrm{mr}}^{\mathbb{F}}\left(J_{\ge s}(n,k)\right)=\left(\genfrac{}{}{0ex}{}{n-2(k-s)}{s}\right)$$ for every infinite field $\mathbb{F}$, and $${\mathrm{mr}}_{+}^{\mathbb{R}}\left(J_{\ge s}(n,k)\right)=\left(\genfrac{}{}{0ex}{}{n-2(k-s)}{s}\right).$$ The lower bound follows from a diagonal submatrix indexed by two carefully chosen families of $k$-subsets. For the upper bound, we construct a symmetric matrix using an exterior power of a bilinear form, a Lagrange interpolation identity, and a generic nonvanishing argument. Over $\mathbb{R}$, an interlacing choice of parameters makes the bilinear form positive definite and yields a positive semidefinite matrix attaining the required upper bound. As consequences, we answer a question from an American Institute of Mathematics workshop, determine the real faithful orthogonality dimension of all graphs $J_{\ge s}(n,k)$ in the stated range, and recover the known minimum-rank formula for Johnson graphs.

arXiv comment12 pages. v2: Substantially revised and expanded. The previous result for the case $s=1$ is extended to all thresholds $1\le s\le k-1$, and the exact real positive semidefinite minimum rank is also determined. Title changed