Wykład odbędzie się w ramach Seminarium Kombinatoryka, Teoria Grafów i Zbiorów Uporządkowanych PW.

Maria Chudnovsky to jedna z najwybitniejszych współczesnych badaczek w dziedzinie matematyki dyskretnej. Zajmuje się teorią grafów, ze szczególnym uwzględnieniem strukturalnej teorii grafów. Jest współautorką (wraz z Neilem Robertsonem, Paulem Seymourem i Robinem Thomasem) dowodu silnego twierdzenia o grafach doskonałych, odpowiadającego pozytywnie na otwartą przez dziesięciolecia hipotezę Berge’a.

Serdecznie zapraszamy
Paweł Rzążewski, Zbigniew Lonc, Jarosław Grytczuk, Hubert Grochowski

Title: Strip Structures: past and present
Abstract: An independent set S of vertices is „constricted” in a graph G if no induced tree in G contains 3 elements of S. In 2009 Paul Seymour and the speaker proved a theorem describing the structure of constricted sets in graphs. It turns out that if a graph G contains a constricted set Z, then G admits a „strip structure”, which is to say that it roughly resembles a line graph. Moreover, the location of the vertices of Z is tightly controlled. This result is called „3-In-A-Tree”.
The original motivation behind 3-In-A-Tree was to provide a recognition algorithm for induced thetas in graphs, but recently it has been reincarnated. In modern graph optimization algorithms it is used to produce small dominating sets in graphs, or to allow for other ways to track the progress of an algorithm.
In this talk we will explain the theorem, and illustrate some of its applications.