Well-quasi-ordering infinite graphs with forbidden finite planar minor

Thomas, Robin

doi:10.1090/S0002-9947-1989-0932450-9

Well-quasi-ordering infinite graphs with forbidden finite planar minor
HTML articles powered by AMS MathViewer

by Robin Thomas PDF

Trans. Amer. Math. Soc. 312 (1989), 279-313 Request permission

Abstract:

We prove that given any sequence ${G_1},{G_2}, \ldots$ of graphs, where ${G_1}$ is finite planar and all other ${G_i}$ are possibly infinite, there are indices $i,j$ such that $i < j$ and ${G_i}$ is isomorphic to a minor of ${G_j}$ . This generalizes results of Robertson and Seymour to infinite graphs. The restriction on ${G_1}$ cannot be omitted by our earlier result. The proof is complex and makes use of an excluded minor theorem of Robertson and Seymour, its extension to infinite graphs, Nash-Williams’ theory of better-quasi-ordering, especially his infinite tree theorem, and its extension to something we call tree-structures over ${\text {QO}}$-categories, which includes infinitary version of a well-quasi-ordering theorem of Friedman.

References

Rigid Borel sets and better quasiorder theory

The metamathematics of the graph minor theorem

Fred Galvin and Karel Prikry, Borel sets and Ramsey’s theorem, J. Symbolic Logic 38 (1973), 193–198. MR 337630, DOI 10.2307/2272055
Graham Higman, Ordering by divisibility in abstract algebras, Proc. London Math. Soc. (3) 2 (1952), 326–336. MR 49867, DOI 10.1112/plms/s3-2.1.326

The Menger-like property of tree-width of infinite graphs and related compactness results

J. B. Kruskal, Well-quasi-ordering, the Tree Theorem, and Vazsonyi’s conjecture, Trans. Amer. Math. Soc. 95 (1960), 210–225. MR 111704, DOI 10.1090/S0002-9947-1960-0111704-1
Joseph B. Kruskal, The theory of well-quasi-ordering: A frequently discovered concept, J. Combinatorial Theory Ser. A 13 (1972), 297–305. MR 306057, DOI 10.1016/0097-3165(72)90063-5
Richard Laver, On Fraïssé’s order type conjecture, Ann. of Math. (2) 93 (1971), 89–111. MR 279005, DOI 10.2307/1970754
Richard Laver, Better-quasi-orderings and a class of trees, Studies in foundations and combinatorics, Adv. in Math. Suppl. Stud., vol. 1, Academic Press, New York-London, 1978, pp. 31–48. MR 520553
Stephen G. Simpson (ed.), Logic and combinatorics, Contemporary Mathematics, vol. 65, American Mathematical Society, Providence, RI, 1987. MR 891239, DOI 10.1090/conm/065
W. Mader, Wohlquasigeordnete Klassen endlicher Graphen, J. Combinatorial Theory Ser. B 12 (1972), 105–122 (German, with English summary). MR 297611, DOI 10.1016/0095-8956(72)90015-9
C. St. J. A. Nash-Williams, On well-quasi-ordering finite trees, Proc. Cambridge Philos. Soc. 59 (1963), 833–835. MR 153601, DOI 10.1017/s0305004100003844
C. St. J. A. Nash-Williams, On well-quasi-ordering infinite trees, Proc. Cambridge Philos. Soc. 61 (1965), 697–720. MR 175814, DOI 10.1017/s0305004100039062
C. St. J. A. Nash-Williams, On better-quasi-ordering transfinite sequences, Proc. Cambridge Philos. Soc. 64 (1968), 273–290. MR 221949, DOI 10.1017/s030500410004281x
R. Rado, Partial well-ordering of sets of vectors, Mathematika 1 (1954), 89–95. MR 66441, DOI 10.1112/S0025579300000565
Neil Robertson and P. D. Seymour, Generalizing Kuratowski’s theorem, Proceedings of the fifteenth Southeastern conference on combinatorics, graph theory and computing (Baton Rouge, La., 1984), 1984, pp. 129–138. MR 777718
Neil Robertson and P. D. Seymour, Graph minors. II. Algorithmic aspects of tree-width, J. Algorithms 7 (1986), no. 3, 309–322. MR 855559, DOI 10.1016/0196-6774(86)90023-4

Graph minors

Tree-width and well-quasi-ordering

Neil Robertson and P. D. Seymour, Graph minors. V. Excluding a planar graph, J. Combin. Theory Ser. B 41 (1986), no. 1, 92–114. MR 854606, DOI 10.1016/0095-8956(86)90030-4

Graph minors

Richard Mansfield and Galen Weitkamp, Recursive aspects of descriptive set theory, Oxford Logic Guides, vol. 11, The Clarendon Press, Oxford University Press, New York, 1985. With a chapter by Stephen Simpson. MR 786122
Stephen G. Simpson, Nonprovability of certain combinatorial properties of finite trees, Harvey Friedman’s research on the foundations of mathematics, Stud. Logic Found. Math., vol. 117, North-Holland, Amsterdam, 1985, pp. 87–117. MR 835255, DOI 10.1016/S0049-237X(09)70156-9
Robin Thomas, A counterexample to “Wagner’s conjecture” for infinite graphs, Math. Proc. Cambridge Philos. Soc. 103 (1988), no. 1, 55–57. MR 913450, DOI 10.1017/S0305004100064616

The tree-width compactness theorem for hypergraphs

Robin Thomas, A Menger-like property of tree-width: the finite case, J. Combin. Theory Ser. B 48 (1990), no. 1, 67–76. MR 1047553, DOI 10.1016/0095-8956(90)90130-R

Infinite graphs without

and better-quasi-ordering

Carsten Thomassen, Configurations in graphs of large minimum degree, connectivity, or chromatic number, Combinatorial Mathematics: Proceedings of the Third International Conference (New York, 1985) Ann. New York Acad. Sci., vol. 555, New York Acad. Sci., New York, 1989, pp. 402–412. MR 1018651, DOI 10.1111/j.1749-6632.1989.tb22479.x