Applications of order trees in infinite graphs. (English) Zbl 07839448
Summary: Traditionally, the trees studied in infinite graphs are trees of height at most \(\omega \), with each node adjacent to its parent and its children (and every branch of the tree inducing a path or a ray). However, there is also a method, systematically introduced by J. M. Brochet and R. Diestel [Trans. Am. Math. Soc. 345, No. 2, 871–895 (1994; Zbl 0814.05029)], of turning arbitrary well-founded order trees \(T\) into graphs, in a way such that every \(T\)-branch induces a generalised path in the sense of R. Rado [Ann. Discrete Math. 3, 191–194 (1978; Zbl 0388.05031)]. This article contains an introduction to this method and then surveys four recent applications of order trees to infinite graphs, with relevance for well-quasi orderings, Hadwiger’s conjecture, normal spanning trees and end-structure, the last two addressing long-standing open problems by R. Halin [ibid. 3, 93–109 (1978; Zbl 0383.05034)].
Keywords:
order trees; normal tree orders; normal spanning trees; well-quasi ordering; minor antichains; colouring numberReferences:
| [1] | Baumgartner, JE, Results and Independence Proofs in Combinatorial Set Theory, 1970, Berkeley: University of California, Berkeley |
| [2] | Bowler, N.; Carmesin, J.; Komjáth, P.; Reiher, C., The colouring number of infinite graphs, Combinatorica, 39, 1225-1235, 2019 · Zbl 1449.05189 · doi:10.1007/s00493-019-4045-9 |
| [3] | Bowler, N.; Geschke, G.; Pitz, M., Minimal obstructions for normal spanning trees, Fund. Math., 241, 245-263, 2018 · Zbl 1402.05152 · doi:10.4064/fm337-10-2017 |
| [4] | Brochet, J-M; Diestel, R., Normal tree orders for infinite graphs, Trans. Am. Math. Soc., 345, 2, 871-895, 1994 · Zbl 0814.05029 · doi:10.1090/S0002-9947-1994-1260198-4 |
| [5] | Bürger, C.; Pitz, M., Partitioning edge-coloured infinite complete bipartite graphs into monochromatic paths, Israel J. Math., 238, 479-500, 2020 · Zbl 1447.05168 · doi:10.1007/s11856-020-2030-z |
| [6] | Diestel, R., Graph Theory, 2015, Berlin: Springer, Berlin |
| [7] | Diestel, R.; Leader, I., Normal spanning trees, Aronszajn trees and excluded minors, J. Lond. Math. Soc., 63, 1, 16-32, 2001 · Zbl 1012.05051 · doi:10.1112/S0024610700001708 |
| [8] | Elekes, M.; Soukup, DT; Soukup, L.; Szentmiklóssy, Z., Decompositions of edge-colored infinite complete graphs into monochromatic paths, Discret. Math., 340, 8, 2053-2069, 2017 · Zbl 1362.05102 · doi:10.1016/j.disc.2016.09.028 |
| [9] | Geschke, S., Kurkofka, J., Melcher, R., Pitz, M.: Halin’s end degree conjecture. Israel J. Math. (2021) · Zbl 07912968 |
| [10] | Hajnal, A., The chromatic number of the product of two ℵ1-chromatic graphs can be countable, Combinatorica, 5, 2, 137-139, 1985 · Zbl 0575.05029 · doi:10.1007/BF02579376 |
| [11] | Halin, R., Über die Maximalzahl fremder unendlicher Wege in Graphen, Mathematische Nachrichten, 30, 1-2, 63-85, 1965 · Zbl 0131.20904 · doi:10.1002/mana.19650300106 |
| [12] | Halin, R.: Unterteilungen vollständiger Graphen in Graphen mit unendlicher chromatischer zahl. In: Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, vol. 31, pp. 156-165. Springer (1967) · Zbl 0153.54204 |
| [13] | Halin, R.: Simplicial decompositions of infinite graphs. In: Annals of Discrete Mathematics, vol. 3, pp. 93-109. Elsevier (1978) · Zbl 0383.05034 |
| [14] | Halin, R., Miscellaneous problems on infinite graphs, J. Graph Theory, 35, 2, 128-151, 2000 · Zbl 0960.05001 · doi:10.1002/1097-0118(200010)35:2<128::AID-JGT6>3.0.CO;2-6 |
| [15] | Jech, T.: Set theory, The Third Millennium Edition Springer Monographs in Mathematics (2013) |
| [16] | Jung, H., Wurzelbäume und unendliche Wege in Graphen, Math. Nachr., 41, 1-22, 1969 · Zbl 0177.27001 · doi:10.1002/mana.19690410102 |
| [17] | Jung, HA, Zusammenzüge und Unterteilungen von Graphen, Mathematische Nachrichten, 35, 5-6, 241-267, 1967 · Zbl 0171.44803 · doi:10.1002/mana.19670350503 |
| [18] | Komjáth, P.: A note on minors of uncountable graphs. In: Mathematical Proceedings of the Cambridge Philosophical Society, vol. 117, pp 7-9 (1995) · Zbl 0843.05099 |
| [19] | Komjáth, P.: Hadwiger’s conjecture for uncountable graphs. In: Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, vol. 87, pp. 337-341. Springer (2017) · Zbl 1437.03145 |
| [20] | Kriz, I.; Thomas, R., Clique-sums, tree-decompositions and compactness, Discrete Math., 81, 2, 177-185, 1990 · Zbl 0745.05021 · doi:10.1016/0012-365X(90)90150-G |
| [21] | Lambie-Hanson, C., On the growth rate of chromatic numbers of finite subgraphs, Adv. Math., 369, 107176, 2020 · Zbl 1440.05090 · doi:10.1016/j.aim.2020.107176 |
| [22] | Nash-Williams, C.S.J.: On well-quasi-ordering infinite trees. In: Mathematical proceedings of the cambridge philosophical society, vol. 61, pp 697-720. Cambridge University Press (1965) · Zbl 0144.23305 |
| [23] | Pitz, M.: A new obstruction for normal spanning trees. Bull. London Math. Soc. 53, 1220-1227 (2021) · Zbl 1475.05159 |
| [24] | Pitz, M.: A note on minor antichains of uncountable graphs. arXiv:2005.05816 (2020) |
| [25] | Pitz, M.: Quickly proving Diestel’s normal spanning tree criterion. Electron. J. Comb. 28(3), P3.59 (2021) · Zbl 1478.05024 |
| [26] | Pitz, M., A unified existence theorem for normal spanning trees, J. Comb. Theory Series B, 145, 466-469, 2020 · Zbl 1448.05037 · doi:10.1016/j.jctb.2020.07.002 |
| [27] | Pitz, M.: Proof of Halin’s normal spanning tree conjecture. Israel J. Math. 246, 353-370 (2021) · Zbl 1487.05098 |
| [28] | Rado, R.: Monochromatic paths in graphs. In: Annals of discrete mathematics, vol. 3, pp. 191-194. Elsevier (1978) · Zbl 0388.05031 |
| [29] | Robertson, N.; Seymour, P.; Thomas, R., Excluding infinite minors, Discret. Math., 95, 1-3, 303-319, 1991 · Zbl 0759.05082 · doi:10.1016/0012-365X(91)90343-Z |
| [30] | Soukup, DT, Trees, Ladders and graphs, J. Comb. Theory, Series B, 115, 96-116, 2015 · Zbl 1319.05041 · doi:10.1016/j.jctb.2015.05.004 |
| [31] | Soukup, DT, Decompositions of edge-coloured infinite complete graphs into monochromatic paths II, Israel J. Math., 221, 1, 235-273, 2017 · Zbl 1375.05108 · doi:10.1007/s11856-017-1552-5 |
| [32] | Stone, AH, On σ-discreteness and Borel isomorphism, Am. J. Math., 85, 4, 655-666, 1963 · Zbl 0117.40103 · doi:10.2307/2373113 |
| [33] | Stone, AH, Non-separable Borel sets, II, Gen. Topol. Appl., 2, 3, 249-270, 1972 · Zbl 0245.54039 · doi:10.1016/0016-660X(72)90010-4 |
| [34] | Thomas, R.: A counter-example to Wagner’s conjecture for infinite graphs. In: Mathematical Proceedings of the Cambridge Philosophical Society, vol. 103, pp. 55-57. Cambridge University Press (1988) · Zbl 0647.05054 |
| [35] | Todorcevic, S.: On a conjecture of R. Rado. J. London Math. Soc.(2) 27(1), 1-8 (1983) · Zbl 0524.03033 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
