Войти
Логин:
Пароль:
Забыли пароль?
научная деятельность
структура институтаобразовательные проектыпериодические изданиясотрудники институтапресс-центрконтакты
русский | english
Научная деятельность >> Семинары >> Дискретная и вычислительная геометрия

Семинар

Дискретная и вычислительная геометрия

Организаторы -  Александр ГайфуллинГригорий Кабатянский, Роман Карасёв, Игорь КричеверОлег Мусин

Cекретарь - Арсений Акопян
 
Семинар проходит по вторникам, в 1415, в аудитории 307 ИППИ РАН.
 

2018

05 июня

Докладчик: Роман Карасёв (МФТИ, ИППИ РАН), совместно с Арсением Акопяном и Сергеем Аввакумовым (Институт науки и техники Австрии)

Тема: Справедливое деление двумерного выпуклого пирога

Аннотация: Индийские философы Нандакумар и Рамана Рао поставили в 2008 году задачу о делении выпуклого плоского пирога на m выпуклых частей равной площади и периметра. Мы не будем обсуждать алгоритмические аспекты этой задачи, а будем говорить исключительно о вопросах существования такого разбиения для любого выпуклого пирога и любого m.

Нандакумар и Рамана Рао сами указали, что для m=2 задача решается простым соображением непрерывности, а для m=4 и больших степеней двойки дали некоторое рассуждение. На самом деле справедливое деление пирога на степень двойки частей было установлено (неявно) в 2003 году Михаилом Громовым как частный случай утверждения о делении меры на "блины", которое Громов использовал для доказательства теоремы о поперечнике гауссовой меры и сферы (ранее обсуждались на нашем семинаре и видимо будут обсуждаться далее).

Случай справедливого деления на три части был сделан Баранем, Благоевичем и Сючем в 2010 году. Случай степени простого, обобщающий все известные на тот момент результаты, доделывался разными людьми (Аронов, Убард, Благоевич, Циглер, Карасёв), хотя неявно был сделан в работе Виктора Васильева 1988 года про сложность нахождения корней многочленов от одного комплексного переменного.

Публикации по случаю степени простого вышли в 2014 году и после этого продвижения застопорились. Ситуация вроде бы была аналогична "топологической теореме Тверберга", в которой для m, не являющихся степенью простого, в итоге удалось построить контрпримеры (правда в достаточно больших размерностях). Однако в этом году у коллектива авторов появились новые идеи, которые позволили доделать задачу для произвольного количества частей m. Например, доказательство случая m=6 выглядит достаточно элементарно и возможно будет изложено полностью.


29 мая

Докладчик: Семён Шлосман (ИППИ РАН)
Тема: Топологическая Теорема Тверберга
Аннотация: ТТТ принадлежит к области топологической комбинаторики. Я расскажу драматическую историю ТТТ и обсужу некоторые вспомогательные результаты.


22 мая

Докладчик: Олег Мусин(Долина Рио_Гранде, ИППИ РАН)

Тема: Минимальные конфигурации на сфере для логарифмического потенциала

Аннотация: Задачи о минимумах потенциальной энергии являются очень сложными. Например, обобщённая задача Томсона (нахождения конфигурации точек с минимумом потенциальной энергии) для потенциала Рисса даже для N=5 точек на сфере остаётся открытой. Единственное математическое доказательство того, что бипирамида является решением этой задачи, известно только для логарифмического потенциала.

В этом докладе будет приведено полное доказательство совсем недавнего результата полученного совместно докладчиком и П. Драгневым. Мы показали, что локальные минимумы логарифмического потенциала с N=d+2 точками в d-мерном пространстве являются вершинами двух взаимно-ортогональных правильных симплексов.


10 апреля

Докладчик: Яна Теплицкая(ПОМИ РАН)

Тема: О задаче Штейнера, минимизации функционала максимального расстояния и самосжимающихся кривых

Аннотация: В первой части доклада я расскажу о построенном нами примере дерева Штейнера с бесконечным числом точек ветвления. Дерево Штейнера -- кратчайшее множество, соединяющее заданные точки. Известна структура такого множества: оно является деревом с вершинами в заданных точках и в некоторых вершинах, возникающих дополнительно. Такие вершины называются точками ветвления и имеют степень три. Было известно, что точек ветвления не более чем счётно, однако до нашей работы не было ясно, может ли их количество быть бесконечным. Оказывается, может. Расскажу о явном примере такого множества.

Во второй части доклада я расскажу о минимайзере максимального расстояния для окружности достаточно большого радиуса и для некоторых других множеств. Минимайзером максимального расстояния для некоторого заданного множества и для заданного расстояния r, называется самое короткое связное множество, такое что заданное множество находится в его замкнутой r-окрестности. Нам удалось найти все такие множества для окружностей достаточно большого (относительно r) радиуса и для множеств с большим радиусом кривизны.

В описанных выше задачах дело происходит на плоскости. Наконец, в третьей части своего доклада я расскажу о том, что самосжимающиеся кривые имеют конечную длину. Кривая с заданной параметризацией называется самосжимающейся относительно некоторой нормы, если для любых трёх моментов времени расстояние между образом второго и третьего момента не превосходит расстояния между образом первого и третьего моментов. Иными словами, для любых точек кривой все точки между ними лежат в шаре нормы с центром во второй точке и с первой точкой на границе. Мы доказали, что в нормированном пространстве любой конечной размерности самосжимающиеся кривые имеют конечную длину.


20 февраля

Докладчик: Роман Карасёв (ИППИ РАН)

Тема: Поперечники по Громову шаров пространств постоянной кривизны (по нашим работам с Арсением Акопяном и Альфредо Убардом)

Аннотация: Этот доклад является второй частью, первая докладывалась 10-го октября, но тогда мы не дошли собственно до заявленной темы доклада.

Теорема Борсука--Улама в одном из вариантов утверждает, что нечётное непрерывное отображение n-мерной сферы в n-мерное евклидово пространство отправляет в нуль две противоположные точки сферы. Несложная надстройка над этой теоремой показывает, что нечётное непрерывное отображение n-мерной сферы в m-мерное евклидово пространство (при m < n) отправляет в нуль некоторое множество, чья (n-m)-мерная мера (в некотором смысле) не менее, чем мера (n-m)-мерной сферы..

Громов в 2003 году доказал, что если в предыдущей формулировке отображение просто непрерывное, но необязательно нечётное, то оно отправляет в одну и ту же точку некоторое множество F, чья (n-m)-мерная мера (в некотором смысле) не менее, чем мера (n-m)-мерной сферы. На самом деле Громов доказал даже больше: что всякая метрическая t-окрестность F на n-сфере не меньше по объёму, чем t-окрестность стандартно вложенной в неё (n-m)-сферы.

Мы обсудим несколько более слабые варианты теоремы Громова о поперечнике для кубов, шара в евклидовом пространстве, и для метрических шаров в пространствах постоянной или ограниченной сверху кривизны; обсудим, что её вариант для меры прообраза допускает точное обобщение на кубы и шары, а вариант с объёмом окрестности -- нет.


2017

26 декабря

Докладчик: Семен Шлосман (ИППИ РАН)

Тема: Kissings in the Jam

Аннотация: Речь пойдёт о 24-мерном многообразии В_12, образованном 12-ю непересекающимися шарами радиуса R, касающимися тринадцатого шара единичного радиуса. Я расскажу о критических точках функции R на этом многообразии. Некоторые из них известны с древних времён; о других слушатели узнают первыми на свете.

Во второй части мы изучим с той же точки зрения 18-мерное многообразие С_6, образованное 6-ю непересекающимися цилиндрами радиуса R, касающимися шара единичного радиуса.


19 декабря

Докладчик: Олег Мусин (University of Texas at Brownsville, ИППИ РАН)

Тема: Плотнейшие сферические упаковки в 4-х мерном пространстве

Аннотация: Этот обзорный доклад посвящён проблемам сферических упаковок в размерности 4. Его основная цель - разобрать возможные подходы для решения задач связанных с плотнейшими упаковками единичных шаров в 4-х мерном евклидовом пространстве. Мы рассмотрим две старые открытые задачи из области сферических упаковок: единственность упаковки с максимальным контактным числом и гипотезу о 24-граннике. Заметим, что из гипотезы о 24-граннике вытекает, что плотнейшей упаковкой в 4-х мерном евклидовом пространстве является D4.


 

3 октября

Докладчик: Александр Максименко

Тема: Комбинаторно-геометрические характеристики сложности задач комбинаторной оптимизации

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

Планируемые к обсуждению результаты можно разбить на три группы:

1. Новые оценки для различных комбинаторных характеристик многогранников задач.

2. Обобщающие выводы на основе понятия аффинной сводимости семейств многогранников, позволяющей сравнивать различные характеристики сложности многогранников.

3. Различные примеры семейств многогранников, значения характеристик сложности которых существенно отличаются от вычислительной сложности соответствующих оптимизационных задач.


 

22 августа 

Докладчик: Олег Мусин (University of Texas at Brownsville, ИППИ РАН)

Тема: Поризм Штейнера, шестерка (hexlet) Содди и сферические коды

Аннотация: Знаменитый поризм Штейнера утверждает, что если цепочка окружностей, каждая из которых касается двух соседних и двух данных непересекающихся окружностей замкнется, то замкнется любая такая цепочка, независимо от выбора первой окружности. Гекслет Содди -- это цепочка из шести сфер, каждая из которых касается двух соседних и трёх заданных попарно касающихся сфер. Обе теоремы несложно доказать при помощи инверсии.

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


 

18 апреля

Аркадий Скопенков (МФТИ)

NP-трудность вложимости и почти вложимости гиперграфов в Rd

Аннотация 

21 февраля 

Докладчик: Михаил Карпухин (McGill University, НМУ)

Тема: Метрики на поверхностях, экстремальные для собственных значений оператора Лапласа--Бельтрами

Аннотация: Настоящий доклад посвящён задаче геометрической оптимизации собственных значений оператора Лапласа. Для фиксированного замкнутого многообразия собственные значения оператора Лапласа--Бельтрами можно рассматривать как функционалы на пространстве метрик единичного объёма. В случае поверхностей, согласно работам Кореваара, Ли, Янга и Яу, они оказываются ограниченными.

Возникает вопрос нахождения максимальных метрик и точной верхней границы для функционалов собственных значений. В последние годы этот вопрос получил особый интерес ввиду связи с теорией минимальных помногообразий в сферах. Используя эту связь, Пенской получил примеры экстремальных метрик на торе и бутылке Клейна. В данном докладе мы приведем новые примеры экстремальных метрик, полученные докладчиком, а также обсудим их максимальность.

17 января 

Владислав Волков (СПб)

Интегральная теорема Коши в арифметике и аддитивной комбинаторике

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

Во второй части рассматриваются различные обобщения и подходы к комбинаторной теореме о нулях, а также ряд приложений к комбинаторике и вопросам о свободных членах некоторых многочленов Лорана, берущим своё начало в статистической физике.

Хорошо известно, что комбинаторная теорема о нулях может быть использована, в частности, для получения короткого и элегантного доказательства теоремы Коши--Дэвенпорта о множествах сумм над полем. В докладе будут представлены новые версии комбинаторной теоремы о нулях: в виде явной формулы на коэффициент многочлена для мультимножеств (с помощью эрмитовой интерполяции), а также в классическом виде для гиперповерхностей. Классический подход Н. Алона к теореме Коши--Дэвенпорта будет обобщен для получения новых и уже известных результатов про размеры различных множеств сумм с ограничениями.

Также речь пойдёт о нахождении свободного члена многочленов Лорана, одним из известных таких соотношений является формула Дайсона. Несмотря на алгебраическую формулировку, данная формула тесно связана с теорией случайных матриц, статистической физикой (моделью Дайсона броуновского движения) и другими областями.

Недавно был обнаружен новый почти элементарный подход к формуле Дайсона с помощью <<комбинаторной теоремы о нулях>>, сводящий её к простой комбинаторной задаче. Удивительным образом данный подход с такой же (или даже большей) лёгкостью применим к q-версии формулы Дайсона, известное доказательство которой было значительно сложнее доказательства версии q=1. Этот результат мы обобщаем для получения элементарных доказательств соотношений Морриса и Аомото, а также для получения положительного ответа на гипотезу Форрестера, поставленную в 1995 году и, как и формула Дайсона, имеющую значение для статистической физики. С помощью той же техники мы получаем соотношения, обобщающие формулы Аомото и Форрестера одновременно, а также q-версии всех описанных соотношений.

2016

14 июня 

Олег Мусин (University of Texas at Brownsville, ИППИ РАН)

Многодольные множества с двумя расстояниями 

Пусть X — множество с двумя расстояниями a и b в евклидовом пространстве, а Γ(Х)обозначает его граф, т.е. граф вершинами которого являются точки ХХ, а рёбрами – пары точек с расстоянием a. В докладе будет приведена классификация всех множеств Х с двумя расстояниями, у которых Γ(Х)является полным k-дольным графом. Мы разберём теорему В. Куперберга о множествах Х в n-мерном единичном шаре с квадратом минимального расстояния между точками не меньше чем 2. Из этой теоремы вытекает, что если такое Х – множество с двумя расстояниями, то Γ(Х) является полным k-дольным графом. В частности, для простых nn все такие ХХ являются подмножествами вершин n-мерного кросс-политопа.

В заключении мы коснёмся работы Эйнхорна и Шёнберга в которой по сути устанавливается взаимно-однозначное соответствие между графами и множествами с двумя расстояниями. 

7 июня 

Олег Мусин (University of Texas at Brownsville, ИППИ РАН)

Изопериметрическая задача для многогранников

Изопериметрическая задача для многогранников впервые была рассмотрена Люилье (1782) и Штейнером (1842). Штейнер предположил, что среди многогранников комбинаторного типа одного из пяти правильных многогранников наибольшим IQ (Isoperimetric Quotient) обладает соответствующий правильный многогранник. Эта гипотеза до сих пор не доказана для икосаэдра. 
Изопериметрическая задача для многогранников с заданным числом граней f в настоящее время решена только для f<8 и f=12. Однако, первые результаты по этой задаче появились еще в XIX веке. В частности, Линделёф (1869) и Минковский (1897) доказали, что наибольший IQ у многогранника М с заданным числом граней только если М описан вокруг шара, причем так, что его грани касаются шара в центрах тяжести. 
В обзорном докладе мы рассмотрим несколько теорем и гипотез, связанных с этой задачей. Мы обсудим одно из доказательств неравенства Голдберга - Фейеша Тота (1934, 1948), которое возможно может быть расширено для всех размерностей. 

12 апреля

Раде Живалевичc (Rade Zivaljevi), Mathematical Institute SASA, Белград

Topology and combinatorics of "unavoidable complexes"

29 марта

Захар Овсянников 

Оптимальные сети

Оптимальные сети -- это вложения графов в некоторые метрические пространства, минимизирующие функционал длины на некотором классе графов и вложений, их область применения варьируется от трассировки печатных плат до эволюционной биологии.

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

22 марта

Isaac Mabillard

Whitney Trick and Counterexamples to the Topological Tverberg Conjecture (Joint work with A. Avvakumov, A. Skopenkov, and U. Wagner) 

Let"s assume that r embedded balls intersect in R^d transversally and that their intersection consists of two points of opposite intersection signs. I"ll describe a generalization of the classical Whitney trick to this situation: Our goal is to eliminate the pair of intersection points, by means of ambient isotopies having "small" support.

A neat application of this "generalized Whitney trick" is the construction of counterexamples to the topological Tverberg conjecture, which asserts that for any continuous map from the N-simplex to R^d, one can always find "a large number" of disjoint cells of the N-simplex that intersect in the image in R^d. Due to the codimension requirements of our current techniques, we can only build counterexamples for d at least 12. So what happens in lower dimensions remains a mystery...

Прошедшие семинары - 2014

Прошедшие семинары - 2013

Прошедшие семинары - 2015

НОВОСТИ И ОБЪЯВЛЕНИЯ
Семинар лаборатории № 8: 4 октября в 14:30 в ИПЭЭ РАН. В.М. Ольшанский. О возможной этологической фу...
Семинар лаб.№9 состоится 2 октября в 11:00 в ауд.307 Аруин А.С. АНТИСИПАТОРНЫЕ И КОМПЕНСАТОРНЫЕ НАСТ...
В.М. Акулин (ИППИ и CNRS): Универсальный неголономный контроль квантовой системы на полугруппе в кон...
3 августа в рамках "Пятничного семинара ИППИ РАН" выступит Владимир Корепин (C.N.Yang Institute for ...
Семинар лаборатории № 8: 31 мая в 14:30 в ИПЭЭ РАН. А.В. Лиманская. Полисомнографическое изучение яв...
Семинар лаборатории № 8: 24 мая в 14:30 в ИПЭЭ РАН. М. Бангура, М.Ю. Кочевалина, Е.И. Родионова. Пов...
22 мая: очередное заседание семинара "Дискретная и вычислительная...
Семинар лаборатории № 8: 26 апреля в 14:30 в ИПЭЭ РАН. А.Т. Алипер. О структуре рецептивных полей ор...
Семинар лаб.9, 24 апреля, 11: 00 Ирина Евгеньевна Сироткина Степени свободы человека. К выход...
Семинар лаборатории № 8: 29 марта в 14:30 в ИПЭЭ РАН. Д.Н. Лапшин, Д.Д. Воронцов. Частотная обусловл...
Все новости   
 

 

  © Федеральное государственное бюджетное учреждение науки
Институт проблем передачи информации им. А.А. Харкевича Российской академии наук, 2018
Об институте  |  Контакты  |  Старая версия сайта