Wykład laureatki IV edycji konkursu im. Edyty Szymańskiej

Data: wtorek, 28.03.2023, godz. 12:00

Prelegent: dr Joanna Polcyn-Lewandowska (WMI UAM)

Abstrakt: 

Jeden z najstarszych wyników współczesnej teorii grafów, twierdzenie Mantela (1907), mówi, że każdy graf o $n$ wierzchołkach, który nie zawiera trójkątów, ma nie więcej niż $\frac{n^2}{4}$ krawędzi.

Około pół wieku później (1962) Andrásfai badając gęste grafy bez trójkątów udowodnił, że spośród wszystkich takich grafów, które dodatkowo nie zawierają zbiorów niezależnych wielkości $s$, gdzie $\frac{2n}{5}\le s<\frac{n}{2}$, najwięcej krawędzi zawiera rozdmuchany cykl na pięciu wierzchołkach.

Przedstawię najnowsze wyniki badań w kierunku zrozumienia struktury gęstych grafów bez trójkątów oraz dużych zbiorów niezależnych.

W szczególności podam wyniki określające maksymalną liczbę krawędzi w grafie o $n$ wierzchołkach, który nie zawiera trójkątów oraz zbiorów niezależnych wielkości $s$, $s\ge \frac{4n}{11}$ oraz podam hipotezę dla $s>\frac{n}{3}$. W przypadku, gdy  $s<\frac{n}{3}$, sytuacja jest odmienna, ale dzięki pracy Brandta rozumiemy ją dość dobrze.

Miejsce: Aula C (WMiI)

Więcej o konkursie oraz laureatce można znaleźć na stronie Konkursu im. Edyty Szymańskiej