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

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

Адрес e-mail:

Кафедральный научно-исследовательский семинар: заседания 2012/13 года

 

Заседания кафедрального семинара проходят по вторникам с 18:30 до 20:00 в аудитории "7 Чудес" в Яндексе (м. Парк культуры, ул. Льва Толстого, д. 16).

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

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

30 апреля 2013 г.
А.Е. Ромащенко «Про Гёделя, Чейтина, и пользу от случайных аксиом»


23 апреля 2013 г.
Д.А. Шабанов «Теорема Хайнала-Семереди и ее обобщения»
В докладе будет рассказано об одном из фундаментальных результатов теории графов (и комбинаторики в целом) - теореме Хайнала - Семереди. Она утверждает, что если G - граф с максимальной степенью вершины D, то для G существует справедливая раскраска множества вершин в D+1 цвет. Справедливая раскраска - это правильная раскраска вершин графа, в которой все цветовые классы имеют почти одинаковую мощность (любые два из них по мощности могут отличаться не более чем на единицу). Легко видеть, что в этом случае граф-дополнение \overline{G} распадается в объединение непересекающихся по вершинам клик почти одинакового размера.
В докладе мы рассмотрим различные обобщения теоремы Хайнала - Семереди, особо уделив внимание относительно недавнему результату Л. Лу и Л. Секеи, которые получили аналог знаменитой теоремы Эрдеша - Ловаса для случая справедливых раскрасок однородных гиперграфов. Их доказательство использует вариант Локальной леммы для отрицательно коррелированных наборов событий произвольного вероятностного пространства.


16 апреля 2013 г.
А. Кустарев «Действия окружности на восьмимерных многообразиях, имеющие ровно три неподвижные точки»
Мы обсудим квадратичные диофантовы уравнения, возникающие в чисто топологических задачах - таких, как описание действий окружности на гладких ориентируемых многообразиях с фиксированным числом изолированных неподвижных точек.


9 апреля 2013 г.
И. Хузиев «Квантовое блуждание в графах Кэли»
Будет рассмотрено понятие квантового блуждания в графах Кэли (в особенности над конечными абелевыми группами), будут получены оценки на время возвращение в графах Кэли над группой Z_2^n с симметричной системой образующих.


2 апреля 2013 г.
А.А. Приходько «Сложность и спектральные свойства некоторых динамических систем комбинаторного происхождения»
Динамическую систему, заданную сохраняющим меру преобразованием с конечной энтропией, можно ассоциировать со случайным процессом, генерирующим бесконечное слово над конечным алфавитом A. Определяет ли спектральный тип системы комбинаторную структура процесса и насколько сложна задача о вычислении спектрального типа?
Мы исследуем эти вопросы на примере нескольких систем символической динамики.


19 марта 2013 г.
А. Клименко «Эргодические теоремы для действий марковских групп»
Эргодическая теорема для действия какой-нибудь группы G утверждает следующее: если G действует сохраняющими меру преобразованиями на некотором вероятностном пространстве, то для любой функции f последовательность взвешенных сумм её образов под действием элементов группы сходится к некоторой функции, инвариантной относительно действия группы.
Различные группы требуют различных последовательностей усреднений. Например, для аменабельной группы G можно взять некоторое исчерпание G множествами F_n и в качестве n-й взвешенной суммы брать среднее арифметическое f(g(x)) по всем g из F_n.
Для "больших" групп, например, свободной группы, такой способ применим плохо.
В докладе будет рассказано, какой способ усреднения годится для марковских групп - некоторого класса групп, включающего в себя, например, все гиперболические группы.


12 марта 2013 г.
С.С. Галкин «Мутации и квантование случайных блужданий»
Оказывается, что некоторые пары случайных блужданий в размерности >1 неотличимы с точки зрения бармена (наблюдателя в фиксированной точке).
Такие примеры получаются мутациями друг дружки, и геометрически соответствуют специальным бирациональным преобразованиям тора. В размерности 2 из трех эквивалентных в этом смысле мутаций можно настроить бесконечно много других.
Кроме того, все вышеперечисленное в размерности два имеет интересное и осмысленное поднятие на квантовый тор.


5 марта 2013 г.
И. Колесниченко «Динамическая задача транзитивного замыкания графа»
Одной их самых естественных задач для направленных графов является поиск транзитивного замыкания. В динамической версии данной задачи, имеется некоторый граф и набор запросов на удаление/добавление ребер и достижимость в графе. Требуется построить алгоритм, который будет эффективно отвечать на указанные запросы. Наиболее интересен случай, когда на запрос достижимости требуется отвечать за время O(1). Очевидным решением является перестроение матрицы транзитивного замыкания при каждом запросе на вставку/удаление. Время работы такого алгоритма ограничено временем умножения двух матриц (то есть O(n^2.376). В докладе же будет разобран алгоритм V. King, который позволяет совершать операции вставки и удаления за учетное время O(n^2 log(n)). Возможно, также будет рассказана одна из работ J. Italiano над этой задачей.


26 февраля 2013 г.
Д.В. Мусатов «Колмогоровские экстракторы с ограничением на память»
Экстракторами называются функции, извлекающие "новую" или "улучшенную" случайность из тех или иных источников. При классической формализации под источником случайности понимается распределение вероятностей, а под мерой качества случайности - мин-энтропия на входе экстрактора и статистическое расстояние до равномерного распределения на выходе. В последние несколько лет развилась другая формализация - колмогоровская. Здесь под источником случайности понимается конечное слово из нулей и единиц, а под мерой случайности - её колмогоровская сложность. В работах Зиманда было доказано существование колмогоровских экстракторов с почти оптимальными параметрами.

В докладе мы распространим определение колмогоровского экстрактора на сложность с ограничением на память и покажем, как доказательство Зиманда можно обобщить на этот случай.


11 декабря 2012 г. 18:30 - 20:00
А.Б. Скопенков «Алгоритмы распознавания реализуемости гиперграфов»
Хорошо известно, что существует быстрый (точнее -- линейный) алгоритм, определяющий, вложим ли данный граф в плоскость, т.е., можно ли граф расположить на плоскости так, чтобы его ребра не пересекались и не самопересекались.

Мы рассмотрим аналогичную задачу для гиперграфов в пространствах произвольной размерности: как распознать вложимость $n$-мерного гиперграфа (т.е. симплициального комплекса) в $m$-мерное пространство?

Будет намечено доказательство того, что при $6< 2m < 3n+3$ указанная проблема распознавания вложимости является NP-трудной (Matousek et al, http://arxiv.org/abs/math/0807.0336). Таким образом, скорее всего, быстрых алгоритмов для ее решения не существует. (Для доказательства будет показано, как некоторая заведомо NP-трудная проблема о булевых функциях сводится к проблеме распознавания вложимости.) Будет рассказано о разработке быстрого алгоритма распознавания вложимости при $2m \ge 3n+3$, а также о близкой задаче --- алгоритмическом распознавании заузленности.

Будет дан популярный обзор с основными идеями доказательств, доступными неспециалистам (в первую очередь студентам). Все необходимые определения (гиперграф, вложимость) будут напомнены. Основные идеи будут представлены на `олимпиадных' примерах: размерности не выше 3 и на простейших частных случаях, свободных от технических деталей.


27 ноября 2012 г. 18:30 - 20:00
А.А. Вороненко «Теория бесповторных функций»
В докладе рассматриваются результаты исследований, возникших из 3невырожденной задачи тестирования бесповторных функций, проводившихся рядом исследователей в период 2002-2012 гг.


20 ноября 2012 г. 18:30 - 20:00
Е.В. Дашков «Алгебры доказуемости теорий с определением истинности»
Формальным теориям, в том числе и связанным с математической практикой, как, например, арифметика Пеано PA, можно ставить в соответствие ординальные числа, некоторым образом выражающие "силу" этих теорий. Согласно классическому результату Генцена, при выборе определенной примитивно рекурсивной системы ординальных обозначений оказывается, что PA доказывает схему трансфинитной индукции до любого $\alpha < \epsilon_0$, однако из этой же схемы для $\epsilon_0$ получается непротиворечивость самой PA.

Принципиально, какое именно вполне упорядочение выбирается. Например, можно построить примитивно рекурсивное вполне упорядочение типа всего лишь $\omega$, такое что индукция по этому упорядочению даст нам непротиворечивость PA. Это же построение проходит для многих теорий, строго сильнее или слабее PA.

Таким образом, возникает проблема отыскания некоей канонической системы ординальных обозначений, которая позволила бы осмысленным образом приписывать теориям ординалы.
Л. Д. Беклемишев предложил извлекать системы ординальных обозначений из связываемого с теорией естественного объекта: т.н. алгебры доказуемости, т.е. алгебры Линденбаума, обогащенной особыми операторами доказуемости. В рамках этого подхода им, в частности, было получено новое доказательство непротиворечивости PA.

Дальнейшее развитие предполагает анализ более сильных теорией, в частности, различных подсистем арифметики второго порядка. Такие теории удобно представлять с помощью расширений PA предикатами истинности по Тарскому. Кроме того, эти расширения интересны и сами по себе.

Изучением их алгебр доказуемости я теперь, в основном, и занимаюсь.


4 декабря 2012 г. 18:30 - 20:00
А.А. Глибичук «Квази-полиномиальная теорма Фреймана-Ружи» 
Знаменитая полиномиальная гипотеза Фреймана-Ружи утверждает, что если $A$ - подмножество произвольной абелевой группы со свойством $|A+A|\le k|A|$, то есть имеет малое удвоение, то оно содержит полиномиально большое подмножество $A^{'}\subset A, |A^{'}|>|A|/K^ {C}$, где $C$ --- абсолютная константа, такое, что оно содержится в обобщенной прогрессии полиномиальной размера (в отличии от самого $A$, которое может, вообще говоря, содержаться в прогрессии экспоненциального размера от $K$). В 2010 году Т. Сандерс получил наилучший известный в настоящее время результат по гипотезе Фреймана-Ружи. В его оценке вместо полиномов стоит $K^{\log^6(K)}$. Позже Шахар Ловетт значительно упростил доказательство Сандерса и немного улучшил его результат (до $K^{\log^3(K)}$) в случае, когда $A$ - подмножество пространства $\mathbb{F}_2^{n}$. Цель доклада - изложить элегантное доказательство Ловетта и объяснить интересную технику Крута-Сисака, которая, по-существу, и дает результат Т. Сандерса.


23 октября 2012 г. 18:30 - 20:00
М.Е. Жуковский «Законы нуля или единицы»
В докладе будет рассказано про предельные свойства вероятностей свойств первого порядка случайных графов Эрдеша-Реньи. Основная часть доклада посвящена случаю p=exp(-a lnN), где p - вероятность ребра, а N - количество вершин графа. Будет рассказано, при каких значениях параметра a выполнен закон нуля или единицы, а также при каких значениях параметра a выполнен закон нуля или единицы существуют пределы вероятностей свойств в зависимости от ограничения, накладываемого на кванторную глубину формул.


16 октября 2012 г. 18:30 - 20:00. Доклад был в МГУ на семинаре Адяна - Беклемишева (ауд. 16-04).
А.Б. Купавский «Дистанционные графы с большим обхватом и большим хроматическим числом»
Эрдеш в 1959 году доказал, что для любых натуральных l и k существуют графы с хроматическим числом, большим k и с длиной наименьшего цикла (обхватом), большим l. В своем докладе я докажу, что для любого l существует последовательность дистанционных графов с обхватом больше l, у которых хроматическое число растет как (c+о(1))^n, где c>1, а n это размерность пространства.


9 октября 2012 г. 18:30 - 20:30
Д.А. Шабанов «Два подхода к получению оценок в теореме Ван дер Вардена»
Знаменитая теорема Ван дер Вардена утверждает, что любых натуральных n>2, r>1 существует такое минимальное число W(n,r), что в любой раскраске множества натуральных чисел от 1 до W(n,r) в r цветов найдется одноцветная арифметическая прогрессия длины n. Величину W(n,r) из теоремы Ван дер Вардена принято называть функцией Ван дер Вардена. Многолетние исследования относительно нахождения W(n,r) и других близких задач на сегодняшний день привели к появлению целого направления в математике - аддитивной комбинаторики. В докладе речь пойдет о двух подходах к получению нижних оценок функции Ван дер Вардена. Первый из них связан с теоремой о симметрии и плотностными задачами аддитивной комбинаторики. Второй - с экстремальными задачами о раскрасках гиперграфов. Кроме того, с помощью второго подхода будет представлена новая нижняя оценка W(n,r).


2 октября 2012 г. 19:00 - 20:30
А.В. Кудинов «Модальная логика в топологических пространствах»
Я постараюсь в доступной форме рассказать основные понятия модальной логики. В докладе будет рассмотрена пропозициональная модальная логика, которая фактически является классической логикой высказываний, расширенной одной или более одноместными связоками. Будет дано определение топологической семантики для модальных логик, в которой модальная связка интерпретируется как взятие внутренности множества. Я расскажу про классические результаты Мак-Кинси и Тарского (McKinsey & Tarski, 1944). Далее мы перейдем к тому, как можно увеличить выразительную силу языка, с помощью добавления новых модальностей: универсальной модальности, модальности неравенства и модальности производного множества.


25 сентября 2012 г. 18:30 - 20:00
Г.Г. Гусев «Поиск решения невырожденной системы $n$ уравнений от $n$ комплексных переменных, имеющих один корень в комплексном торе»
На докладе я расскажу о теореме, которую мы с Сашей Эстеровым доказали пару недель назад. Из результатов теоретической геометрии известно, что количество решений невырожденной системы полиномиальных уравнений совпадает со смешанным объемом многогранников Ньютона многочленов, задающих эту систему. Возникают естественные вопросы: Когда этот объем равен 0? А когда он равен 1? Ответ на первый вопрос - тема студенческой работы. Ответ на второй - непростая классификационная теорема, о которой я и расскажу. Важно, что формулировка теоремы достаточно лаконична и из нее вытекает простой наглядный алгоритм поиска единственного решения соответствующей системы уравнений.


Заседания семинара в 2011/12 учебном году
Заседания семинара в 2010/11 учебном году
Заседания семинара в 2009/10 учебном году
Заседания семинара в 2008/09 учебном году

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

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

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

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

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