Одним из главных принципов уникальной «системы Физтеха», заложенной в основу образования в МФТИ, является тщательный отбор одаренных и склонных к творческой работе представителей молодежи. Абитуриентами Физтеха становятся самые талантливые и высокообразованные выпускники школ всей России и десятков стран мира.

Студенческая жизнь в МФТИ насыщенна и разнообразна. Студенты активно совмещают учебную деятельность с занятиями спортом, участием в культурно-массовых мероприятиях, а также их организации. Администрация института всячески поддерживает инициативу и заботится о благополучии студентов. Так, ведется непрерывная работа по расширению студенческого городка и улучшению быта студентов.

Адрес e-mail:

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

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

25 апреля 2016 г. 
Алексей Балицкий
Будем говорить про одно обобщение теоремы Хелли, в котором пересечение любого поднабора множеств представляется в виде объединения не более k выпуклых.


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

18 апреля 2016 г.
Никита Чернега
Обсуждалась статья Гила Калая о неулучшаемом результате по дробной теореме Хелли. Оригинальная статья Калая называется "Intersection patterns of convex sets". Главная лемма Вегнера опубликована в статье "d-collapsing and nerves of families of convex sets".

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» .

Если вы заметили в тексте ошибку, выделите её и нажмите Ctrl+Enter.

© 2001-2016 Московский физико-технический институт
(государственный университет)

Техподдержка сайта

МФТИ в социальных сетях

soc-vk soc-fb soc-tw soc-li soc-li
Яндекс.Метрика