Семинары >> Дискретная и вычислительная геометрия >> Прошедшие семинары
2014
23 декабря
Олег Мусин (ИППИ)
Экстремальные задачи упаковок кругов на сфере
Будет рассказано о серии работ докладчика с А. С. Тарасовым по проблеме Таммеса и неприводимым графам.
Недавно, с точностью до изометрии, нами были перечислены все локально-жесткие упаковки конгруэнтных кругов (сферических шапочек) на единичной сфере с числом кругов N <12. Эта задача эквивалентна перечислению сферических неприводимых контактных графов. В докладе будет показано, что с помощью списка неприводимых контактных графов можно решать различные задачи об экстремальных упаковках таких как задача Таммеса для сферы и проективной плоскости, задача о наибольшем числе контактов у сферических упаковок, задачи Данцера и другие задачи о неприводимых контактных графах.
16 декабря
Михаил Исаев (МФТИ)
Перечисление эйлеровых циклов
Эйлеровым циклом графа называется замкнутый путь по ребрам графа, использующей все ребра ровно один раз. BEST-теорема (названная согласно инициалам авторов*B*ruijn, Aardenne-*E*hhrenfest, *S*mith, *T*utte) позволяет связать число различный эйлеровых циклов с количеством помеченных остовных деревьев. Согласно матричной теореме о деревьях перечисление остовных деревьев сводится к подсчету минора специальной матрицы, ассоциированной с графом. В докладе планируется подробно обсудить этот подход для случаев ориентированного и неориентированного графа, а также доказать вышеупомянутые теоремы (и вариации).
Доклад основан на работах [1] и [2]:
[1] М.И. Исаев, «Асимптотическое перечисление эйлеровых циклов в графах, обладающих сильными перемешивающим свойствами», Известия РАН. Серия Математическая, Т. 77(6), 2013, 45‐70
[2] B. D. McKay, R. W. Robinson, Asymptotic enumeration of eulerian circuits in the complete graph. Combinatorics, Probability and Computing, 7(4), 1998, 437-449.
18 ноября
Об отображениях, переводящих прямые в плоские кривые
(По результатам совместной работы с В. Петрущенко)
Планаризация — это отображение f из открытого подмножества U вещественной проективной плоскости в вещественное проективное трехмерное пространство, переводящее отрезки прямых, содержащиеся в U, в отрезки плоских кривых. Изучение планаризаций тесно связано с изучением отображений, переводящих прямые в элементы определенных линейных систем (скажем, в окружности, коники и проч.). Классический результат в этом направлении — это теорема Мебиуса-фон Штаудта об отображениях, переводящих прямые в прямые. Эта теорема иногда называется основной теоремой проективной геометрии. Мы предполагаем, что все рассматриваемые планаризации достаточно гладки, то есть достаточное число раз дифференцируемы. Мы приведем полное описание всех планаризаций по модулю следующего отношения эквивалентности: два отображения эквивалентны, если они совпадают на непустом открытом множестве, после проективного преобразования в прообразе и проективного преобразования в образе. Кроме тривиальных случаев, имеется 16 классов, из которых 6 классов состоят из кубических отображений, а остальные 10 — из квадратичных отображений.
14 октября
Олег Мусин (ИППИ)
Обобщения и приложения лемм Шпернера и Таккера
Будет рассказано о совсем новых результатах докладчика по этой тематике. Одна из тем доклада — лемма А. Ю. Шашкина и ее обобщение. Кроме того, будет обсуждаться применение леммы Шпернера к задачам о справедливом распределении.
7 октября
Сергей Ландо
On the signed number of circuits of even length in nonoriented graphs
A chord diagram is a one-face map. To a chord diagram, a simple graph can be associated, which is the intersection graph of the diagram. The chord diagram structure allows one to assign signs to circuits of even length in this graph in a natural way. The difference between the number of positive and negative circuits of given length 2k is a graph invariant. This invariant is closely related to the weight system (in other words, to the Vassiliev knot invariants) associated to the Lie algebra sl2. It happens that this invariant admits a natural extension to arbitrary graphs, including those that are not intersection graphs of chord diagrams. This fact leads to a number of questions concerning the existence of more graph invariants related to sl2 and other Lie algebras.
The talk is based on a joint paper with E. Kulakova, T. Mukhutdinova and G. Rybnikov (2014).
30 сентября
Илья Шкредов
О сумме произведений
Феномен сумм произведений — это аддитивно-комбинаторное утверждение, которое, грубо говоря, состоит в том, что любое конечное подмножество кольца (например, целых чисел), отличное от подкольца, имеет либо большую сумму, либо большое произведение. Данное чисто комбинаторное утверждение имеет глубокие следствия в теории чисел, криптографии и теоретической информатике. Мы дадим небольшой обзор имеющихся здесь результатов и скажем несколько слов о последних достижениях в этой области.
23 сентября
Алексей Канель-Белов, Илья Иванов-Погодаев
Конечно-определенные ниль-полугруппы, иные объекты и непериодические мозаики
Доклад посвящен решению проблемы Шеврина о существовании бесконечной конечно определенной ниль-полугуппы. Это решение открывает перспективы для аналогичных проблем в теории колец и групп.
Элементы полугруппы интерпретируются как геодезические пути на комплексе, составленном из непериодической мозаики. Данный комплекс отвечает пространству со свойством «равномерной эллиптичности» – любые две точки на расстоянии d соединены системой геодезических образующих диск толщины λd. (поведение подобно противоположным точкам на сфере).
По сути дела, используется обобщениие теоремы Гудмана–Штраусса о задании любой подстановочной системы (типа мозаик Пенроуза) локальными правилами примыкания.
20 мая
Михаил Цфасман
Упаковки шаров и теория чисел (она же алгебраическая геометрия)
Я, в очередной раз, расскажу про применения теории чисел и алгебраической геометрии к задаче о плотных упаковках шаров. Эта и похожие задачи заставили нас по-новому взглянуть на то, как именно ставить вопросы в алгебраической теории чисел и геометрии над конечными полями.
13 мая
Владимир Дольников
О (p,q)-свойстве графов и гиперграфов
22 апреля
Роман Карасёв
Метод Громова стягивания в пространстве циклов
Мы рассмотрим технику, которую Михаил Громов назвал "стягивание в пространстве циклов".
Начнём с примера такого утверждения (Громов, 2010): В евклидовом пространстве размерности d рассматриваются независимые случайные точки в количестве d+1, тогда можно доказать, что некоторая фиксированная точка пространства всегда покрывается выпуклой оболочкой этих случайных точек (симплексом) с вероятностью не менее 1/(d+1)! На этом примере метод демонстрируется довольно наглядно, буден рассказан существенно упрощённый вариант доказательства Громова.
Также мы рассмотрим леммы К. Макмаллена о покрытии евклидова пространства и тора. Они доказываются той же техникой и мы обсудим более простой вариант доказательства, по сравнению с доказательством Макмаллена.
Также мы обсудим результат докладчика и М. Матдинова про одноцветные компоненты при раскрашивании куба, который тоже доказывается аналогичной техникой.
15 апреля
Семён Шлосман
Небоскрёбы
Будут рассказаны некоторые известные факты про диаграммы Юнга и их многомерные аналоги (2D разбиения или небоскрёбы). В частности, будет разъяснена формула Мак-Магона для производящей функции небоскрёбов. Будет также продемонстрирована производящая функция 3D разбиений.
Во второй части будут изложены результаты совместной работы докладчика с О. Огиевецким, посвящённой комбинаторному доказательству одной формулы А. А. Кириллова и её обобщений. Работа использует соответствие Робинсона-Шенстеда (RS-correspondence), которое тоже будет разъяснено.
8 апреля
Александр Гайфуллин
Изгибаемые кросс-политопы в пространствах произвольных размерностей
В 1897 году Р. Брикар нашел три типа изгибаемых самопересекающихся октаэдров в трехмерном евклидовом пространстве. В докладе будет рассказана конструкция изгибаемых самопересекающихся кросс-политопов в пространствах постоянной кривизны (евклидовом, сферическом и пространстве Лобачевского) произвольных размерностей. В размерностях 5 и выше это -- первые примеры изгибаемых многогранников. Более того, будет дана классификация всех изгибаемых кросс-политопов.
1 апреля
Олег Мусин (ИППИ)
Дискретные аналоги теорем о неподвижных точках
Дискретным аналогом теоремы Брауэра о неподвижной точке является знаменитая лемма Шпернера, а теоремы Борсука - Улама леммы Таккера и Ки Фана. В докладе предполагается обсудить эти леммы и их обобщения. Недавно докладчику удалось найти общее утверждение, из которого эти леммы получаются как следствие.
18 марта
Сергей Гашков (мехмат МГУ)
Схемная сложность вычислений
О различных задачах, которые можно сформулировать в терминах сложности алгебраических вычислений неветвящимися программами.
11 марта
Николай Долбилин (МИАН)
Локальные теоремы о структуре кристаллов
4 марта
Григорий Ольшанский
Детерминантные точечные процессы
25 февраля
Игорь Кричевер
Аналитическая теория разностных уравнений с рациональными и эллиптическими коэффициентами
В докладе был представлен новый подход к построению аналитической теории разностных уравнений, который позволяет ввести понятие локальных монодромий мероморфных решений таких уравнений.
18 февраля
Иван Дынников (Стекловка)
Лежандровы узлы, монотонное упрощение и гипотеза Джонса
4 февраля
Александр Бернштейн (Лаб.1 ИППИ РАН)
Manifold Learning - что это такое
| 
