In the mathematics of infinite graphs, Halin's grid theorem states that the infinite graphs with thick ends are exactly the graphs containing subdivisions of the hexagonal tiling of the plane. It was published by Rudolf Halin in 1965. It is a precursor to the work of Neil Robertson and Paul Seymour linking treewidth to large grid minors in finite graphs, which became an important component of the algorithmic theory of bidimensionality.
Definitions and statement A ray, in an infinite graph, is a semi-infinite path: a connected infinite subgraph in which one vertex has degree one and the rest have degree two. In a precursor to the paper proving his grid theorem, Halin defined two rays r 0 {\displaystyle r_{0}} and r 1 {\displaystyle r_{1}} to be equivalent if there exists a ray r 2 {\displaystyle r_{2}} that includes infinitely many vertices from each of them. This is an equivalence relation, and its equivalence classes (sets of mutually equivalent rays) are called the ends of the graph. Halin defined a thick end of a graph to be an end that contains infinitely many rays that, despite being equivalent, are pairwise disjoint from each other.
An example of a graph with a thick end is provided by the hexagonal tiling of the Euclidean plane. The subset of the hexagonal tiling within any fixed angle also has infinitely many disjoint rays. Reinhard Diestel defines a partial hexagonal grid with this combinatorial structure consisting of the integer points ( x , y ) {\displaystyle (x,y)} with 0 ≤ x ≤ y {\displaystyle 0\leq x\leq y} (a 45° angle), with vertical edges connecting each ( x , y ) {\displaystyle (x,y)} to ( x , y + 1 ) {\displaystyle (x,y+1)} but with horizontal edges from ( x , y ) {\displaystyle (x,y)} to ( x + 1 , y ) {\displaystyle (x+1,y)} only when x + y {\displaystyle x+y} is odd. For a partial hexagonal grid, defined in this way, the geometric rays extending vertically from each point ( x , x ) {\displaystyle (x,x)} provide infinitely many disjoint graph-theoretic rays, all of which belong to the same thick end. Halin's theorem states that this example is universal: every graph with a thick end contains as a subgraph either this partial hexagonal grid itself, or a graph formed from it by modifying it in simple ways, by subdividing some of its edges into finite paths. The subgraph of this form can be chosen so that its rays belong to the given thick end. Conversely, whenever an infinite graph contains a subdivision of the hexagonal tiling, it must have a thick end, namely the end that contains all of the rays that are subgraphs of this subdivision.
Analogues for finite graphs As part of their work on graph minors leading to the Robertson–Seymour theorem and the graph structure theorem, Neil Robertson and Paul Seymour proved that a family F {\displaystyle {\mathcal {F}}} of finite graphs has unbounded treewidth if and only if the minors of graphs in F {\displaystyle {\mathcal {F}}} include arbitrarily large square grid graphs, or equivalently subgraphs of the hexagonal tiling formed by intersecting it with arbitrarily large disks. Although the precise relation between treewidth and grid minor size remains elusive, this result became a cornerstone in the theory of bidimensionality, a characterization of certain graph parameters that have particularly efficient fixed-parameter tractable algorithms and polynomial-time approximation schemes. For finite graphs, the treewidth is always one less than the maximum order of a haven, where a haven describes a certain type of strategy for a robber to escape the police in a pursuit–evasion game played on the graph, and the order of the haven gives the number of police needed to catch a robber using this strategy. Thus, the relation between treewidth and grid minors can be restated: in a family of finite graphs, the order of the havens is unbounded if and only if the size of the grid minors is unbounded. For infinite graphs, the equivalence between treewidth and haven order is no longer true, but instead havens are intimately connected to ends: the ends of a graph are in one-to-one correspondence with the havens whose order is the aleph number ℵ 0 {\displaystyle \aleph _{0}} . It is not always the case that an infinite graph has a haven of infinite order if and only if it has a grid minor of infinite size, but Halin's theorem provides an extra condition (the thickness of the end corresponding to the haven) under which it becomes true.
References
