Data wydarzenia:

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

Grafika konkursowa i zdjęcie laureatki

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ż n24 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 2n5s<n2, 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, s4n11 oraz podam hipotezę dla s>n3. W przypadku, gdy  s<n3, 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