Home

Семинар 14 ноября 2008 года

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

Докладчик: Д. Ицыксон, К. Шмаков.

Тема: Графы большой колмогоровской сложности являются расширителями.

Abstract

В докладе будет доказано, что из графа большой колмогоровской сложности (случайного графа) с $ n $ вершинами и $ O(n) $ ребрами можно выкинуть несколько ребер так, чтобы получившийся граф обладал следующими свойствами: - степени его вершин ограничены константой; - для любого разбиения множества вершин на две примерно равные части, существует $ Omega(n) $ рёбер, соединяющих вершины из разных частей. Никаких предварительных знаний о колмогоровской сложности от слушателей не предполагается.