Halin's grid theorem

In graph theory, a branch of mathematics, 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 (1965), and is a precursor to the work of Robertson and Seymour linking treewidth to large grid minors, 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. Halin (1964) defined two rays r₀ and r₁ to be equivalent if there exists a ray r₂ 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 (1965) defined a thick end of a graph to be an end that contains infinitely many rays that are pairwise disjoint from each other.

The hexagonal tiling of the plane

An example of a graph with a thick end is provided by the hexagonal tiling of the Euclidean plane. Its vertices and edges form an infinite cubic planar graph, which contains many rays. For example, some of its rays form Hamiltonian paths that spiral out from a central starting vertex and cover all the vertices of the graph. One of these spiraling rays can be used as the ray r₂ in the definition of equivalence of rays (no matter what rays r₀ and r₁ are given), showing that every two rays are equivalent and that this graph has a single end. There also exist infinite sets of rays that are all disjoint from each other, for instance the sets of rays that use only two of the six directions that a path can follow within the tiling. Because it has infinitely many pairwise disjoint rays, all equivalent to each other, this graph has a thick end.

Halin's theorem states that this example is universal: every graph with a thick end contains as a subgraph either this graph 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 of finite graphs has unbounded treewidth if and only if the minors of graphs in 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 of order ℵ₀. It is not always true 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

• Demaine, Erik D.; Hajiaghayi, MohammadTaghi (2005), "Bidimensionality: new connections between FPT algorithms and PTASs", Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA) (PDF), pp. 590–601, MR 2298309.
• Diestel, Reinhard (2004), "A short proof of Halin's grid theorem", Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, 74: 237–242, doi:10.1007/BF02941538, MR 2112834.
• Diestel, Reinhard; Kühn, Daniela (2003), "Graph-theoretical versus topological ends of graphs", Journal of Combinatorial Theory, Series B, 87 (1): 197–206, doi:10.1016/S0095-8956(02)00034-5, MR 1967888.
• Halin, Rudolf (1964), "Über unendliche Wege in Graphen", Mathematische Annalen, 157 (2): 125–137, doi:10.1007/bf01362670, hdl:10338.dmlcz/102294, MR 0170340.
• Halin, Rudolf (1965), "Über die Maximalzahl fremder unendlicher Wege in Graphen", Mathematische Nachrichten, 30 (1–2): 63–85, doi:10.1002/mana.19650300106, MR 0190031.
• Seymour, Paul D.; Thomas, Robin (1993), "Graph searching and a min-max theorem for tree-width", Journal of Combinatorial Theory, Series B, 58 (1): 22–33, doi:10.1006/jctb.1993.1027.