Tree of Tangles

The following is a summary of Efficiently distinguishing tangles in locally finite graphs [JK2024] which is joint work with Raphael W. Jacobs. In 2024 it is published in Journal of Combinatorial Theory, Series B. You can find a preprint on arXiv. 

Main Results

1.) Every connected locally finite graph without thick ends has a canonical tree-decomposition which efficiently distinguishes all its tangles [JK2024, Theorem 1].

2.) If in a locally finite graph G a tree of tangles N does not induce a tree-decomposition, then G contains a thick end (equivalently: a half-grid minor) [JK2024, Theorem 2]. Moreover, we locate a thick end in every problematic limit of N.

Summary

A tree of tangles of a graph G is a nested set N of separations which efficiently distinguishes all tangles and every separation in N is such an efficient tangle distinguisher. Not only Carmesin, Hamann and Miraftab [CHM22, Theorem 7.3] but also Elbracht, Kneip and Teegen [EKT2021, Theorem 6.6] proved that every locally finite graph admits a tree of tangles. One of the gems of Robertson and Seymour's graph minor series [RS91] is the tree-of-tangles theorem: Every finite graph admits a tree-decomposition which efficiently distinguishes all its tangles. Equivalently one may phrase it as: Every finite graph admits a tree of tangles which induces a tree-decomposition.  

While not only every tree of tangles but even every nested set of separations of a finite graph induces a tree-decomposition [CDHS14, Theorem 4.8], Elbracht, Kneip and Teegen presented a graph [EKT2021, Example 4.9] which admits a tree of tangles N that does not induce a tree-decomposition. To do so they showed that the nested set N has a problematic limit, that is some strictly ≤-decreasing¹ sequence of separations (Aᵢ , Bᵢ) in N such that their intersection ⋂ᵢ (Bᵢ \ Aᵢ) is non-empty. Indeed, this suffices due to their characterisation of the nested sets N of separations which induce a tree-decomposition [EKT2021, Lemma 2.7] as those which do not contain a problematic limit. 

It is quite central to their example that it has a thick end in its problematic limit. In fact our 1st main result ensures that one finds such a thick end in each problematic limit of every tree of tangles. It is noteworthy that previous work achieved extensions of Robertson and Seymour's trees-of-tangles theorem to infinite graphs through relaxation of the conclusion but we identified the obstructions directly and obtain a full-strength extension, our 2nd main result, as a cororally when these are absent.

References

[CDHS14] J. Carmesin, R. Diestel, F. Hundertmark, and M. Stein, Connectivity and tree structure in finite graphs, Combinatorica 34.1 (2014): 1–35. Available at arXiv:1105.1611.

[CHM22] J. Carmesin, M. Hamann, and B. Miraftab, Canonical trees of tree-decompositions, Journal of Combinatorial Theory, Series B 152 (2022): 1–26. Available at arXiv:2002.12030.

[EKT2021] C. Elbracht, J. Kneip, and M. Teegen, Trees of tangles in infinite separation systems, Mathematical Proceedings of the Cambridge Philosophical Society 173.2 (2022): 297 - 327. Available at arXiv:2005.12122.

[RS91] N. Robertson and P. D. Seymour, Graph minors. X. Obstructions to tree-decomposition, Journal of Combinatorial Theory, Series B 52 (1991): 153–190.

¹Attention: Nowadays we define the natural partial order on the set of separations by (A,B) ≤ (C,D) if A ⊇ C and B ⊆ D. Previously, e.g. in [JK2024], we have still used its inverse order as ≤.