Это канал Лаборатории комбинаторных и геометрических структур МФТИ.
Основные направления исследований лаборатории:
• Экстремальная комбинаторика
• Дискретная геометрия
• Теоретическая информатика
• Связи комбинаторики с алгоритмами и оптимизацией
Здесь мы будем публиковать анонсы семинаров и научных мероприятий, новости лаборатории, информация о курсах, воркшопах, школах и открытых возможностях. Записи семинаров и материалы прошлых мероприятий доступны на сайте 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👍1🐳1