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} ≤ 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≥\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
