Адрес e-mail:

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

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-2020 Московский физико-технический институт (национальный исследовательский университет)

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

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

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

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

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