Speaker:

Ton Kloks (National Tsing Hua University )

Time:

• 10:20-11:20 (Time in Beijing)
• November 3, 2023 (Friday)

Venue:

518, Research Building 4

Abstract:

This is a paper from 1994.  (In my opinion this paper is a work of art.)   
The paper proves Robertson’s conjecture on well-quasi-orders by topological minors for classes of graphs that are closed under minors.
 
 Robertson conjectured that classes of graphs are WQO by topological minors 
 if they don’t have arbitrary long double paths. The conjecture has been proved; 
 The first part of the proof was published in 2023.

 I will explain (ordinary) graph minors, well-quasi-orders, topological minors 
 and everything else that is needed in great detail. 
 I expect that I will need at least 3 hours in total for this paper; 
 so probably we will split it up into two Fridays. 

 For my talk I have not prepared any slides; I will use the whiteboard, and 
 put the text of Ding’s paper on the screen. (We will go through it step by step.) 

 The plan is that I will speak later about the FPT algorithm by Grohe et al. (2011) for topological minors (if people are interested in that).