pith. sign in

arxiv: 2605.21015 · v1 · pith:SI5UJD45new · submitted 2026-05-20 · 🧮 math.CO · cs.DS

Treewidth of the n times n toroidal grid

Tatsuya Gima , Hiraku Morimoto , Yuto Okada , Yota Otachi This is my paper

Pith reviewed 2026-05-21 03:41 UTC · model grok-4.3

classification 🧮 math.CO cs.DS
keywords treewidthtoroidal gridbramblegrid graphisoperimetric inequalitygraph decompositioncombinatorics
0
0 comments X

The pith

The n by n toroidal grid has treewidth exactly 2n-1 for all n at least 5.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper proves that the treewidth of the n by n toroidal grid graph equals 2n minus 1 for every n of size 5 or larger. It closes the remaining gap by raising the lower bound from 2n minus 2 to match the known upper bound of 2n minus 1. The proof builds a bramble of order 2n from the largest connected pieces left after any deletion of 2n minus 1 vertices. Treewidth controls the speed of many exact algorithms on graphs, so the exact number lets researchers replace exponential-in-2n bounds with precise statements for this family of wrapped grids.

Core claim

We show that the treewidth of the n × n toroidal grid is 2n-1 for all n ≥ 5. 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 analysis of balls of radius n/2-1 and their boundaries to overcome structural obstructions when n is even.

What carries the argument

Bramble of order 2n formed from the largest remaining connected components after the removal of any 2n-1 vertices, using vertex-isoperimetric bounds from the infinite grid and boundary analysis on balls of radius n/2-1.

If this is right

  • Treewidth-dependent algorithms on toroidal grids now have a tight parameter of 2n-1 rather than an interval.
  • The minimum width of any tree decomposition of the graph is exactly 2n-1.
  • The result extends the known treewidth formula from open grids and cylinders to the fully periodic toroidal case for sufficiently large n.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same isoperimetric-plus-ball analysis may give exact treewidths for higher-dimensional toroidal grids.
  • Comparison with the treewidth of planar n by n grids (which is n) becomes sharper once the toroidal case is settled.
  • For n below 5 the statement is excluded and direct verification remains necessary.

Load-bearing premise

Removing any 2n-1 vertices from the n by n torus always leaves at least one connected component large enough that the collection of all such components forms a bramble of order 2n.

What would settle it

An explicit set of 2n-1 vertices in the n by n torus for some n at least 5 whose removal leaves every connected component of size smaller than 2n would show that no bramble of order 2n exists.

Figures

Figures reproduced from arXiv: 2605.21015 by Hiraku Morimoto, Tatsuya Gima, Yota Otachi, Yuto Okada.

Figure 1
Figure 1. Figure 1: (Left) Tn with n = 6. (Center) We often draw Tn without edges. (Right) A row and a column. and NG[v] = {v} ∪ NG(v). For S ⊆ V , let NG(S) = S v∈S NG(v)  \ S and NG[S] = S ∪ NG(S). By distG(u, v), we denote the distance between u and v in G; that is, distG(u, v) is the number of edges in a shortest u–v path in G. 3. Lower bounds on neighborhood size via infinite grids In this section, we present lower boun… view at source ↗
Figure 2
Figure 2. Figure 2: There are 4m internally vertex-disjoint paths between R \ {v} and C \ {v}. Lemma 4.2. If S ⊆ V (T2m+1) is connected and |S| = 2m2 , then |NT2m+1 (S)| ≥ 4m + 1. Proof. Let r and c be the numbers of rows and columns of T2m+1 that S intersects. If r ≤ 2m − 1 and c ≤ 2m − 1, then Lemmas 3.1 and 3.3 with |S| = 2m2 imply that |NT2m+1 (S)| ≥ β∞(|S|) ≥ 4m + 2. By symmetry, we may assume that r ≥ 2m. We first consi… view at source ↗
Figure 3
Figure 3. Figure 3: (left) and (center), the crossed vertices form a set J of 4m − 1 (= 11) vertices and the black vertices form the unique maximum component of T2m − J [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: The (m − 1)-balls centered at c and c ′ = c + (m, m) in two different drawings. Lemma 5.3. Let m ≥ 3 and let B be the (m − 1)-ball centered at c ∈ V (T2m). For every v ∈ B, the induced subgraph T2m[B \ {v}] has a unique maximum component D. This component D satisfies |V (D)| ≥ 2m2 − 2m − 1 and NT2m(V (D)) = NT2m(B) ∪ {v}. Proof. Let A = {c + (i, j) | (i, j) ∈ {(m − 2, 0),(−(m − 2), 0),(0, m − 2),(0, −(m − … view at source ↗
Figure 5
Figure 5. Figure 5: Internally vertex-disjoint paths between [PITH_FULL_IMAGE:figures/full_fig_p010_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: A small separator M has to be an m-boundary set. 5.2. Constructing a bramble of T2m Now we are ready to construct a bramble of T2m with order 4m for 2m ≥ 6. We say that a set J ⊆ V (T2m) is m-boundary-free if it contains no m-boundary set as a subset. • For each m-boundary-free set J ⊆ V (T2m) of size 4m−1, we set HJ to be a maximum component of T2m − J. If there are two or more maximum components, then we… view at source ↗
Figure 7
Figure 7. Figure 7: J = {v, v + (m, m)} ∪ {v + (d, d), v + (d, −d), v + (−d, d), v + (−d, −d) | d ∈ [m − 1]}. By Lemmas 5.3 and 5.6, we have the following lower bounds on the size of elements of E. Observation 5.7. Each element of E1 has size at least 2m2 − 2m and each element of E2 has size at least 2m2 − 2m − 1. Now we are ready to complete the proof. Lemma 5.8. Any two elements of E touch. Proof. Let X, Y ∈ E. Suppose to t… view at source ↗
read the original abstract

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 analysis of balls of radius $n/2-1$ and their boundaries to overcome structural obstructions when $n$ is even.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The paper proves that the treewidth of the n×n toroidal grid is exactly 2n−1 for every integer n≥5. The upper bound 2n−1 was already known; the new contribution is a matching lower bound obtained by exhibiting a bramble of order 2n. The construction considers, for each set S of 2n−1 vertices, a largest connected component C_S in the toroidal grid minus S and shows that the collection {C_S} forms a bramble of order 2n. The argument transfers vertex-isoperimetric inequalities from the infinite grid and performs a separate boundary analysis of balls of radius n/2−1 to handle the even-n case.

Significance. Exact treewidth of toroidal grids is a basic structural question whose resolution sharpens the complexity of many problems on these graphs. The proof combines standard bramble techniques with isoperimetric estimates and supplies an explicit construction that may extend to other toroidal or vertex-transitive graphs.

major comments (1)
  1. [Bramble construction and even-n analysis (around the discussion of balls of radius n/2−1)] The central lower-bound argument (bramble of order 2n) relies on showing that every component C_S after deletion of 2n−1 vertices has neighborhood size at least 2n. While the infinite-grid isoperimetric inequality is used, the toroidal geometry for even n introduces diametrically opposite flat boundaries in radius-(n/2−1) balls. The manuscript states that a careful boundary analysis overcomes these obstructions, but the precise counting that guarantees |N(C_S)|≥2n for every such S must be verified; a single counter-example S of size 2n−1 that leaves only components with smaller neighborhoods would drop the bramble order to 2n−1 and falsify the claimed treewidth.
minor comments (2)
  1. [Preliminaries] Define the toroidal distance and the precise notion of a wrapped ball of radius r before invoking the radius-(n/2−1) estimates.
  2. [Figures and tables] Add a short table or diagram contrasting the infinite-grid and toroidal boundary sizes for even and odd n to make the even-case argument easier to follow.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and for raising this important point about the even-n boundary analysis. We address the concern directly below and will revise the manuscript to strengthen the exposition of the counting argument.

read point-by-point responses

  1. Referee: The central lower-bound argument (bramble of order 2n) relies on showing that every component C_S after deletion of 2n−1 vertices has neighborhood size at least 2n. While the infinite-grid isoperimetric inequality is used, the toroidal geometry for even n introduces diametrically opposite flat boundaries in radius-(n/2−1) balls. The manuscript states that a careful boundary analysis overcomes these obstructions, but the precise counting that guarantees |N(C_S)|≥2n for every such S must be verified; a single counter-example S of size 2n−1 that leaves only components with smaller neighborhoods would drop the bramble order to 2n−1 and falsify the claimed treewidth.

    Authors: We agree that explicit verification of the neighborhood lower bound is essential. The argument proceeds by cases on the size and location of the largest component C_S. When C_S is not contained in a radius-(n/2−1) ball, the infinite-grid isoperimetric inequality directly yields |N(C_S)| ≥ 2n. When C_S lies inside such a ball, the two diametrically opposite flat boundaries cannot both be fully covered by a set S of only 2n−1 vertices while leaving C_S disconnected from the rest of the torus: covering both flats requires at least 2n vertices (n per flat), and any attempt to use fewer vertices on one flat forces the component to connect around the torus or to acquire additional boundary vertices on the curved sides. We have checked all possible placements of S relative to these balls and confirmed no counter-example exists. To address the referee’s request for verification, we will add a dedicated lemma that enumerates the admissible boundary configurations for even n and proves |N(C_S)| ≥ 2n in each case. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation uses external isoperimetric facts

full rationale

The paper's lower bound is obtained by an explicit bramble construction: for every set S of 2n-1 vertices, select a maximum-order component C_S in the toroidal grid minus S, then verify that the family of all such C_S forms a bramble of order 2n. This argument invokes vertex-isoperimetric inequalities of the infinite grid (an independent combinatorial fact) together with a direct case analysis of balls of radius n/2-1 on the torus. Neither step is defined in terms of the target treewidth value, nor is any parameter fitted to the toroidal data and then re-used as a prediction. The cited upper bound (Ellis-Warren 2008) and prior lower bound (Kiyomi-Okamoto-Otachi 2016) are external; the present construction does not reduce to them by definition or by a self-citation chain. The derivation is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on standard graph theory background and domain-specific properties of grids; no free parameters or new entities are introduced.

axioms (1)
  • domain assumption Vertex-isoperimetric properties of the infinite grid establish tight lower bounds on neighborhood sizes
    Invoked to bound component sizes after vertex removal in the toroidal setting.

pith-pipeline@v0.9.0 · 5684 in / 1149 out tokens · 36006 ms · 2026-05-21T03:41:07.638918+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages

  1. [1]

    Treewidth and gonality of glued grid graphs.Discret

    Ivan Aidun, Frances Dean, Ralph Morrison, Teresa Yu, and Julie Yuan. Treewidth and gonality of glued grid graphs.Discret. Appl. Math., 279:1–11, 2020.doi:10.1016/J.DAM.2019.10.024

    work page doi:10.1016/j.dam.2019.10.024 2020

  2. [2]

    Wagner, and Alfred M

    Yaniv Altshuler, Vladimir Yanovski, Daniel Vainsencher, Israel A. Wagner, and Alfred M. Bruck- stein. On minimal perimeter polyminoes. InDGCI 2006, Lecture Notes in Computer Science, pages 17–28, 2006.doi:10.1007/11907350_2

    work page doi:10.1007/11907350_2 2006

  3. [3]

    Bezrukov and Uwe Leck

    Sergei L. Bezrukov and Uwe Leck. A simple proof of the Karakhanyan–Riordan theorem on the even discrete torus.SIAM J. Discret. Math., 23(3):1416–1421, 2009.doi:10.1137/080715081

    work page doi:10.1137/080715081 2009

  4. [4]

    Bodlaender

    Hans L. Bodlaender. A partialk-arboretum of graphs with bounded treewidth.Theor. Comput. Sci., 209(1-2):1–45, 1998.doi:10.1016/S0304-3975(97)00228-4

    work page doi:10.1016/s0304-3975(97)00228-4 1998

  5. [5]

    Bodlaender, Alexander Grigoriev, and Arie M

    Hans L. Bodlaender, Alexander Grigoriev, and Arie M. C. A. Koster. Treewidth lower bounds with brambles.Algorithmica, 51(1):81–98, 2008.doi:10.1007/S00453-007-9056-Z

    work page doi:10.1007/s00453-007-9056-z 2008

  6. [6]

    Lower bounds on the pathwidth of some grid-like graphs.Discret

    John Ellis and Robert Warren. Lower bounds on the pathwidth of some grid-like graphs.Discret. Appl. Math., 156(5):545–555, 2008.doi:10.1016/J.DAM.2007.02.006

    work page doi:10.1016/j.dam.2007.02.006 2008

  7. [7]

    On tree width, bramble size, and expansion.J

    Martin Grohe and Dániel Marx. On tree width, bramble size, and expansion.J. Comb. Theory B, 99(1):218–228, 2009.doi:10.1016/J.JCTB.2008.06.004

    work page doi:10.1016/j.jctb.2008.06.004 2009

  8. [8]

    Planar lattice subsets with minimal vertex boundary.Electron

    Radhika Gupta, Ivan Levcovitz, Alexander Margolis, and Emily Stark. Planar lattice subsets with minimal vertex boundary.Electron. J. Comb., 28(3), 2021.doi:10.37236/10055

    work page doi:10.37236/10055 2021

  9. [9]

    A discrete isoperimetric problem on multidimensional torus.Doklady AN Armenia SSR, LXXIV(2):61–65, 1982

    Vilik Karakhanyan. A discrete isoperimetric problem on multidimensional torus.Doklady AN Armenia SSR, LXXIV(2):61–65, 1982. in Russian

    work page 1982

  10. [10]

    On the treewidth of toroidal grids.Discret

    Masashi Kiyomi, Yoshio Okamoto, and Yota Otachi. On the treewidth of toroidal grids.Discret. Appl. Math., 198:303–306, 2016.doi:10.1016/J.DAM.2015.06.027

    work page doi:10.1016/j.dam.2015.06.027 2016

  11. [11]

    An ordering on the even discrete torus.SIAM J

    Oliver Riordan. An ordering on the even discrete torus.SIAM J. Discret. Math., 11(1):110–127, 1998.doi:10.1137/S0895480194278234

    work page doi:10.1137/s0895480194278234 1998

  12. [12]

    Seymour and Robin Thomas

    Paul D. Seymour and Robin Thomas. Graph searching and a min-max theorem for tree-width.J. Comb. Theory B, 58(1):22–33, 1993.doi:10.1006/JCTB.1993.1027

    work page doi:10.1006/jctb.1993.1027 1993

  13. [13]

    Polyominoes with minimum site-perimeter and full set achievement games.Eur

    Nándor Sieben. Polyominoes with minimum site-perimeter and full set achievement games.Eur. J. Comb., 29(1):108–117, 2008.doi:10.1016/J.EJC.2006.12.008

    work page doi:10.1016/j.ejc.2006.12.008 2008

  14. [14]

    Discrete isoperimetric problems.SIAM J

    Da-Lun Wang and Ping Wang. Discrete isoperimetric problems.SIAM J. Appl. Math., 32(4):860– 870, 1977.doi:10.1137/0132073

    work page doi:10.1137/0132073 1977

  15. [15]

    David R. Wood. Treewidth of cartesian products of highly connected graphs.J. Graph Theory, 73(3):318–321, 2013.doi:10.1002/JGT.21677. 14

    work page doi:10.1002/jgt.21677 2013