Просеминар по комбинаторной геометрии (2015 — 2016)

  • В этом семестре занятия будут проходить по понедельникам в аудитории 520 ГК. Время уточните у А.М.Балицкого. Семинары ведут Владимир Леонидович Дольников и Алексей Михайлович Балицкий.
  • Чтобы подписаться на рассылку семинара, напишите А.М.Балицкому или А.А.Полянскому.
  • По поводу всей литературы, которая используется на семинаре, обращайтесь к А.М.Балицкому или к А.А.Полянскому.
  • Почты: alexey_m39@mail.ru Алексей Михайлович Балицкий, alexander.polyanskii@yandex.ru Александр Андреевич Полянский
  • Задачи семинара http://www.papeeria.com/p/94e928df6222329375674bd3261c2d1e#/Задачи+семинара.tex

Предстоящие семинары:

27 марта 2016 г.
Никита Волков
Будет рассказано про дробную теорему Хелли для «коробочек», а также про схожие проблемы.
Никита Чернега
Будет рассказан про дробную теорему Хелли (усиленная версия полученная Гилом Калаи).

Прошедшие семинары:

21 марта 2016 г.
Владимир Леонидович Дольников
В докладе речь пойдёт о метрических теоремах отделимости — насколько должны быть удалены точки двух множеств (по сравнению с расстояниями внутри множеств), чтобы их можно было гарантированно разделить.

14 марта 2016 г.
Ринат Садыков
Были рассказаны следующие классические факты: цветная теорема Каратеодори (с доказательством И. Бараня) и теорема Тверберга (с доказательством К. Саркарьи). Также кратко обсуждались формулировки потенциальных обобщений теоремы Тверберга: цветная версия, топологическая версия.
С материалом можно ознакомиться по книге J. Matousek «Lectures on Discrete Geometry».

29 февраля 2016 г.
Алексей Балицкий
1) В восьмидесятых годах прошлого века Э. Борош и З. Фюреди, тогда ещё студенты, доказали следующую теорему.
Пусть на плоскости дано n точек общего положения. Тогда существует точка (не из числа данных), накрываемая случайным треугольником с вершинами в данных точках с вероятностью не менее 2/9-o(1).

Излагалось простое доказательство по Буху:
http://www.borisbukh.org/buckbuck.html

Другое несложное доказательство (но уже с топологическим флёром) можно найти в этой статье:
http://arxiv.org/pdf/1005.1392v1.pdf

Оно немного труднее первого, но зато обобщается для других ситуаций. Например, несложно обобщить его для доказательства «двойственной» теоремы: на плоскости даны прямые, и мы ищем точку, окружённую большой долей троек этих прямых. Это рассуждение можно увидеть здесь:
http://arxiv.org/pdf/1602.05073v1.pdf

Число 2/9 в теореме неулучшаемо, это пытались показать (но ошиблись в примере) и сами Борош и Фюреди. Правильный пример (и обсуждение неправильного) можно найти здесь:
http://arxiv.org/pdf/0804.4464.pdf

2) Также на семинаре обсуждалась следующая теорема Бороша—Фюреди—Бараня—Паха—Громова.

Пусть в \mathbb{R}^d даны абсолютно непрерывные вероятностные меры \mu_0, \ldots, \mu_d. Рассматривается случайный симплекс (x_0 \ldots x_d), вершины которого выбираются из распределений x_i \sum \mu_i. Тогда существует точка c такая, что вероятность накрытия этой точки случайным симплексом не меньше \frac{1}{(d+1)!}.

Эту теорему естественно рассматривать как многомерный «цветной» вариант теоремы Бороша—Фюреди (Барань впервые доказал многомерный результат, Пах рассмотрел «цветную» версию, Громов доказал ещё более общий топологический вариант).

Излагалось доказательство по статье Карасёва:
http://arxiv.org/pdf/1012.5890v2.pdf

Небольшое усиление оценки (в целом, по мотивам доказательства Карасёва) можно найти тут:
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p39

22 февраля 2016 г.
Ринат Садыков
Речь на семинаре шла о некотором обобщении теоремы Семереди—Троттера для алгебраических кривых (т.е. о теореме о числе инциденций между n точками и m кривыми ограниченной степени), а также о том, как можно подобную теорему применить в задаче о числе различных расстояний между точками на двух прямых. Был доказан следующий факт: есть две неортогональные прямых, на каждой из них выбрано по n точек, тогда число различных расстояний образованных парами точек, расположенных на различных прямых, по крайней мере O(n^{4/3}).
На следующей страничке можно найти больше информации о подобных фактах (обсуждавшиеся факты изложены в частях 3 и 6 записок лекций).
http://math.caltech.edu/~2014-15/3term/ma191c-sec2/

15 февраля 2016 г.
Александр Зайков
Будет рассказано про книгу J. Matousek «33 miniatures; applicatiions of linear algebra» и продолжение одной из миниатюр.
Книга: http://kam.mff.cuni.cz/~matousek/stml-53-matousek-1.pdf
Миниатюра 12. Почему прямоугольник с иррациональным соотношением сторон нельзя замостить квадратами (идея: рассмотрение \mathbb{R} как векторного пространства над \mathbb{Q} и построение удачного линейного функционала).
Миниатюра 13. Почему клику на десяти вершинах нельзя покрыть тремя графами Петерсена (идея: линейная алгебра над матрицами смежности).
Миниатюра 16. Сколько гиперплоскостей требуется, чтобы накрыть все вершины единичного куба, кроме одной (идея: combinatorial Nullstellensatz).
Миниатюра 20. Лемма Штайница про упорядочение векторов, чтобы частные суммы были невелики (идея: удачное индукционное утверждение плюс рассмотрение крайних точек полиэдра — множества решений системы линейных неравенств).

8 февраля 2016 г.
Александр Андреевич Полянский
1. Теорема о числе треугольников на плоскости, если проведено n прямых.
Основано на статье А.Я. Белова:
http://www.mathnet.ru/links/0b0b6a6dd48dee95f4980458c31a2488/rm4516.pdf
Также подробный разбор этой статьи можно прочитать по ссылке.
http://kvant.mccme.ru/1992/11/treugolniki_i_katastrofy.htm
2. Доказательство теоремы Семереди-Троттера с помощью полиномиального метода. См. оригинальную статью Каплана, Матушека, Шарира:
http://arxiv.org/abs/1102.5391
Подробный разбор этой статьи можно найти по ссылке
http://www.turgor.ru/lktg/2014/7/index.htm
Другой вероятностный путь доказательства см. в лекциях Адама Шефера (1 лекция):
https://adamsheffer.wordpress.com/2015/04/15/polynomial-method-lecture-notes/
Третий путь доказательства («элементарный», но не значит, что простой) можно найти в книге J.Matousek «Lectures on discrete geometry» (4 глава).

7 декабря 2015 г.
Никита Чернега
1. Применение discharging method для доказательства линейного количества ребер в 3-квази-планарных графах. Статья Акермана и Тардоша:
http://sci.haifa.ac.il/~ackerman/publications/3quasi.pdf
Обзор-введение в discharging method в комбинаторной геометрии (на странице Википедии найти ссылку на обзор Hilneny):
https://en.wikipedia.org/wiki/Discharging_method_(discrete_mathematics)

30 ноября 2015 г.
Никита Волков
1. Результаты по замощениям тетраэдров. Статьи:
http://tetrahedraverse.com/tverse/packings/temp2/tetraspace.pdf
http://www.ams.org/notices/201211/rtx121101540p.pdf?hc_location=ufi

Алексей Михайлович Балицкий
1. Задача об оценке углов тетраэдра: правда ли, что в любом тетраэдре есть трёхгранный угол с телесным углом не больше, чем в правильном тетраэдре? Ответ — да (в размерности 3), доказательство использует следующие идеи:

  • полярная двойственность на сфере (прокомментирована);
  • формула Крофтона (прокомментирован и был дан набросок доказательства);
  • изопериметрия для сферических треугольников (не доказано,, см. ссылки в статье ниже).

Статья А.Акопяна и Р.Карасева (в статье есть ошибка в доказательстве теоремы для размерности 4):
http://arxiv.org/abs/1505.05263
2. Cформулирована центральную трансверсальную теорему Владимира Леонидовича Дольникова, обсуждались её крайние случаи (Rado’s centerpoint theorem, Ham sandwich theorem).
Упражнение: доказать теорему о центральной точке (в $\mathbb{R}^d$ дано семейство точек и нужно доказать существование такой точки, необязательно из семейства, что любое полупространство, содержащее её, будет содержать и хотя бы $\frac{1}{1+d}$ точек из семейства).
Хороший источник, по которому можно ознакомиться с топологической техникой в комбинаторике и дискретной геометрии — замечательная книга J.Matousek «Using the Borsuk—Ulam theorem».

23 ноября 2015 г.
Михаил Григорьев
1. Выпуклые разбиения плоскости.
Задачи:
(М.Григорьев) Какую долю заданной «хорошей» меры на плоскости можно гарантированно вырезать выпуклыми множеством, не задевающим заданные $n$ точек. Для четных было получено точное значение. Для нечетных $n$ было показано, что оптимальная доля лежит в отрезке $\left[\dfrac{2}{n+3}; \dfrac{2}{n+2}\right]$. Поэтому данный вопрос остается открытым.
2. (В.Л.Дольников) Какое минимальное число точек должно быть брошено в $\mathbb{R}^3$, чтобы семейство выпуклых оболочек всех поднаборов из $r$ точек нельзя было пересечь одной прямой? Ответ дать в зависимости от $r$.

16 ноября 2015 г.
Алексей Михайлович Балицкий
1. Теорема Дуаньона. Доказательство можно найти в книге A.Schrijver «Theory of Linear and Integer» (с.234).
Про прямолинейное количественное обобщение теорема Дуаньона можно прочитать в статье Де Лоеры: http://arxiv.org/abs/1405.2480

9 ноября 2015 г.
Алексей Михайлович Балицкий
1. Базовые теоремы о выпуклости (теоремы Каратеодори, Радона, Хелли). Их можно найти в книге А.Барвинока.
2. Теорема Штейница (аналог теоремы Каратеодори о точке, находящейся во внутренности выпуклой оболочки).
3. Теорема Дуаньона — теорема типа Хелли для целочисленных точек (без доказательств). В следующий раз будет рассказана подробно.
Ринат Садыков.
1. Смешанные теоремы типа Хелли-Дуаньона. Статья Аверкова и Вайсмантела: http://arxiv.org/pdf/1002.0948v2.pdf

2 ноября 2015 г.
Алексей Михайлович Балицкий
Базовые понятия выпуклой геометрии.
1. Поляра к множеству, выпуклая двойственность.
2. Неравенство Бляшке—Сантало и гипотеза Малера.
3. Эллипсоид Джона, его свойства. Симметричный случай можно найти в следующей книге: K.Ball «Elementary Introduction to Modern Convex Geometry» http://library.msri.org/books/Book31/files/ball.pdf
Рекомендованная литература: А.Barvinok «A Course in convercity» (написана достаточно просто и понятно, можно найти большинство рассказанных фактов), P.M.Gruber «Convex and Discrete Geometry» (скорее экнциклопедического типа).

26 октября 2015 г.
Саша Зайков
1. Было рассказано доказательство гипотезы Барани-Качальского-Паха о теореме Хелли для объемов. Статья Мартона Надзоди:
http://arxiv.org/pdf/1503.07491.pdf
При доказательтсве использовались

  • Эллипсоид Джона
  • Теорема Штейница (аналог теоремы Каратеодори о точке, находящейся во внутренности выпуклой оболочки).
  • Теорема Дворецкого

Последние можно найти в книге K.Ball «Elementary introduction to Modern Convex Geometry» .