Laboratory of Mathematical Logic at PDMI

Пятница, 9 ноября, комната 106. Начало в 17:45.

Докладчик: С. Николенко.

Тема: Structure and randomness in combinatorics.

Abstract

Доклад по статье Terence Tao.

В комбинаторике и информатике часто возникает дихотомия между объектами с богатой структурой (полные двудольные графы, полиномы малой степени и т.д.) и ``псевдослучайными'' объектами. У структурированных объектов свои свойства, у ``псевдослучайных'' --- свои, и зачастую приходится рассматривать их отдельно, однако при этом один и тот же объект не может быть одновременно структурированным и ``псевдослучайным''. Это приводит к интересной идее: может быть, можно каким-нибудь образом разложить любой объект в сумму $$f = f_{str}+f_{psd}+f_{err},$$ где $f_{str}$ структурирован, $f_{psd}$ ``псевдослучаен'', а $f_{err}$ --- малая ошибка? Мы попытаемся получить такие разложения для гильбертовых и метрических пространств, а затем применить их к задачам теории графов и теории кодирования.