Naredni sastanak Seminara biće održan u petak, 26. decembra 2025, u sali 301f Matematičkog instituta SANU sa početkom u 12:15.
Predavač: Strahinja Gvozdić, ETH Cirih
Naslov predavanja: JA DIŠEM DUBOKO I SAVRŠENA UPARIVANjA BROJIM
Apstrakt:
Klasična Dirakova teorema u teriji grafova tvrdi da svaki graf minimalnog
stepena bar n/2 sadrži Hamiltonov ciklus, odnosno savršeno uparivanje.
Bondi je 1995. postavio pitanje koliko najmanje graf koji zadovoljava ovaj
uslov (takav graf nazivamo Dirakovim) zapravo mora da sadrži Hamiltonovih
ciklusa ili savršenih uparivanja. Kakler i Kan su u dva uticajna rada
2009. godine dali iznenađujuć odgovor: svaki Dirakov graf sadrži barem
onoliko Hamiltonovih ciklusa, odnosno savršenih uparivanja, koliko je
očekivanje datog broja u slučajnom grafu iste gustine grana (do na
sublinearnu grešku u eksponentu). Nedavno su Kvan, Safavi i Vang delimično
proširili ovaj rezultat na hipergrafove u slučaju savršenih uparivanja. Na
predavanju ćemo objasniti neke ideje njihovog dokaza i pokazati kako se
željeni broj savršenih uparivanja može obezbediti uz nešto jači uslov od
Dirakovog, što daje delimičan odgovor na pitanje postavljeno u radu Kvana,
Safavi i Vanga.
Napomena: Predavanja možete pratiti na daljinu. Sve informacije su dostupne na stranici:
