Excluding a countable clique (Q1305523): Difference between revisions

Let \(G= (V,E)\) be a simple undirected graph (possibly infinite). \(H\) is a minor of \(G\) if \(G\) contains a family \((V_x)_{x\in V(H)}\) of disjoint connected vertex sets (possibly infinite) such that \(G\) has a \(V_x- V_y\) edge whenever \(xy\) is an edge of \(H\). If \(T\) is a tree and \({\mathcal V}= (V_t)_{t\in T}\) is a family of vertex sets \(V_t\) in \(G\) then the pair \({\mathcal D}= (T,{\mathcal V})\) is called a tree-decomposition of \(G\) if it satisfies three conditions for \(V_t\), given in Chapter 2. Some properties of tree-decompositions which are necessary for the proofs are considered by nine lemmas in Chapter 5. \({\mathcal D}\) is said to have a finite adhesion if the values of \(|V_{t_1}- V_{t_2}|\) for edges \(t_1t_2\in T\) and of \(\liminf_{i\to\infty}|V_{t_i}\cap V_{t_{i+1}}|\) for infinite paths \(t_1t_2\dots\) in \(T\) are always finite. A surface \(S\) is defined to be a compact connected 2-manifold with boundary, and \(S\) is said to be closed if its boundary is empty. The class of all countable graphs that can be nearly embedded in \(S\) is denoted by \({\mathcal F}(S)\). The concept of nearly embedding of \(G\) in \(S\) is defined in Chapter 2, and in Chapter 4 some of its properties are given. The main results of the authors are given by two theorems. The first result is the extension to infinite graphs of the known \(K_n\) excluded minor theorem of Robertson and Seymour (Theorem 2.2). Let \(S_n\) be the orientable (and analogously \(S_n'\) the non-orientable) closed surfaces of highest genus in which \(K_n\) cannot be embedded. Then, for integers \(n\) and \(k\) the following holds: For every \(n\geq 0\) there exists a \(k\geq 0\) such that every (finite or infinite) graph with no \(K_n\) minor has a tree-decomposition over \({\mathcal F}(S_n- k)\cup{\mathcal F}(S_n'- k)\) (Theorem 3.1). Its extensive proof (in Chapter 6) is carried out with the help of a lemma (Lemma 6.1). The second result is a structural characterization of the infinite graphs that have no \(K_{\aleph_0}\) minor. It yields a refinement of an earlier characterization of Robertson, Seymour, and Thomas (Theorem 2.1): A graph has no \(K_{\aleph_0}\) minor iff it has a tree-decomposition of finite adhesion over plane graphs with at most one vertex (Theorem 3.2). Also this proof is an extensive one and is carried out by two lemmas in Chapter 7.