During the talk, we give a short introduction to the graph minor project of Robertson and Seymour, that is a series of twenty papers that runs along more than 500 pages published from 1983 to 2004. The main result is the proof of conjecture of Wagner : in any infinite set of graphs, there must be a pair of graphs one of which is a minor of the other. This seemingly simple statement is in fact very deep and has algorithmic consequences of stunning generality. We will explain the statement and its consequences in a gentle way for computer scientists and mathematicians who are not specialists in graph theory (including all basic definitions). We will also present recent developments on analogs of some of the results of Robertson and Seymour when the « minor » containment relation is replaced by the « induced subgraph » containment relation.

Some results obtained jointly with Pierre Aboulker, Isolde Adler, Eunjung Kim and Ni Luh Dewi Sintiari will be presented.

Our Math Research Seminar will not be broadcasted via Zoom this time.

Everyone is welcome and encouraged to attend.