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\ge2$, $1\le s\le k-1$, and $n\ge2k-s$, we prove $$ \operatorname{mr}^{\mathbb F}\left(J_{\ge s}(n,k)\right) = \binom{n-2(k-s)}{s} $$ for every infinite field $\mathbb F$, and $$ \operatorname{mr}_{+}^{\mathbb R}\left(J_{\ge s}(n,k)\right) = \binom{n-2(k-s)}{s}. $$ 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.

Disclosure

“or the submitted work. Competing interests. The authors have no relevant financial or non-financial interests to disclose. Data availability. No datasets were generated or analyzed during the current study. Use of generative AI. We used ChatGPT to generate exploratory code for assessing the plausibility of conjectured statements and to help polish the language of proof drafts written by the authors. All mathematical claims, calculations, and proofs were independently verified by”

PDF page 11

Classification

Rewriting existing author-written text

Multiplier

4

Verified

2026-08-24T00:34:12.480Z

Structural counts