Home

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

  • The directory /tmp/drutex-d08145ef673e23f3fcc0e0a309b0784f-1 has been created.
  • The directory /tmp/drutex-d08145ef673e23f3fcc0e0a309b0784f-2 has been created.
  • The directory /tmp/drutex-d08145ef673e23f3fcc0e0a309b0784f-3 has been created.

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

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

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

Abstract

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