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

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

Адрес e-mail:

Межкафедральный семинар

В весеннем семестре 2013/2014 года заседания межкафедрального семинара проходили в Долгопрудном по средам в 18:30 - 20:00 в аудитории Актовый зал. Семинар проводится совместно с кафедрой математических основ управления ФУПМ МФТИ и кафедрой высшей математики МФТИ.

Научный семинар поддержан Лабораторией структурных методов анализа данных в предсказательном моделировании (ПреМоЛаб), МФТИ, грант правительства РФ дог. 11.G34.31.0073.

Вы можете подписаться на RSS-ленту или трансляцию в ЖЖ этого и других близких по тематике семинаров на сайте http://combalg.ru/seminars.

Прошедшие заседания:

29 апреля 2014 г. (115 КПМ
J.H. Kim «A tale of models for random graphs» 
Since Erdős and Rényi introduced random graphs in 1959, two closely related models for random graphs have been extensively studied. In the G(n,m) model, a graph is chosen uniformly at random from the collection of all graphs that have n vertices and m edges. In the G(n,p) model, a graph is constructed by connecting each pair of two vertices randomly. Each edge is included in the graph G(n,p) with probability p independently of all other edges. Researchers have studied when the random graph G(n,m) (or G(n,p), resp.) satisfies certain properties in terms of n and m (or n and p, resp.). If G(n,m) (or G(n,p), resp.) satisfies a property with probability close to 1, then one may say that a `typical graph’ with m edges (or expected edge density p, resp.) on n vertices has the property. Random graphs and their variants are also widely used to prove the existence of graphs with certain properties. In this talk, a well-known problem for each of these categories will be discussed. First, a new approach will be introduced for the problem of the emergence of a giant component of G(n,p), which was first considered by Erdős–Rényi in 1960. Second, a variant of the graph process G(n,1),G(n,2),…,G(n,m),… will be considered to find a tight lower bound for Ramsey number R(3,t) up to a constant factor. No prior knowledge of graph theory is needed in this talk.


16 апреля 2014 г. 
А. Акопян «Теорема Киршбрауна о сжимающих отображениях» 
В докладе будет рассказано о теореме Киршбрауна о сжимающих отображениях, которая утверждает, что любое отображение [latex]f[/latex] из [latex]X \subset R^d[/latex] в [latex]R^d[/latex], которое не увеличивает расстояние между точками, может быть доопределено на всё пространство [latex]R^d[/latex] с сохранением этого свойства. Будут приведены некоторые следствия из этой теоремы и её связи с задачами оригами. 

26 марта 2014 г.
А.М. Вершик «Комбинаторика путей градуированного графа и ее применения в анализе и алгебре»
Граф, градуированный неотрицательными целыми числами (диаграмма Браттели), или, что то же самое, дискретная марковская цепь с конечным множеством состояний, - это наиболее важный объект современной асимптотической комбинаторики. Пространство путей такого графа есть марковский компакт, а число путей, ведущих в данную вершину (обобщенный биномиальный коэффициент), есть важнейшая числовая функция. Для графа Паскаля эти числа суть обычные биномиальные коэффициенты, а для графа Юнга - размерности представлений симметрической группы.
В докладе будет рассказано о различных задачах, связанных с этими понятиями, — адическое преобразование на пространстве путей, внутренняя метрика, предельная форма и др. Все необходимые для понимания доклада понятия будут определены. Также будут поставлены некоторые задачи.

12 марта 2014 г.
Семинар отменен

05 марта 2014 г. (семинар пройдет в 202НК)
А. Балицкий «Финслеровы бильярды в выпуклых телах»
Нетрудно представить себе материальную точку (бильярдный шар), движущуюся внутри выпуклого тела (бильярдный стол) и отражающуюся от границы тела по правилу «угол падения равен углу отражения». Это понятие можно математически формализовать, что приводит к конструкции некоторой динамической системы (которую можно считать гамильтоновой) с разными интересными свойствами.
Достаточно давно (начиная с Биркгофа в начале 20-го века) изучаются бильярды, и в частности, изучаются замкнутые бильярдные траектории на плоскости и в больших размерностях.  Недавно Шири Артштайн-Авидан и Ярон Островер интерпретировали минимальную длину бильярдной траектории в терминах инварианта «симплектическая ёмкость», установив таким образом связь с новой и интересной наукой «симплектическая геометрия». При этом оказалось полезно рассматривать бильярды не только в евклидовой норме, но и в произвольной не обязательно рефлексивной финслеровой норме.
В докладе будет рассказано про правило отражения для бильярдов в произвольной норме, характеризацию (по Бездеку и Бездеку) длины минимальной замкнутой траектории и оценки этой длины в некоторых полезных случаях. Значительная часть обсуждаемых результатов может быть доказана (и изначально была доказана) методами симплектической геометрии, но будет изложена элементарными средствами.

26 февраля 2014 г.
О.Н. Герман «Некоторые вопросы мультипликативной теории чисел»
Пусть заданы n линейно независимых линейных форм в d-мерном евклидовом пространстве. Один из основных вопросов мультипликативной теории чисел заключается в том, насколько "малым" может быть произведение значений этих линейных форм на целочисленной решетке. Мы поговорим о мультипликативных диофантовых экспонентах, о теоремах переноса, о спектре Морделла-Грубера, о мультипликативных обобщениях плохо приближаемых чисел, о многомерной теореме Дирихле, а также о гипотезах Литтлвуда и Оппенгейма.

19 февраля 2014 г.
А.А. Полянский «Гипотеза Шура в [latex]\mathbb{R}^d[/latex]»
Граф диаметров в [latex]\mathbb{R}^d[/latex] --- граф вершинами которого являются конечное множество точек в [latex]\mathbb{R}^d[/latex], а ребрами являются пары точек находящихся на расстоянии равном диаметру. Гипотеза Шура утверждает: максимальное число полных подграфов размера d (d-клик) в графе диаметров на n вершинах в d-мерном евклидовом пространстве равно n. В работе З. Шура, М.А. Пёлеса, X. Мартини, Я.С. Купитза гипотеза Шура была доказана для d=3. Кроме того, в этой же работе было доказано, что в графе диаметров множества в d-мерном пространстве не более одной (d+1)-клики. Дальнейшее продвижение в гипотезе Шура получили Ф. Мориц и Я. Пах. Они доказали, что если в графе диаметров на n вершинах в d-мерном пространстве любые две d-клики имеют не менее d-2 общих вершин, то число d-клик  в этом графе не превосходит n. Не так давно А.Б. Купавским и А.А. Полянским была доказана гипотеза Шура в общем случае. А.А. Полянский расскажет план доказательства в случае [latex]\mathbb{R}^d[/latex], которое можно обобщить и на большие размерности.

 

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

11 сентября 2013 г.
А.Я. Канель-Белов, П. Лавров «Оценка количества запретов необходимых для задания периодического слова»
Слово ..abababa.. можно однозначно с точностью до сдвига задать запретив подслова {aa, bb}, слово ..aabaab.. - {aaa, bb, bab}
Исследуется зависимость длины наименьшего периода от количества запретов.
(понятно, что период характеризует сложность слова, а размер системы запретов - сложность его описания)
Получена точная (с примером) оценка для количества запретов слов в двухсимвольном алфавите {a, b}:
[latex]|S| >= log_\alpha(n)[/latex], где S - запреты, n - наименьший период слова,
[latex]\alpha = \frac{1+\sqrt(5)}{2}[/latex] - золотое сечение,
а также асимптотическая - с точностью до константы - в случае
k-буквенного алфавита
([latex]|S| >= log_\alpha(n)-C(k)[/latex]), которая, как легко показывается - тоже точна.
В решении строится последовательность графов, связанных некоторыми правилами эволюции, размер конечного из которых равен периоду слова и оценивается их рост в процессе эволюции.

18 сентября 2013 г.
А.В. Савватеев «Равновесия Нэша-Роллса в неатомарных играх с поиском коалиционной структуры: общая теорема существования»
Будут представлены новые результаты в теории многомерного размещения.
Конкретно, будет доказана общая теорема существования миграционно-устойчивого разбиения на клубы при уравнивающем способе распределения издержек, а также показана потенциальность (в обобщённом смысле) игры размещения с принципом равнодолевого участия.

25 сентября 2013 г.
Д. Малышев «Исследование "критических" наследственных классов в анализе вычислительной сложности задач на графах»
Развитие теории сложности вычислений способствовало укоренению
пессимистического взгляда на возможность существования эффективных
(полиномиальных) алгоритмов для многих задач на графах, представляющих практический и/или теоретический интерес. Одним из возможных способов преодоления алгоритмической сложности таких задач является сужение, т.е. наложение дополнительных ограничений на класс рассматриваемых графов. Иногда учет этих ограничений, т.е. принадлежности графа некоторому классу, приводит к созданию полиномиального алгоритма для решения задачи. В других случаях удается доказать, что задача для графов из того или иного класса остается NP-полной. К настоящему времени накоплено огромное количество фактов того и иного рода. Придать этому процессу целенаправленность и систематичность можно, переходя от рассмотрения отдельных классов к рассмотрению представительных семейств классов. В докладе будут изложены результаты подготовленной докторской диссертации по поиску «линии водораздела» между «простыми» и «сложными» элементами семейства наследственных классов графов.

2 октября 2013 г.
О.Р. Мусин «Дискретные аналоги теорем Брауэра и Борсука-Улама»
Знаменитая теорема Брауэра утверждает, что любое непрерывное отображение замкнутого круга (шара) в себя имеет неподвижную точку. Эта теорема имеет огромное число приложений. Вторая, не менее знаменитая теорема, - теорема Борсука - Улама. Эта теорема неформально известна как «теорема о температуре и давлении»: в любой момент времени на Земле найдутся две диаметрально противоположных точки с равной температурой и равным давлением.
У этих двух теорем имеются дискретные аналоги - это леммы Шпернера и Таккера о раскрашивании вершин триангуляций. (Имеются элементарные доказательства лемм, которые не требует "продвинутой" математики и доступны даже школьникам старших классов.)
В докладе мы собираемся обсудить различные обобщения этих лемм и их доказательства.

16 октября 2013 г.
В. Беляев «Провалы в бесконечности»
Изучая некоторые бесконечные математические структуры, мы сталкиваемся с интересным явлением – отсутствием структур промежуточной сложности, то есть в исследуемом классе объектов присутствуют либо сложные, либо относительно простые структуры. В математике нет единого, универсального языка, на котором может быть описано указанное явление. Одним из наиболее распространенных понятий, формализующих понятие «сложности», и с помощью которого могут быть описаны некоторые известные нам «провалы» является понятие функции роста связного графа, конечнопорожденной группы и т.д.
Исследованиям «роста» групп и графов посвящено достаточно большое количество работ и в первой половине лекции речь пойдет о «провалах в бесконечности», описываемых в терминах функций роста. Примерное содержание этой части лекции следующее: рост римановых многообразий и альтернатива Милнора для функций роста конечнопорожденных групп. Группы полиномиального, экспоненциального и промежуточного ростов. Функции роста симметрических графов. Проблемы классификации симметрических графов полиномиального роста и кристаллических решеток. Рост конечных симметрических групп и проблема сортировки на графах.
Вторая половина лекции будет посвящена аналогичному явлению «провала в бесконечности», но которое уже не может быть описано в терминах функций роста. Речь будет идти о строении некоторых подгрупп бесконечных симметрических групп. Подстановка некоторого множества называется финитарной, если она сдвигает с места лишь конечное число точек. Оказывается, подгруппа, порожденная произвольным множеством финитарных подстановок либо содержит «почти каждую» финитарную подстановку, либо имеет очень ограниченное строение. Это явление было названо «финитарной дихотомией», а вокруг этого явления появился ряд интригующих проблем, которые не могут быть решены вот уже около 40 лет, несмотря на усилия многих алгебраистов. 

6 ноября 2013 г.
В.А. Шлык «Полиэдральный подход в теории разбиений чисел: результаты и новые проблемы»
Теория разбиений натуральных чисел ­­на натуральные слагаемые – классическое направление в теории чисел и комбинаторике. В ее создании участвовали Эйлер, Лежандр, Коши, Гаусс, Юнг, Макмагон, Харди, Рамануджан, Радемахер, Эрдёш.
Поток статей, посвященных разбиениям чисел, не ослабевает и сейчас. Разбиения чисел находят применения в различных областях математики,в статистической механике и современной физике.
В докладе излагаются результатыполиэдрального подхода к исследованию разбиений чисел. Благодаря представлению множества разбиений числа n в виде ограниченного многогранника в n-мерном пространстве, обнаруженыего комбинаторно-геометрическая структура, новые классы разбиений и отношения между ними. Основными элементами любого многогранника являются его вершины и грани максимальной размерности. Грани многогранника разбиений полностью охарактеризованы, но описание его вершин остается открытой проблемой.
Особый интерес к ней объясняется тем, что вершины многогранника образуют базис множества разбиений соответствующего числа, поскольку остальные разбиения являются их выпуклыми комбинациями. Более того, оказалось, что этот базис можно уменьшить, так как все вершины можно получить из подмножества опорных вершин с помощью простых комбинаторных операций. Другие результаты о строении многогранникаразбиений говорят осмежности вершин, о связях между вершинами и содержащими их гранями, а также о связи вершин с известными структурами аддитивной комбинаторики.
Специальное внимание уделяется новым задачам, порожденным полиэдральным взглядом на множества разбиения чисел. Одна из главных проблем – описание зависимости числа вершин многогранника от разбиваемого числа. Результаты вычислений вершин и опорных вершин для многогранниковразбиениймалых чисел говорят о том, что их число существенно меньше числа всех разбиений – примерно 59 и 7 тысяч, соответственно, против 190 миллионов для n = 100. Однако число вершин растет не монотонно с ростом n: похоже, что онозависит от теоретико-числовых свойствn. Знаменитую асимптотическую формулу для числа разбиенийnХарди и Рамануджан доказали спустя 20 лет после того, как Макмагонвычислил эти числа для всех n ≤ 200. Возможность применения компьютера позволяет надеяться, что для числа вершин это удастся сделать скорее.
Основное содержание доклада будет понятно студентам, изучающим дискретную математику и склонным к комбинаторному мышлению.

13 ноября 2013 г.
П. Кожевников «О сложности объединения и пересечения многоугольников»
Для практических приложений важно оценивать сложность операции пересечения/объединения фигур на плоскости, ограниченных замкнутым ломаными без самопересечений. Если фигуры выпуклые, то сложность пересечения находится легко. Однако, если фигуры не являются выпуклыми, то задача становится более содержательной. В докладе будут обсуждаться известные  оценки сложности пересечения фигур, в частности точные оценки для сложности пересечения двух многоугольников с данным количеством вершин, в которых угол больше/меньше развернутого.

27 ноября 2013 г.
А.Я. Канель-Белов «Комбинаторика слов, квантовая теория малых сокращений и проблемы теории колец»
Известно, что если групповое слово записать по кругу (например, [latex]aba^{-1}b^{-1}[/latex]) то получится класс сопряженности, ибо результат записи по кругу слов [latex]u[/latex] и [latex]aua^{-1}[/latex] совпадают. Соотношения в группах изображаются классами сопряженности элементов. Процедуре вывода соотношений отвечает выкладывание мозаике. В ряде случаев алгоритм проверки равенства слова единицы базируется на следующей конструкции: слово записывается по кругу и мы пытаемся сократить его длину с помощью определяющего соотношения. На этом базируется техника Ольшанского (см. "Комбинаторика определяющих соотношений").
До самого последнего времени аналогичная техника  для работы с кольцами была неизвестна. Совсем недавно такая техника появилась. К счастью, она оказалась элементарной и есть надежда решить ряд задач теории колец, к чему публика и приглашается.

11 декабря 2013 г.
И.И. Богданов «О связи хроматического числаграфа и хроматических чисел окрестностей его вершин»
Какие ограничения локальная структура графа накладывает на его глобальные свойства? Одному из вопросу такого плана посвящён наш доклад. Именно, пусть окрестность любой вершины графа (фикстрованного радиуса) имеет небольшое хроматическое число; что тогда можно сказать про хроматическое число всего графа? (Окрестность понимается в графском, смысле: этомножество всех вершин, соединённыз путями ограниченной длины с центром.) При отсутствии ограничений на размер графа ничего сказать нельзя; в докладе этот вопрос исследуеется в зависмости от количества вершин графа.

18 декабря 2013 г.
А.А. Разборов «Непрерывная комбинаторика»
Дискретная математика задумывалась и затем развивалась в течении столетий как наука о конечном. Однако во многих (если не в большинстве) современных приложений фигурируют структуры хотя всё ещё и конечные, но не просто большие, а очень большие. При этом изучаемые числовые характеристики таких структур как правило обладают определёнными свойствами "непрерывности": при "небольшом" изменении самой структуры значение рассматриваемой характеристики меняется "не слишком". В такой ситуации весьма естественно попытаться осуществить предельный переход и непосредственно рассматривать бесконечные аналоги. Это в самом деле оказывается возможным и приводит к красивой и стройной теории, связанной со многими другими вещами в математике и теоретической информатике.
Два различных, но взаимосвязанных подхода к построению такой теории известны под названием пределов графов (graph limits) и алгебры флагов (flag algebras), и в своём докладе я постараюсь немного рассказать об обоих.


 

Заседания 2012/2013 учебного года 

 
Заседания 2011/2012 учебного года 

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

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

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

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

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