Полные подграфы в случайных графах и регулярные резолюции

Размер максимальной клики в случайном графе Эрдеша-Реньи $G(n,p)$ хорошо известен и практически полностью определяется плотностью графа $p=p(n)$. Однако доказательство того, что почти все графы плотности ниже критической не содержат клику требуемого размера, совершенно неконструктивно и не даёт никаких указаний на то, как этот факт доказывать для индивидуальных графов. Исследование этого вопроса с точки зрения теории сложности доказательств является в настоящее время довольно активной областью, связанной с приложениями в теории комбинаторной оптимизации и криптографии (planted clique) и в теории параметризованной сложности доказательств.
Настоящий доклад основан на совместной работе с Atserias, Bonacina, de Rezende, Laiuria и Nordstrom (STOC 2018), в которой эта задача решена для системы регулярных резолюций. Именно, показывается, что при подходящих значениях параметров любое доказательство отсутствия клики требуемого размера в случайном графе обязано иметь экспоненциальный размер.