2026/07/07 by Tao Hu, Quanyu Tang · 1 voice
#math.CO
Let J≥ 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≥ 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≥2, 1≤ s≤ k-1, and n≥2k-s, we prove mr\mathbb F(J≥ s(n,k)) = \binomn-2(k-s)s for every infinite field \mathbb F, and mr+\mathbb R(J≥ s(n,k)) = \binomn-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≥ s(n,k) in the stated range, and recover the known minimum-rank formula for Johnson graphs.