Answers are grounded in this paper and cite their sources.
For a graph $G=(V,E)$, the boxicity box(G) is the least integer d such that G is the intersection graph of axis-parallel boxes in Rᵈ. The Kneser graph $K(n,k)$ is the graph whose vertex set corresponds to the family of k sized subsets of an n sized ground set, and a pair of vertices are adjacent if and only if the corresponding sets are disjoint. In this short paper, we provide new bounds for the boxicity of $K(n,k)$. We first show that for k≥ 2 and n≥ 2k+1, box(K(n,k))≥ n-2k, thereby improving the lower bounds of Caoduro and Lichev [Discrete Mathematics 346(5):113333 (2023)] when n≥ 3k+1 and k≥ 3. The proof of this result uses the topological method and follows a strategy similar to Greene's proof of the Kneser's conjecture on the chromatic number of $K(n,k)$. We also show that for k≥ 2, t≥ 1 and $n=2k+t$, box(K(2k+t,k)) ≤ O( t³log(2k+t) ). In particular, for every t=t(k)≥1 with t³log k=o(k), box(K(2k+t,k))=o(k). This is the first upper bound on the boxicity of $K(n,k)$ that is sublinear in n. We also show that for large enough k, box(K(2k+1,k))≤ 3ln (2k+1)/lnln (2k+1).
No takes yet. Share an insight, caveat, or question.
Chandran et al. (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: