{"id":"arxiv/2611.17183","url":"https://arxiv.org/abs/2611.17183","tags":["math.CO","cs.DM"],"score":0,"title":"New bounds on the boxicity of Kneser graphs","domain":"math.CO","source":"arxiv","authors":["L. Sunil Chandran","Suraj Kumar Sahoo"],"reviews":0,"subject":"math.CO","summary":"For a graph $G=(V,E)$, the boxicity $\\operatorname{box}(G)$ is the least integer $d$ such that $G$ is the intersection graph of axis-parallel boxes in $\\mathbb{R}^d$. 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\\ge 2$ and $n\\ge 2k+1$, $\\operatorname{box}(K(n,k))\\ge n-2k$, thereby improving the lower bounds of Caoduro and…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-11-12","reactions":{}}