Treewidth of grid subsets (Q2416442)

The \(3\)-dimensional \( n \times n \times n \) grid \( Q_n \) considered in this paper is the `usual' \(3\)-dimensional grid with non-decreasing diagonals of its unit cubes added to its set of edges. Any \(2\)-coloring of the vertices of \( Q_n \) is known to contain a monochromatic subgraph with \( \Omega(n^2)\) vertices. This paper is concerned with the `\(2\)-dimensionality' of such subgraphs as represented by their tree-width. The authors prove that for any tree-width \( t \geq 0 \) there exists an \( n \geq 1 \) such that any partition of the vertices of \(Q_n\) into two sets has the property that at least one of the sets induces a subgraph of \( Q_n\) of tree-width at least \(t\). As a corollary, the class \( Q_n \), \( n \geq 1 \), is not tree-width fragile. Unlike the previously known classes which are not tree-width fragile, the class \( Q_n \), \( n \geq 1 \), has bounded maximum degree. It is also the first known class that is not tree-width fragile while being fractionally tree-width fragile. In addition, it is shown that any subset of vertices separating the vertices of \(Q_n\) into two subsets contains an induced subgraph of tree-width at least \( \frac{n}{\sqrt{18}}-1 \). The employed proof techniques include an interesting use of a discrete variant of homotopy theory.