Laboratory of Mathematical Logic at PDMI

Вторник, 18 апреля, комната 412. Начало в 13:30.

Докладчик: А. Тискин.

НЕСТАНДАРТНЫЕ ПРИМЕНЕНИЯ ЭКСТРЕМАЛЬНОЙ ТЕОРИИ ГРАФОВ
В 1975 г. Семереди сформулировал и доказал лемму о регулярном разбиении (Szemeredi's regularity lemma). В последние годы этот результат стал активно использоваться для решения экстремальных задач теории графов, однако его применение возможно и в других областях математики. В докладе будет рассказано о двух задачах, решенных при помощи нестандартного применения леммы семереди: задача об асимптотической плотности упаковки трехмерных полимино, и задача о коммуникационной сложности умножения булевых матриц.