Seminarium Kombinatoryka, Teoria Grafów i Zbiorów Uporządkowanych
Wydział Matematyki i Nauk Informacyjnych, Politechnika Warszawska
Kalendarz Środy, 10:15-11:45
Pinezka Gmach MiNI PW, Sala 431, ul. Koszykowa 75, Warszawa
Komputer Seminaria odbywają się stacjonarnie z transmisją na platformie MS Teams.
Mail Jeśli chcesz dołączyć do spotkania, to napisz do sekretarza seminarium.

Najbliższy referat
17.12.2025 (102) Maria Chudnovsky Princeton University
Strip Structures: past and present
\(\quad\)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". \(\quad\)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. \(\quad\)In this talk we will explain the theorem, and illustrate some of its applications.
Zespół prowadzący