Наредни састанак Семинара биће одржан у петак, 26. децембра 2025, у сали 301ф Математичког института САНУ са почетком у 12:15.
Предавач: Страхиња Гвоздић, ЕТХ Цирих
Наслов предавања: ЈА ДИШЕМ ДУБОКО И САВРШЕНА УПАРИВАЊА БРОЈИМ
Апстракт:
Класична Диракова теорема у терији графова тврди да сваки граф минималног
степена бар n/2 садржи Хамилтонов циклус, односно савршено упаривање.
Бонди је 1995. поставио питање колико најмање граф који задовољава овај
услов (такав граф називамо Дираковим) заправо мора да садржи Хамилтонових
циклуса или савршених упаривања. Каклер и Кан су у два утицајна рада
2009. године дали изненађујућ одговор: сваки Дираков граф садржи барем
онолико Хамилтонових циклуса, односно савршених упаривања, колико је
очекивање датог броја у случајном графу исте густине грана (до на
сублинеарну грешку у експоненту). Недавно су Кван, Сафави и Ванг делимично
проширили овај резултат на хиперграфове у случају савршених упаривања. На
предавању ћемо објаснити неке идеје њиховог доказа и показати како се
жељени број савршених упаривања може обезбедити уз нешто јачи услов од
Дираковог, што даје делимичан одговор на питање постављено у раду Квана,
Сафави и Ванга.
Напомена: Предавања можете пратити на даљину. Све информације су доступне на страници:
