Адрес e-mail:

Математический практикум (осень 2020 - весна 2021)

Весенний семестр


25.05.2021 (зачет)

18.05.2021 (зачет)

11.05.2021

27.04.2021

13.04.2021

30.03.2021

23.03.2021

16.03.2021

09.03.2021

02.03.2021

16.02.2021


09.02.2021


02.02.2021



Осенний семестр


24.11.2020 (Семинар отменен)
  • О. Калиниченко "Перколяция в случайном графе"

Пусть G,H  – графы,а F – остовный подграф G. Будем говорить, что F слабо H-насыщаем в G, если в нем нет копий H, но к нему можно добавить в каком-то порядке недостающие ребра из G так, что при добавлении каждого нового ребра в графе появляется новая копия H (иными словами, существует H-перколяция из F в G). Числом слабого насыщения wsat(G,H) называется минимальное количество ребер в слабо H-насыщаемом графе в G. Впервые задача поиска числа слабого насыщения была сформулирована Боллобашем для полных G, H еще в 1968 году, а решена Ловасом лишь спустя 9 лет. В 2017 году Коранди и Судаков доказали стабильность числа слабого насыщения для полного графа (т.е. а.п.н. совпадение wsat(G(n,p),K_s) с ответом для полного графа K_n в случае константной вероятности проведения ребра p). Мы доказали общее утверждение, из которого следуют как результат Судакова и Коранди, так и стабильность  в случае некоторых других графов H и константного p.  Мы также находим пороговую вероятность для свойства стабильности в случае, когда H - звезда.
Доклад основан на совместной работе с М.Е. Жуковским.


17.11.2020
  • С. Киселев "Раскраски кнезеровских графов"

Кнезеровским графом KG(n, k) называется граф, чьи вершины -- k-элементные подмножества [n] = {1, ..., n}, и две вершины соединены ребром, если соответствующие множества не пересекаются. Известно, что хроматическое число такого графа равняется n - 2k + 2, при этом для доказательства нижней оценки используется раскраска, где для всех цветов, кроме одного, найдётся элемент x из [n], содержащийся во всех вершинах этого цвета. Будем называть такие цвета тривиальными. При анализе раскрасок кнезеровского графа часто возникает вопрос, существует ли раскраска без тривиальных цветов. В докладе я приведу примеры таких раскрасок и покажу, что при n > 8 k^2 раскрасок без тривиальных цветов не существует.


10.11.2020
  • Р. А. ван Беверн "Алгоритм Кристофидеса или алгоритм Кристофидеса-Сердюкова? История открытия и публикации"

Полный анонс
Одним из самых фундаментальных результатов в области комбинаторной оптимизации является полиномиальный 3/2-приближённый алгоритм для метрической задачи коммивояжёра. Он был представлен Никосом Кристофидесом в 1976 г. и хорошо известен под названием «алгоритм Кристофидеса». В последнее время некоторые авторы стали называть его «алгоритмом Кристофидеса-Сердюкова», утверждая, что он был опубликован независимо в СССР в 1978 г. В докладе будет рассказано об историческом контексте, в котором произошло параллельное и почти одновременное открытие ставшего всемирно известным алгоритма.


03.11.2020
Анонс


27.10.2020

Несмотря на простоту формулировки, задача Нельсона о вычислении хроматического числа плоскости все еще не решена, а с ростом размерности зазор между нижней и верхней оценками все увеличивается. В докладе я расскажу о некоторых близких вопросах. Что будет, если запретить одноцветность не единичных отрезков, а некоторых других, более сложных конфигураций? Что будет, если начать мерить расстояния между точкам по-другому?

Оказывается, что ответы на некоторые вопросы такого типа тесно связаны со следующей интересной задачей. Пусть дано некоторое конечное множество целых чисел. Насколько "экономно" можно покрыть целочисленную прямую, используя лишь копии данного множества?


20.10.2020

Будет рассказано о нескольких задачах, связанных с функциями распределения квадратичных форм и более общих многочленов от гауссовских случайных величин, т.е. с функциями вида P(F(x_1,…,x_n)<t), где F — квадратичная форма или многочлен от n переменных, x_i — гауссовские случайные величины, скажем, просто координаты в n-мерном пространстве, наделенном стандартной гауссовской мерой. Важный интересный частный случай — форма вида c_1 x_1^2+… +c_nx_n^2, т.е. хи-квадрат с весами. Случай 
одинаковых весов c_i=1 хорошо исследован и связан с одной из самых популярных в приложениях статистик. Все необходимые понятия будут введены, никаких сведений, 
выходящих за рамки курса анализа первого года, не требуется. Будет рассказано как о недавних достижениях в этом направлении, так и об открытых проблемах.

13.10.2020
Анонс


06.10.2020

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

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

Противодействие коррупции | Сведения о доходах

Политика обработки персональных данных МФТИ

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

Использование новостных материалов сайта возможно только при наличии активной ссылки на https://mipt.ru

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