Big Seminar of Laboratory

Big Seminar of Laboratory

spring 2020
Held in zoom
Seminar page

Big Seminar by Laboratory on Combinatorial and Geometric Structures from now on will be in English. The seminar aims to expose various works and topics connected to discrete mathematics. Since it is a broad field we suggest that the key terms and concepts are explained during the talks.

The seminar is held in zoom
Meeting ID: 279-059-822
Password: First six digits of $\pi$ after the decimal point

You can also write a letter to Alexander Polyanskii ( or Maksim Zhukovskii ( if you want to be added to the mailing list.

Organizers:Andrey Kupavskii, János Pach, Alexander Polyanskii, Ilya Shkredov, Maksim Zhukovskii.

Seminar page on the MathNet

Seminar page on the

June 4 19.00 MSK (UTC +3)

Daniel Korandi (University of Oxford, UK)
«Exact stability for Turán's theorem»

Turán's theorem says that an extremal $K_{r+1}$-free graph is $r$-partite. The Stability Theorem of Erdös and Simonovits shows that if a $K_{r+1}$-free graph with n vertices has close to the maximal $t_r(n)$ edges, then it is close to being $r$-partite. In this talk we determine exactly the $K_{r+1}$-free graphs with at least m edges that are farthest from being $r$-partite, for any $m > t_r(n) - δn^2$. This extends work by Erdös, Györi and Simonovits, and proves a conjecture of Balogh, Clemen, Lavrov, Lidický and Pfender. Joint work with Alexander Roberts and Alex Scott.

June 11 19.00 MSK (UTC +3)

Grigory Kabatiansky (Skoltech, Moscow)

June 18 19.00 MSK (UTC +3)

Jacob Fox (Stanford University)

June 25 19.00 MSK (UTC +3)

Alexander Razborov (University of Chicago)

July 2 19.00 MSK (UTC +3)

Jozsef Balogh (University of Illinois)

May 28 19.00 MSK (UTC +3)

David Conlon (Caltech)
«Recent progress in extremal graph theory»

The extremal number ex(n, H) of a graph H is the largest number of edges in an n-vertex graph containing no copy of H. In this talk, we will describe some of the recent progress that has been made on understanding this question in the difficult case when H is bipartite.

May 21 19.00 MSK (UTC +3)

Dor Minzer (IAS, Princeton)
«New sharp thresholds results and applications in extremal combinatorics»

The classical hypercontractive inequality for the Boolean hypercube lies at the core of many results in analysis of Boolean functions. Though extensions of the inequality to different domains (e.g. the biased hypercube) are known, they are often times quantitatively weak, making them harder to apply.

We will discuss new forms of this inequality and some of their consequences, such as qualitatively tight version of Bourgain's sharp threshold theorem, as well as a variant that applies for sparse families. Time permitting, we will also discuss applications to two problems in extremal combinatorics: the (cross version) of the Erdos matching conjecture, and determining the extremal size of families of vectors in $\{0,1,...,m-1\}^n$ avoiding a fixed intersection size, for $m\geq 3$.

Based on joint works with Peter Keevash, Noam Lifshitz and Eoin Long.

May 14 19.00 MSK (UTC +3)

Will Perkins (UIC Chicago)
«Counting independent sets with the cluster expansion»

I'll present two tools from statistical physics, abstract polymer models and the cluster expansion, and show how they can be used in extremal and enumerative combinatorics to give very good approximations to the number of (weighted) independent sets in certain graphs. In one application we use the cluster expansion in concert with Sapozhenko's container lemma (and Galvin's generalization) to obtain new results on the weighted number of independent sets in the hypercube and their typical structure. Joint work with Matthew Jenssen.

May 7 19.00 MSK (UTC +3)

Oleg R. Musin (University of Texas Rio Grande Valley)
«Sphere Packings in Four Dimensions»

In this talk I'm going discuss reasonable approaches for solutions to problems related to densest sphere packings in 4-dimensional Euclidean space. I consider two long--standing open problems: the uniqueness of maximum kissing arrangements in 4 dimensions and the 24--cell conjecture. Note that a proof of the 24-cell conjecture also proves that $D_4$ is the densest sphere packing in 4 dimensions.

April 30 19.00 MSK (UTC +3)

Bhargav Narayanan (Rutgers University, USA)
«Finding homeomorphs»

A number of interesting problems at the interface of topology and combinatorics arise when we view r-uniform hypergraphs as (r-1)-dimensional simplicial complexes. I’ll talk about some recent developments around the Dirac and Turan problems for 3-graphs or equivalently, 2-complexes.

April 23 15.30 MSK (UTC +3)

Brendan McKay (Australian National University)
«Complex Martingales and Regular Graphs»

Based on the joint work with Mikhail Isaev from Monash University & MIPT.

The asymptotic enumeration of regular graphs, and more generally of graphs with specified degree sequences, has occupied combinatorialists for a long time. We will start with a survey of previous results, with a quick summary of the methods used. Then we will focus on the application of complex-analytic methods to degree sequences that are sufficiently dense. Next we will show how a general theorem on complex martingales can be applied to the estimation of the necessary integrals. Then we will apply a theorem of Isaev on cumulant expansions to find an asymptotic expansion for the number of regular graphs of degree at least $n^t$ for some $t>0$.

9 апреля 19:10 - 20:30

Александр Эмилевич Гутерман (МГУ)
«Функция перманента матриц и ее значения»

Доклад основан на работах [2, 3, 4, 5].

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

Среди вопросов, которые будут обсуждаться в докладе:

  • проблема Полиа конвертации перманента и определителя [7],
  • проблема Брюальди-Ньюмана существования границы подряд идущих значений перманента (0,1)-матриц [1],
  • положительное решение проблемы Ванга-Кройтера, поставленной в 1974, [6, 8], полученное в [2].

Список литературы

  1. R. A. Brualdi, M. Newman, Some theorems on permanent, J. Res. Natl. Bur. Stand., Sect. B 69B:3 (1965) 159–163.
  2. M.V. Budrevich, A.E. Guterman, Krauter conjecture on permanents is true, Journal of Combinatorial Theory – Ser. A, 162 (2019) 306-343.
  3. M. Budrevich, G. Dolinar, A. Guterman, B. Kuzma, Graph characterization of fully indecomposable nonconvertible (0,1)-matrices with minimal number of ones, Ars Mathematica Contemporanea, 17:1 (2019) 141-151
  4. G. Dolinar, A.E. Guterman, B. Kuzma, M. Orel, On the Polya permanent problem over finite fields, European J. of Combinatorics, 32 (2011) 116-132.
  5. A.E. Guterman, K.A. Taranin, On the values of the permanent of (0,1)-matrices, Linear Algebra and Its Application, 552 (2018) 256-276.
  6. A.R. Krauter, Recent results on permanents of (+1, -1)-matrices, Ber. No. 249, Berichte, 243-254, Forschungszentrum Graz, Graz, 1985.
  7. G. Polya, Aufgabe, 424, Arch. Math. Phys. 20:3 (1913) 271.
  8. E.T.H. Wang, On permanents of (+1, -1)-matrices, Israel J. Math., 18 (1974) 353-361.

26 марта 19:10 - 20:30

Владимир Юрьевич Протасов (L'Aquila, МГУ и Высшая Школа Экономики)
«Максимальный ацикличный подграф и устойчивость динамических систем»

Проблема MAS (Maximal Acyclic Subgraph) состоит в том, чтобы убрать из заданного ориентированного графа все циклы, при этом оставив наибольшее возможное число его ребер. Это — одна из классических NP-полных задач. В настоящее время не известно ни одного алгоритма, который давал бы ее приближенное решение с коэффициентом приближения большим 1/2 (коэффициент 1/2 получить легко). Оказывается, задача MAS тесно связана с задачей стабилизации динамической системы — задачей нахождения ближайшей устойчивой линейной системы. Это позволяет применить к задаче MAS методы из теории устойчивости линейных систем. Мы, в частности, увидим, что некоторая ослабленная версия MAS может быть решена явно даже для относительно больших графов, а для самой задачи MAS построим алгоритм, дающий хорошие численные результаты приближенного решения. Заодно поговорим о возможных приложениях в математической экономике (модель Леонтьева) и экологии (популяционная динамика).

Часть результатов получены совместно с А.Цветковичем (институт Гран Сассо, Италия).

12 марта 19:10 - 20:30

Мощевитин Николай Германович (МГУ)
«Неравенства для диофантовых экспонент»

Взаимосвязь задачи об обыкновенных приближениях нескольких чисел и о равномерных приближениях этих же чисел была обнаружена в работах В. Ярника в 30 - 50-е годы 20 века. Результаты Ярника были быстро забыты. Они были переоткрыты в конце 20 века в работах различных математиков. Особо примечательной была концепция В.М. Шмидта и Л. Зуммерера, получившая название «Параметрическая геометрии чисел». В частности, Шмидт и Зуммере предположили, что оптимальное соотношение между обыкновенными и равномерными приближениями достигается на числах, для которых граф логарифмов последовательных минимумов является "регулярным". Эта гипотеза была доказана А. Марна и Н. Мощевитиным, а более простое доказательство недавно получено В.Нгуен, А. Поельсом и Д. Руа.

В докладе будет рассказано о всех соответствующих гипотезах, результатах и приложениях.

5 марта 19:10 - 20:30

Верещагин Н.К. (МГУ и ВШЭ)
«Cамоподобные замощения плоскости многоугольниками»

Пусть дано конечное семейство многоугольников $F$ и действительное число $k$ такие, что каждый многоугольник из $F$ можно разрезать на многоугольники, подобные многоугольникам из $F$ с коэффициентом подобия $k$. Пусть также зафиксирована такая схема разрезания $S$. Тогда тройке $k,F,S$ естественным образом сопоставляется семейство замощений плоскости многоугольниками из $F$. Замощения этого семейства называются самоподобными замощениями, задаваемыми $k,F,S$. Интерес к самоподобным замощениям связан с тем, что все они апериодичны. Примером самоподобных замощений являются замощения Пенроуза.

27 февраля 19:10 - 20:30

Шкредов И.Д. (МИАН, МГУ, МФТИ)
«Суммы произведений: от теории чисел к росту в группах и обратно»

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