{"id":"arxiv/2605.21015","url":"https://arxiv.org/abs/2605.21015","tags":["math.CO","cs.DS"],"score":0,"title":"Treewidth of the $n \\times n$ toroidal grid","domain":"math.CO","source":"arxiv","authors":["Tatsuya Gima","Hiraku Morimoto","Yuto Okada","Yota Otachi"],"reviews":0,"subject":"math.CO","summary":"In this paper, we show that the treewidth of the $n \\times n$ toroidal grid is $2n-1$ for all $n \\ge 5$. This closes the gap between the previously known upper bound of $2n-1$ (Ellis and Warren, DAM 2008) and the lower bound of $2n-2$ (Kiyomi, Okamoto, and Otachi, DAM 2016). To establish the matching lower bound, we construct a bramble of maximum order by utilizing maximum components obtained after removing $2n-1$ vertices. Our construction relies on the vertex-isoperimetric properties of the infinite grid to establish tight lower bounds on neighborhood sizes, combined with a careful…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-05-20","reactions":{}}