|
ВИДЕОТЕКА |
Традиционная зимняя сессия МИАН–ПОМИ, посвященная теме «Математическая
логика»
|
|||
|
Полные подграфы в случайных графах и регулярные резолюции А. А. Разборов Математический институт им. В.А. Стеклова Российской академии наук, г. Москва |
|||
Аннотация: Размер максимальной клики в случайном графе Эрдеша-Реньи Настоящий доклад основан на совместной работе с Atserias, Bonacina, de Rezende, Laiuria и Nordstrom (STOC 2018), в которой эта задача решена для системы регулярных резолюций. Именно, показывается, что при подходящих значениях параметров любое доказательство отсутствия клики требуемого размера в случайном графе обязано иметь экспоненциальный размер. |