Vaidy Sivaraman (Binghamton)

Nash-Williams' Minimal Bad Sequence Argument

Abstract for the Combinatorics Seminar
2013 December 3

C. Nash-Williams introduced a technique to prove a theorem of Kruskal, stating that any infinite set of finite trees contains two trees such that one of them is a topological subgraph of the other. We will see the technique in action by proving a famous result of G. Higman on well-quasi-ordering finite sequences. I will also discuss the far-reaching consequences of this technique. This will naturally lead to the spectacularly successful graph minors project of N. Robertson and P. Seymour, and the recent matroid minors project of J. Geelen, B. Gerards, and G. Whittle.


To the Combinatorics Seminar Web page.