Это канал Лаборатории комбинаторных и геометрических структур МФТИ.
Основные направления исследований лаборатории:
• Экстремальная комбинаторика
• Дискретная геометрия
• Теоретическая информатика
• Связи комбинаторики с алгоритмами и оптимизацией
Здесь мы будем публиковать анонсы семинаров и научных мероприятий, новости лаборатории, информация о курсах, воркшопах, школах и открытых возможностях. Записи семинаров и материалы прошлых мероприятий доступны на сайте https://combgeo.org/.
Физически лаборатория находится в корпусе прикладной математики МФТИ, 102б.
Будем рады видеть вас на наших мероприятиях!
Основные направления исследований лаборатории:
• Экстремальная комбинаторика
• Дискретная геометрия
• Теоретическая информатика
• Связи комбинаторики с алгоритмами и оптимизацией
Здесь мы будем публиковать анонсы семинаров и научных мероприятий, новости лаборатории, информация о курсах, воркшопах, школах и открытых возможностях. Записи семинаров и материалы прошлых мероприятий доступны на сайте https://combgeo.org/.
Физически лаборатория находится в корпусе прикладной математики МФТИ, 102б.
Будем рады видеть вас на наших мероприятиях!
❤7👍2🔥1
12 февраля в 18:30 (МСК) на Большом семинаре CombGeoLab выступит Nikhil Bansal с докладом о недавнем прорыве в Combinatorial Discrepancy: продвижении в гипотезе Комлоша и доказательстве 40-летней гипотезы Бека–Фиалы для широкого диапазона параметров.
Title: On Beck-Fiala and Komlós Conjectures
Abstract: A conjecture of Komlós states that the discrepancy of any collection
of unit vectors is O(1), i.e., for any matrix A with unit columns,
there is a vector x with -1,1 entries such that |Ax|_\infty = O(1).
The related Beck-Fiala conjecture states that any set system with
maximum degree k has discrepancy O(k^{1/2}).
I will describe an O((log n)^{1/4}) bound for the Komlós problem,
improving upon an O((log n)^{1/2}) bound due to Banaszczyk.
Time permitting, we will see how these ideas can be used to resolve
the Beck-Fiala conjecture for k >= (log n)^2.
Ссылка на доклад (12 февраля 18:30 МСК):
https://us02web.zoom.us/j/82214467974?pwd=9bbtIr8GMwIQ6cQmgacqdeDhL6IAhn.1
Доклад будет интересен всем, кто интересуется вероятностными методами, алгоритмическими аспектами и применением линейной алгебры в комбинаторике.
Title: On Beck-Fiala and Komlós Conjectures
Abstract: A conjecture of Komlós states that the discrepancy of any collection
of unit vectors is O(1), i.e., for any matrix A with unit columns,
there is a vector x with -1,1 entries such that |Ax|_\infty = O(1).
The related Beck-Fiala conjecture states that any set system with
maximum degree k has discrepancy O(k^{1/2}).
I will describe an O((log n)^{1/4}) bound for the Komlós problem,
improving upon an O((log n)^{1/2}) bound due to Banaszczyk.
Time permitting, we will see how these ideas can be used to resolve
the Beck-Fiala conjecture for k >= (log n)^2.
Ссылка на доклад (12 февраля 18:30 МСК):
https://us02web.zoom.us/j/82214467974?pwd=9bbtIr8GMwIQ6cQmgacqdeDhL6IAhn.1
Доклад будет интересен всем, кто интересуется вероятностными методами, алгоритмическими аспектами и применением линейной алгебры в комбинаторике.
🔥5❤3👍1
19 февраля в 18:30 (МСК) на Большом семинаре CombGeoLab выступит Matija Bucić.
Название доклада: Equiangular lines via improved eigenvalue multiplicity
Аннотация:
A family of lines passing through the origin in an inner product space is said to be equiangular if every pair of lines defines the same angle. In 1973, Lemmens and Seidel raised what has since become a central question in the study of equiangular lines in Euclidean spaces. They asked for the maximum number of equiangular lines in R^r with a common angle of alpha. This classical question stems its origins from elliptic geometry, and has since found connections and applications to a large number of different areas. Improving on a number of recent breakthroughs, we determine the answer up to lower order terms for essentially the whole range of parameters and determine it precisely when alpha=arccos(1/(2k-1)) for any positive integer k, when the dimension is at least exponential in a polynomial in k. The key new ingredient underlying our results is an improved upper bound on the multiplicity of the second-largest eigenvalue of a graph.
Joint work with Igor Balla.
Ссылка на доклад (19 февраля 18:30 МСК):
https://us02web.zoom.us/j/82214467974?pwd=9bbtIr8GMwIQ6cQmgacqdeDhL6IAhn.1
Название доклада: Equiangular lines via improved eigenvalue multiplicity
Аннотация:
A family of lines passing through the origin in an inner product space is said to be equiangular if every pair of lines defines the same angle. In 1973, Lemmens and Seidel raised what has since become a central question in the study of equiangular lines in Euclidean spaces. They asked for the maximum number of equiangular lines in R^r with a common angle of alpha. This classical question stems its origins from elliptic geometry, and has since found connections and applications to a large number of different areas. Improving on a number of recent breakthroughs, we determine the answer up to lower order terms for essentially the whole range of parameters and determine it precisely when alpha=arccos(1/(2k-1)) for any positive integer k, when the dimension is at least exponential in a polynomial in k. The key new ingredient underlying our results is an improved upper bound on the multiplicity of the second-largest eigenvalue of a graph.
Joint work with Igor Balla.
Ссылка на доклад (19 февраля 18:30 МСК):
https://us02web.zoom.us/j/82214467974?pwd=9bbtIr8GMwIQ6cQmgacqdeDhL6IAhn.1
❤3👍2🔥2🐳1
12 марта в 18:30 (МСК) на Большом семинаре CombGeoLab выступит Dmitrii Zakharov.
Название доклада: Sets with moderate doubling
Аннотация:
Let A be a subset in an abelian group G such that |A+A| < |A|^{1.99}. In this case we say that A has moderate doubling. What can be said about the structure of A? Essentially nothing is known about this problem. If instead 1.99 we put 1.01, i.e. consider sets A with small doubling, then the Polynomial Freiman-Ruzsa conjecture predicts that A has to be close to to a subgroup (or Bohr set).
We discuss examples and possible conjectures about the structure of moderate doubling sets. We prove that in the case of G = F_2^n, the set A must intersect significantly with a subgroup coset. We follow the entropic approach which was used in the recent resolution of the PFR conjecture over F_2.
Joint work with Alex Cohen.
Ссылка на доклад:
https://us02web.zoom.us/j/82214467974?pwd=9bbtIr8GMwIQ6cQmgacqdeDhL6IAhn.1
Название доклада: Sets with moderate doubling
Аннотация:
Let A be a subset in an abelian group G such that |A+A| < |A|^{1.99}. In this case we say that A has moderate doubling. What can be said about the structure of A? Essentially nothing is known about this problem. If instead 1.99 we put 1.01, i.e. consider sets A with small doubling, then the Polynomial Freiman-Ruzsa conjecture predicts that A has to be close to to a subgroup (or Bohr set).
We discuss examples and possible conjectures about the structure of moderate doubling sets. We prove that in the case of G = F_2^n, the set A must intersect significantly with a subgroup coset. We follow the entropic approach which was used in the recent resolution of the PFR conjecture over F_2.
Joint work with Alex Cohen.
Ссылка на доклад:
https://us02web.zoom.us/j/82214467974?pwd=9bbtIr8GMwIQ6cQmgacqdeDhL6IAhn.1
🔥6❤1
26 марта (Чт) в 18:30 (МСК) на Большом семинаре CombGeoLab выступит Sahar Diskin
Title: Supercritical sharpness of percolation
Abstract: Given an infinite transitive graph (such as the standard lattice Z^d), build a random subgraph by independently including each edge with probability p. This model undergoes a phase transition as p varies across the critical value p_c marking the emergence of an infinite component. A fundamental result is that for any fixed p<p_c, the probability that a given vertex is in a component of size at least n decays exponentially with n. We will prove the analogous result for the supercritical regime, p>p_c.
Based on a (very recent) joint work with Easo, Ramanan-Radhakrishnan, Sudakov, and Tassion.
Ссылка на доклад:
https://us02web.zoom.us/j/82214467974?pwd=9bbtIr8GMwIQ6cQmgacqdeDhL6IAhn.1
Title: Supercritical sharpness of percolation
Abstract: Given an infinite transitive graph (such as the standard lattice Z^d), build a random subgraph by independently including each edge with probability p. This model undergoes a phase transition as p varies across the critical value p_c marking the emergence of an infinite component. A fundamental result is that for any fixed p<p_c, the probability that a given vertex is in a component of size at least n decays exponentially with n. We will prove the analogous result for the supercritical regime, p>p_c.
Based on a (very recent) joint work with Easo, Ramanan-Radhakrishnan, Sudakov, and Tassion.
Ссылка на доклад:
https://us02web.zoom.us/j/82214467974?pwd=9bbtIr8GMwIQ6cQmgacqdeDhL6IAhn.1
👍4❤2
16 апреля (Чт) в 18:30 (МСК) на Большом семинаре CombGeoLab выступит Lyuben Lichev, TU Wien
Title: The power of choice: a geometric perspective
Abstract: In the random geometric graph process random points are embedded consecutively in the d-dimensional unit torus and every two points at distance at most r form an edge. In the first part of the talk, we will explore analogues of well-known hitting time results for connectivity and Hamiltonicity in the Erdős–Rényi graph process when r approaches 0. The main focus of the talk will fall on a discussion of a geometric version of the power of choice where, at each step, an agent is shown two independent random points and is allowed to choose one of them. Related sharp threshold and hitting time results will be considered in an online and an offline version of the choice process. Joint work with Dawid Ignasiak.
Ссылка на доклад:
https://us02web.zoom.us/j/82214467974?pwd=9bbtIr8GMwIQ6cQmgacqdeDhL6IAhn.1
Title: The power of choice: a geometric perspective
Abstract: In the random geometric graph process random points are embedded consecutively in the d-dimensional unit torus and every two points at distance at most r form an edge. In the first part of the talk, we will explore analogues of well-known hitting time results for connectivity and Hamiltonicity in the Erdős–Rényi graph process when r approaches 0. The main focus of the talk will fall on a discussion of a geometric version of the power of choice where, at each step, an agent is shown two independent random points and is allowed to choose one of them. Related sharp threshold and hitting time results will be considered in an online and an offline version of the choice process. Joint work with Dawid Ignasiak.
Ссылка на доклад:
https://us02web.zoom.us/j/82214467974?pwd=9bbtIr8GMwIQ6cQmgacqdeDhL6IAhn.1
🔥3❤2
23 апреля (Чт) в 14:00 (МСК) на Большом семинаре CombGeoLab выступит Jie Ma, USTC/Tsinghua, TU Wien
Title: Supersaturation for Color-Critical Graphs and Beyond
Abstract:
In this talk, we discuss supersaturation phenomena in extremal graph theory from both combinatorial and spectral viewpoints. For a fixed graph \(F\), the supersaturation problem asks for the minimum number of copies of \(F\) in an \(n\)-vertex graph with \(\mathrm{ex}(n,F)+q\) edges. Classical results determine this quantity for all color-critical graphs (including cliques and odd cycles) when \(q\) lies in the linear regime, but the picture beyond this range remains far from complete.
We present recent progress that substantially extends this theory. On the combinatorial side, we construct new families of graphs showing that the extremal configurations obtained by adding edges to Turán graphs are not always optimal, thereby refuting existing conjectures and identifying new threshold phenomena. On the spectral side, we establish analogues of supersaturation under constraints on the spectral radius, obtaining sharp bounds for color-critical graphs and revealing a parallel theory in the spectral setting.
These results provide new structural insights into supersaturation and highlight a unified picture with sharp transitions and diverse behavior depending on the graph \(F\). This talk is based on two joint projects with Longfei Fang, Yongtao Li, Huiqiu Lin, and Long-Tu Yuan.
Ссылка на доклад:
https://us02web.zoom.us/j/82214467974?pwd=9bbtIr8GMwIQ6cQmgacqdeDhL6IAhn.1
Title: Supersaturation for Color-Critical Graphs and Beyond
Abstract:
In this talk, we discuss supersaturation phenomena in extremal graph theory from both combinatorial and spectral viewpoints. For a fixed graph \(F\), the supersaturation problem asks for the minimum number of copies of \(F\) in an \(n\)-vertex graph with \(\mathrm{ex}(n,F)+q\) edges. Classical results determine this quantity for all color-critical graphs (including cliques and odd cycles) when \(q\) lies in the linear regime, but the picture beyond this range remains far from complete.
We present recent progress that substantially extends this theory. On the combinatorial side, we construct new families of graphs showing that the extremal configurations obtained by adding edges to Turán graphs are not always optimal, thereby refuting existing conjectures and identifying new threshold phenomena. On the spectral side, we establish analogues of supersaturation under constraints on the spectral radius, obtaining sharp bounds for color-critical graphs and revealing a parallel theory in the spectral setting.
These results provide new structural insights into supersaturation and highlight a unified picture with sharp transitions and diverse behavior depending on the graph \(F\). This talk is based on two joint projects with Longfei Fang, Yongtao Li, Huiqiu Lin, and Long-Tu Yuan.
Ссылка на доклад:
https://us02web.zoom.us/j/82214467974?pwd=9bbtIr8GMwIQ6cQmgacqdeDhL6IAhn.1
🔥3❤2
Этим летом в Лаборатории вновь состоится Летняя Исследовательская Программа для Студентов - ЛИПС-26. Она пройдет с 13 июля по 15 августа в МФТИ, г. Долгопрудный. Программа рассчитана в первую очередь на студентов 2-4 курсов бакалавриата и магистратуры.
Целью программы станет исследование открытых задач на стыке комбинаторики, геометрии и топологии с последующим полноценным оформлением результатов в виде публикаций.
▷ Приглашаем всех желающих студентов к участию в программе - о том, как отправить заявку читайте на странице мероприятия. Совсем скоро мы также объявим стартовые задачи, следите за новостями ◁
Самая свежая информация всегда доступна на странице https://combgeo.org/events-ru/summer-2026/.
Целью программы станет исследование открытых задач на стыке комбинаторики, геометрии и топологии с последующим полноценным оформлением результатов в виде публикаций.
▷ Приглашаем всех желающих студентов к участию в программе - о том, как отправить заявку читайте на странице мероприятия. Совсем скоро мы также объявим стартовые задачи, следите за новостями ◁
Самая свежая информация всегда доступна на странице https://combgeo.org/events-ru/summer-2026/.
🔥8❤3👻1
Новости ЛИПС-26:
⚡️ Опубликованы формулировки стартовых задач
⚡️ Прием заявок продлен до 23 мая
Вся актуальная информация доступна на странице мероприятия. Ждем ваши заявки!
⚡️ Опубликованы формулировки стартовых задач
⚡️ Прием заявок продлен до 23 мая
Вся актуальная информация доступна на странице мероприятия. Ждем ваши заявки!
🔥5❤🔥2💋1
Привет друзья!
Информация для участников ЛИПС-26:
📅 Мы приносим извинения за задержки по изначально объявленным датам. Приглашения на собеседования по полученным заявкам начались на этой неделе.
📅 Также до 10 июня продолжается прием заявок в рамках второй волны.
📅 Окончательный список участников запланирован на 20 июня.
Благодарим за терпение, а также приглашаем всех, кто не успел!
Информация для участников ЛИПС-26:
📅 Мы приносим извинения за задержки по изначально объявленным датам. Приглашения на собеседования по полученным заявкам начались на этой неделе.
📅 Также до 10 июня продолжается прием заявок в рамках второй волны.
📅 Окончательный список участников запланирован на 20 июня.
Благодарим за терпение, а также приглашаем всех, кто не успел!
❤4🥰2
13 - 14 июля приглашаем всех на конференцию $A.M.≥50$, приуроченную к юбилею Андрея Михайловича Райгородского. Конференция выпадает на первые дни ЛИПС-26, но это открытое событие и мы будем рады всем слушателям!
___
Пленарные докладчики конференции:
Imre Bárány (Rényi Institute of Mathematics)
Stefano Boccaletti (Institute for Complex Systems)
Gyula O. H. Katona (Rényi Institute of Mathematics)
János Pach (Rényi Institute of Mathematics)
Герман Олег Николаевич (ВШЭ)
Долбилин Николай Петрович (Математический интститут им. В.А. Стеклова РАН)
Кабатянский Григорий Анатольевич (Сколтех)
Карасёв Роман Николаевич (МФТИ)
Мощевитин Николай Германович (МГУ)
Семенов Алексей Львович (МГУ)
____
Конференция пройдет в Долгопрудном в здании Физтех.Клуба (Первомайская 3А, ТЦ Дирижабль, 2 этаж).
Подробнее читайте на странице события.
___
Пленарные докладчики конференции:
Imre Bárány (Rényi Institute of Mathematics)
Stefano Boccaletti (Institute for Complex Systems)
Gyula O. H. Katona (Rényi Institute of Mathematics)
János Pach (Rényi Institute of Mathematics)
Герман Олег Николаевич (ВШЭ)
Долбилин Николай Петрович (Математический интститут им. В.А. Стеклова РАН)
Кабатянский Григорий Анатольевич (Сколтех)
Карасёв Роман Николаевич (МФТИ)
Мощевитин Николай Германович (МГУ)
Семенов Алексей Львович (МГУ)
____
Конференция пройдет в Долгопрудном в здании Физтех.Клуба (Первомайская 3А, ТЦ Дирижабль, 2 этаж).
Подробнее читайте на странице события.
🔥21
Объявляем участников программы ЛИПС в этом году:
◈ Даниил Акимов (МФТИ)
◈ Никита Викол (МФТИ)
◈ Полина Воробьёва (СПбГУ)
◈ Ахмед Габин (МФТИ)
◈ Тимофей Данилов (СПбГУ)
◈ Иван Дмитриев (МФТИ)
◈ Ян Дрожецкий (ВШЭ)
◈ Иван Коршунов (МФТИ)
◈ Михаил Курс (МФТИ)
◈ Таисия Липатова (ВШЭ)
◈ Илья Лобацкий (МФТИ)
◈ Александра Медведева (МГУ)
◈ Никита Миронов (ВШЭ)
◈ Александр Новосёлов (МФТИ)
◈ Антон Плюснин (МФТИ)
◈ Елизавета Прибыткова (СПбГУ)
◈ Никита Пшеничный (МГУ)
◈ Александр Ромачевский (МФТИ)
◈ Анна Садовская (ВШЭ, Нижний Новгород)
◈ София Труфанова (МФТИ)
◈ Михаил Тырин (МФТИ)
◈ Сергей Фомин (СПбГУ)
◈ Платон Хаматов (МФТИ)
◈ Тимур Шамазов (СПбГУ)
◈ Илья Широков (СПбГУ)
Всех поздравляем и ждем встречи на ЛИПСе!
◈ Даниил Акимов (МФТИ)
◈ Никита Викол (МФТИ)
◈ Полина Воробьёва (СПбГУ)
◈ Ахмед Габин (МФТИ)
◈ Тимофей Данилов (СПбГУ)
◈ Иван Дмитриев (МФТИ)
◈ Ян Дрожецкий (ВШЭ)
◈ Иван Коршунов (МФТИ)
◈ Михаил Курс (МФТИ)
◈ Таисия Липатова (ВШЭ)
◈ Илья Лобацкий (МФТИ)
◈ Александра Медведева (МГУ)
◈ Никита Миронов (ВШЭ)
◈ Александр Новосёлов (МФТИ)
◈ Антон Плюснин (МФТИ)
◈ Елизавета Прибыткова (СПбГУ)
◈ Никита Пшеничный (МГУ)
◈ Александр Ромачевский (МФТИ)
◈ Анна Садовская (ВШЭ, Нижний Новгород)
◈ София Труфанова (МФТИ)
◈ Михаил Тырин (МФТИ)
◈ Сергей Фомин (СПбГУ)
◈ Платон Хаматов (МФТИ)
◈ Тимур Шамазов (СПбГУ)
◈ Илья Широков (СПбГУ)
Всех поздравляем и ждем встречи на ЛИПСе!
😈9❤2👍1
Привет, друзья! На странице конференции $A.M.≥50$ появилось расписание докладов. Также мы просим всех, кто планирует приехать, зарегистрироваться через Google Форму. До скорой встречи!
❤3
Расписание на первый день конференции ＄A.M.≥50＄, 13 июля:
9:50 - Открытие
10:00 - Семенов Алексей Львович (МГУ)
10:50 - János Pach (Rényi Institute of Mathematics)
11:40 - Долбилин Николай Петрович (Математический интститут им. В.А. Стеклова)
12:30 - Ланч
14:00 - Герман Олег Николаевич (НИУ ВШЭ)
14:50 - Мощевитин Николай Германович (TU Wien, Austria)
15:40 - Кофе-брейк
________
Секционные доклады:
16.10 - Шабанов Дмитрий Александрович (МФТИ, МГУ, НИУ ВШЭ)
16.40 - Жуковский Максим Евгеньевич (University of Sheffield)
17.10 - Купавский Андрей Борисович (МФТИ)
17.40 - Воронов Всеволод Александрович (АГУ)
18.10 - Захаров Дмитрий Андреевич (MIT)
18.40 - Чернявский Михаил Юрьевич (МФТИ)
Темы и аннотации докладов, а также возможные изменения в расписании, смотрите на странице конференции.
9:50 - Открытие
10:00 - Семенов Алексей Львович (МГУ)
10:50 - János Pach (Rényi Institute of Mathematics)
11:40 - Долбилин Николай Петрович (Математический интститут им. В.А. Стеклова)
12:30 - Ланч
14:00 - Герман Олег Николаевич (НИУ ВШЭ)
14:50 - Мощевитин Николай Германович (TU Wien, Austria)
15:40 - Кофе-брейк
________
Секционные доклады:
16.10 - Шабанов Дмитрий Александрович (МФТИ, МГУ, НИУ ВШЭ)
16.40 - Жуковский Максим Евгеньевич (University of Sheffield)
17.10 - Купавский Андрей Борисович (МФТИ)
17.40 - Воронов Всеволод Александрович (АГУ)
18.10 - Захаров Дмитрий Андреевич (MIT)
18.40 - Чернявский Михаил Юрьевич (МФТИ)
Темы и аннотации докладов, а также возможные изменения в расписании, смотрите на странице конференции.
🔥9❤2
Второй день конференции ＄A.M.≥50＄ (завтра, 14 июля) пройдет по следующему расписанию:
10:00 - Леонидов Андрей Владимирович (Физический институт им. П.Н. Лебедева РАН)
10:50 - Gyula O. H. Katona (Rényi Institute of Mathematics)
11:40 - Карасёв Роман Николаевич (ИППИ РАН)
12:30 - Ланч
14:00 - Imre Bárány (Rényi Institute of Mathematics)
14:50 - Stefano Boccaletti (Institute for Complex Systems)
15:40 - Кабатянский Григорий Анатольевич (Сколтех)
16:30 - Кофе-брейк
17:00 - Дольников Владимир Леонидович (МФТИ)
17:30 - Обсуждение открытых проблем
_____
Приглашаем всех желающих! Темы и аннотации докладов, а также возможные изменения в расписании, смотрите на странице конференции.
10:00 - Леонидов Андрей Владимирович (Физический институт им. П.Н. Лебедева РАН)
10:50 - Gyula O. H. Katona (Rényi Institute of Mathematics)
11:40 - Карасёв Роман Николаевич (ИППИ РАН)
12:30 - Ланч
14:00 - Imre Bárány (Rényi Institute of Mathematics)
14:50 - Stefano Boccaletti (Institute for Complex Systems)
15:40 - Кабатянский Григорий Анатольевич (Сколтех)
16:30 - Кофе-брейк
17:00 - Дольников Владимир Леонидович (МФТИ)
17:30 - Обсуждение открытых проблем
_____
Приглашаем всех желающих! Темы и аннотации докладов, а также возможные изменения в расписании, смотрите на странице конференции.
💯5😎2🔥1