New bounds on the boxicity of Kneser graphs

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 Lichev [Discrete Mathematics 346(5):113333 (2023)] when $n\geq 3k+1$ and $k\ge 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\ge 2$, $t\ge 1$ and $n=2k+t$, $\operatorname{box}(K(2k+t,k)) \leq O( t^3\log(2k+t) ).$ In particular, for every $t=t(k)\ge1$ with $t^3\log k=o(k)$, $\operatorname{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$, $\operatorname{box}(K(2k+1,k))\le \frac{3\ln (2k+1)}{\ln\ln (2k+1)}$.

Authors

Publication Details

Journal
arXiv (Cornell University)
Published
2026-11-12
DOI
https://doi.org/10.48550/arxiv.2611.17183
Primary Topic
Advanced Graph Theory Research
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

New bounds on the boxicity of Kneser graphs

L. Sunil Chandran, Suraj Kumar Sahoo
arXiv (Cornell University)
Advanced Graph Theory Research
preprint

New bounds on the boxicity of Kneser graphs

L. Sunil Chandran, Suraj Kumar Sahoo
preprint en

Abstract

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 Lichev [Discrete Mathematics 346(5):113333 (2023)] when $n\geq 3k+1$ and $k\ge 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\ge 2$, $t\ge 1$ and $n=2k+t$, $\operatorname{box}(K(2k+t,k)) \leq O( t^3\log(2k+t) ).$ In particular, for every $t=t(k)\ge1$ with $t^3\log k=o(k)$, $\operatorname{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$, $\operatorname{box}(K(2k+1,k))\le \frac{3\ln (2k+1)}{\ln\ln (2k+1)}$.

arXiv (Cornell University)
Advanced Graph Theory Research
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon