Home

Семинар 9 ноября 2007 года

Пятница, 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} $ --- малая ошибка? Мы попытаемся получить такие разложения для гильбертовых и метрических пространств, а затем применить их к задачам теории графов и теории кодирования.