Optimizing the graph minors weak structure theorem (Q2870501)

A key result in the structural theory of graphs is Robertson, Seymour and Thomas's so-called weak structure theorem for graphs excluding a certain fixed graph as a minor [\textit{N. Robertson} and \textit{P. D. Seymour}, J. Comb. Theory, Ser. B 63, No. 1, 65--110 (1995; Zbl 0823.05038)]. The original theorem is that there is a function \(f: \mathbb{N}\times \mathbb{N}\rightarrow \mathbb{N}\) such that for every \(k\in \mathbb{N}\), every \(h\)-vertex graph \(H\) and every graph \(G\), either \(G\) contains \(H\) as a minor, or \(G\) has treewidth at most \(f(h,k)\) or there is a set \(X\) of at most \({h\choose 2}\) vertices (apices) of \(G\) such that \(G\backslash X\) contains as a subgraph a subdivision of a certain graph, the `wall\'\, of height \(k\) which is arranged in \(G\) in a certain `flat\'\, manner (called the flatness condition: we omit its exact definition).NEWLINENEWLINEThe paper under review gives a significant sharpening of the weak structure theorem by firstly, making \(f(h,k)\) a function linear in \(k\) and secondly by reducing the maximum number of apices from \({h\choose 2}\) to \(h-5\). This is optimal as can be shown by considering a \(k\times k\) grid all of whose vertices are adjacent to all vertices in a \(K_{h-5}\). The proof is non-trivially harder than in the original paper of Robertson and Seymour: in particular, it uses their strong structure theory on the global structure of graphs with no \(K_{h}\) minor [\textit{N. Robertson} and \textit{P. D. Seymour}, J. Comb. Theory, Ser. B 89, No. 1, 43--76 (2003; Zbl 1023.05040)] together with facts from [\textit{F. V. Fomin} et al., J. Comb. Theory, Ser. B 101, No. 5, 302--314 (2011; Zbl 1223.05022)].