Видеотека
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Видеотека
Архив
Популярное видео

Поиск
RSS
Новые поступления






Летняя школа «Современная математика», 2010
20 июля 2010 г. 17:00, г. Дубна
 


Экстремальные задачи комбинаторики и теории геометрических графов. Лекция 1

А. М. Райгородский
Видеозаписи:
Windows Media 515.5 Mb
Flash Video 863.1 Mb
MP4 863.1 Mb

Количество просмотров:
Эта страница:1737
Видеофайлы:838

А. М. Райгородский


Видео не загружается в Ваш браузер:
  1. Проверьте с Вашим администратором, что из Вашей сети разрешены исходящие соединения на порт 8080
  2. Сообщите администратору портала о данной ошибке

Аннотация: Лекции будут посвящены одному из самых ярких разделов современной комбинаторики — теории геометрических графов. Основным объектом нашего исследования будет так называемый дистанционный граф (он же граф расстояний), вершины которого — это точки плоскости (или пространства более высокой размерности), а ребра — отрезки заданной длины. Этот объект весьма труден для исследования, и на многие — казалось бы, простые — вопросы о его свойствах нет окончательных ответов. Нас будут в первую очередь интересовать «экстремальные» характеристики графов расстояний. Среди них хроматическое число — минимальное количество цветов, в которые можно так покрасить вершины графа, чтобы вершины, соединенные ребром, были разноцветными; обхват — длина кратчайшего цикла в графе. Для отыскания этих характеристик мы познакомимся с основами линейно-алгебраического и вероятностного методов в комбинаторике. Кроме того, мы пронаблюдаем интересные связи между задачами комбинаторной геометрии и теории кодирования.
Бо́льшая часть материала будет доступна старшеклассникам. Приблизительная структура лекций следующая.
Лекция 1. Определение дистанционного графа. Простейшие свойства: число ребер в случае плоскости и пространства, хроматические числа в маленьких размерностях и др. Обхват дистанционного графа. Клики (полные подграфы) в дистанционных графах.
Лекция 2. Задача о наибольшей мощности совокупности $M=\{M_1,…,M_s\}$ подмножеств конечного множества с запретами на величины $|M_i\cap M_j|$. Линейно-алгебраический метод. Хроматические числа дистанционных графов в растущей размерности.
Лекция 3. Некоторые идеи теории кодирования. Построение дистанционных графов, не содержащих клик заданного размера и имеющих большое хроматическое число. Большое хроматическое число и большой обхват.
Лекция 4. Вероятностный метод. Уточнение результатов третьей лекции.
Цикл докладов

ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru
 
Обратная связь:
 Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2021