# Большой семинар лаборатории

По четвергам, 19:00
весенний семестр 2019 / 2020
Online
в zoom

Начинает работу семинар лаборатории комбинаторных и геометрических структур. Его основная цель - обзорные доклады на различные темы, преимущественно связанные с дискретной математикой. Начиная с 23 апреля семинар проводится на английском языке.

Встречи проходят в zoom
Meeting ID: 279-059-822
Password: первые 6 знаков числа $\pi$ после запятой

Также, вы можете написать Александру Полянскому (alexander.polyanskii@yandex.ru) или Максиму Жуковскому (zhukmax@gmail.com), чтобы получать email-рассылку о событиях лаборатории.

Руководители семинара: Максим Жуковский, Андрей Купавский, Янош Пах, Александр Полянский, Илья Шкредов.

Страница семинара на MathNet

Страница семинара на MathSeminars.org

Анонсы:
 October 22 19.00 MSK (UTC +3)

Robert Robere (McGill University)
Nullstellensatz Size-Degree Trade-offs from the Reversible Pebbling Game

We discuss recent work in which we establish a tight relationship between Nullstellensatz certificates of the so-called "pebbling" formulas — which play an important role in a variety of results in proof complexity, circuit complexity, and logic — and the "reversible pebbling game", a well-studied combinatorial pebbling game on directed graphs. To be precise: we show that a graph G can be reversibly pebbled in time t and space s if and only if there is a Nullstellensatz certificate of the pebbling formula over G in length t+1 and degree s. This result is independent of the underlying field of the Nullstellensatz certificate, and implies sharp bounds for other proof systems in the literature; furthermore, we can apply known reversible pebbling time-space tradeoffs to obtain strong length-degree trade-offs for Nullstellensatz certificates. To our knowledge these are the first strong tradeoffs known for this propositional proof system.

This is joint work with Susanna de Rezende, Or Meir and Jakob Nordstrom.

 October 29 19.00 MSK (UTC +3)

Julian Sahasrabudhe (University of Cambridge)
Combinatorial discrepancy in harmonic analysis

Given a collection of finite sets $A_1,..., A_n$ in $\{1,\ldots,n\}$, a basic problem in combinatorial discrepancy theory is to find a colouring $f : \{1,\ldots,n\} \rightarrow \{ \pm 1 \}$ so that each sum $\left| \sum_{x \in A_i} f(x) \right|$ is as small as possible. I will discuss how the sort of combinatorial and probabilistic reasoning used to think about problems in combinatorial discrepancy can used to solve an old conjecture of J.E. Littlewood in the area of harmonic analysis.

This talk is based on joint work with Balister, Bollobás, Morris and Tiba.

 November 5 19.00 MSK (UTC +3)

Wojciech Samotij (Tel Aviv University)
TBA

 November 19 19.00 MSK (UTC +3)

Noga Alon (Princeton University)
TBA

Архив:
 October 15 19.00 MSK (UTC +3)

Alexey Garber (The University of Texas Rio Grande Valley)
Voronoi conjecture for five-dimensional parallelohedra

In this talk I am going to discuss a well-known connection between lattices in $\mathbb{R}^d$ and convex polytopes that tile $\mathbb{R}^d$ with translations only.

My main topic will be the Voronoi conjecture, a century old conjecture which is, while stated in very simple terms, is still open in general. The conjecture states that every convex polytope that tiles $\mathbb{R}^d$ with translations can be obtained as an affine image of the Voronoi domain for some lattice.

I plan to survey several known results on the Voronoi conjecture and give an insight on a recent proof of the Voronoi conjecture in the five-dimensional case. The talk is based on a joint work with Alexander Magazinov.

 October 8 19.00 MSK (UTC +3)

Márton Naszódi (Loránd Eötvös University, Budapest)
John ellipsoid for log-concave functions

We extend the notion of the largest volume ellipsoid contained in a convex body to the setting of log-concave functions. As an application, we prove a quantitative Helly-type result about the integral of the pointwise minimum of a family of log-concave functions. Joint work with Grigory Ivanov.

 October 1 19.00 MSK (UTC +3)

Rob Morris (IMPA)
Erdős covering systems

A covering system of the integers is a finite collection of arithmetic progressions whose union is the set $\mathbb{Z}$. The study of these objects was initiated by Erdős in 1950, and over the following decades he asked a number of beautiful questions about them. Most famously, his so-called "minimum modulus problem" was resolved in 2015 by Hough, who proved that in every covering system with distinct moduli, the minimum modulus is at most $10^{16}$.

In this talk I will present a variant of Hough's method, which turns out to be both simpler and more powerful. In particular, I will sketch a short proof of Hough's theorem, and discuss several further applications. I will also discuss a related result, proved using a different method, about the number of minimal covering systems.

Joint work with Paul Balister, Béla Bollobás, Julian Sahasrabudhe and Marius Tiba.

 September 10 19.00 MSK (UTC +3)

Lutz Warnke (Georgia Institute of Technology)
Counting extensions in random graphs

We consider rooted subgraphs in random graphs, i.e., extension counts such as (a) the number of triangles containing a given root' vertex, or (b) the number of paths of length three connecting two given root' vertices. In 1989 Spencer gave sufficient conditions for the event that, whp, all roots of the binomial random graph G(n,p) have the same asymptotic number of extensions, i.e., $(1 \pm \epsilon)$ times their expected number. For the important strictly balanced case, Spencer also raised the fundamental question whether these conditions are necessary.

We answer this question by a careful second moment argument, and discuss some open problems and cautionary examples for the general case.

Based on joint work with Matas Sileikis, see arXiv:1911.03012

 September 3 19.00 MSK (UTC +3)

Zoltán Füredi (Rényi Institute, Budapest and University of Illinois, Urbana-Champaign)
A useful tool in combinatorics: Intersecting set-pair systems

The notion of cross intersecting set pair system (SPS) of size $m$, $\Big(\{A_i\}_{i=1}^m, \{B_i\}_{i=1}^m\Big)$ with $A_i\cap B_i=\emptyset$ and $A_i\cap B_j\ne\emptyset$, was introduced by Bollobás and it became an important tool of extremal combinatorics. His classical result states that $m\le {a+b\choose a}$ if $|A_i|\le a$ and $|B_i|\le b$ for each $i$.

After reviewing classical proofs, applications and generalizations, our central problem is to see how this bound changes with additional conditions.

In particular we consider $1$-cross intersecting set pair systems, where $|A_i\cap B_j|=1$ for all $i\ne j$.

We show connections to perfect graphs, clique partitions of graphs, and finite geometries. Many problems are proposed. Most new results is a joint work with A. Gyárfás and Z. Király.

 August 13 19.00 MSK (UTC +3)

Yufei Zhao (MIT, Boston)
The joints problem for varieties

We generalize the Guth-Katz joints theorem from lines to varieties. A special case of our result says that N planes (2-flats) in 6 dimensions (over any field) have $O(N^{3/2})$ joints, where a joint is a point contained in a triple of these planes not all lying in some hyperplane. Our most general result gives upper bounds, tight up to constant factors, for joints with multiplicities for several sets of varieties of arbitrary dimensions (known as Carbery's conjecture). Our main innovation is a new way to extend the polynomial method to higher dimensional objects.

Joint work with Jonathan Tidor and Hung-Hsun Hans Yu.

 July 30 19.00 MSK (UTC +3)

Pavel Valtr (Charles University, Prague)
Holes and islands in random point sets

For $d\ge 2$, let $S$ be a finite set of points in $\mathbb{R}^d$ in general position. A set $H$ of $k$ points from $S$ is a $k$-hole in $S$ if all points from $H$ lie on the boundary of the convex hull $\mathrm{conv}(H)$ of $H$ and the interior of $\mathrm{conv}(H)$ does not contain any point from $S$. A set $I$ of $k$ points from $S$ is a $k$-island in $S$ if $\mathrm{conv}(I)\cap S=I$. Note that each $k$-hole in $S$ is a $k$-island in $S$.

For fixed positive integers $d, k$ and a convex body $K$ in $\mathbb{R}^d$ with $d$-dimensional Lebesgue measure 1, let $S$ be a set of $n$ points chosen uniformly and independently at random from $K$. We show that the expected number of $k$-islands in $S$ is in $O(n^d)$. In the case $k=d+1$, we prove that the expected number of empty simplices (that is, $(d+1)$-holes) in $S$ is at most $2^{d-1}d!{n\choose d}$.

Our results improve and generalize previous bounds by Bárány and Füredi (1987), Valtr (1995), Fabila-Monroy and Huemer (2012), and Fabila-Monroy, Huemer, and Mitsche (2015). Joint work with Martin Balko and Manfred Scheucher.

 July 16 19.00 MSK (UTC +3)

Jozsef Solymosi (University of British Columbia)
Directions in an affine Galois plane and the clique number of the Paley graph

We prove that the number of directions determined by a set of the form A × B ⊂ AG(2,p), where p is prime, is at least |A||B| − min{|A|,|B|} + 2. We are using the polynomial method: the Rédei polynomial with Szőnyi's extension + a simple variant of Stepanov's method. As an application of the result, we obtain an upper bound on the clique number of the Paley graph.

Based on joint work with Daniel Di Benedetto and Ethan White.

 July 9 19.00 MSK (UTC +3)

Fedor Petrov (Steklov Mathematical Institute of Russian Academy of Sciences)
List colorings of direct products

Let $G=C_n\times C_m$ be a toroidal grid (that is, 4-regular graph), where $nm$ is even. We prove that this graph $G$ is 3-choosable. We also prove some more general results about list colorings of direct products. The proofs are algebraic, the starting point is Alon — Tarsi application of Combinatorial Nullstellensatz, and the main difficulty is to prove that the corresponding coefficient of the graph polynomial is non-zero.

The talk is based on joint results with Alexey Gordeev, Zhiguo Li and Zeling Shao. No preliminary knowledge is required.

 July 2 19.00 MSK (UTC +3)

József Balogh (University of Illinois)
Independent sets in regular graphs

Estimating the number of independent sets of regular graphs is in the center of attention recently.

The classical result of Korshunov and Sapozhenko in 1983 counts the number of independent sets in the hypercube, and then shows that typical independent sets are not far from the trivial construction. The main focus of the talk to prove similar results for the middle two layers of the hypercube.

This is partly joint work with Bela Bollobas, Ramon I. Garcia, Lina Li, Bhargav Narayanan, Andrew Treglown, Adam Zs. Wagner.

 June 25 19.00 MSK (UTC +3)

Alexander Razborov (University of Chicago and Steklov Mathematical Institute)
Limits of Dense Combinatorial Objects

The theory of limits of discrete combinatorial objects has been thriving for over a decade. There are two known approaches to it, one is geometric and semantic ("graph limits") and another is algebraic and syntactic ("flag algebras". The language of graph limits is more intuitive and expressive while flag algebras are more helpful when it comes to generalizations to combinatorial objects other than graphs, as well as to concrete calculations.

In this talk I will try to give a gentle introduction to the subject. Time permitting, I will talk about general ideas behind our joint research with Leonardo Coregliano attempting to build a unified theory using model-theoretical language and apply it to the study of quasi-randomness.

 June 18 19.00 MSK (UTC +3)

Jacob Fox (Stanford University)
Subset sums, completeness and colorings

We develop novel techniques which allow us to prove a diverse range of results relating to subset sums and complete sequences of positive integers, including solutions to several long standing open problems. These include: solutions to the three problems of Burr and Erdös on Ramsey complete sequences, for which Erdös later offered a combined total of 350 analogous results for the new notion of density complete sequences; the answer to a question of Alon and Erdös on the minimum number of colors needed to color the positive integers less than $n$ so that $n$ cannot be written as a monochromatic sum; the exact determination of an extremal function introduced by Erdös and Graham and first studied by Alon on sets of integers avoiding a given subset sum; and, answering a question of Tran, Vu and Wood, a common strengthening of seminal results of Szemerédi-Vu and Sárközy on long arithmetic progressions in subset sums.

Based on joint work with David Conlon and Huy Tuan Pham.

 June 11 19.00 MSK (UTC +3)

Grigory Kabatiansky (Skoltech, Moscow)
Cover-free families of sets, their generalizations and applications

We start from the following question:

What is the maximal number of subsets of a given finite set such that no one subset is covered by t others?

We present the history of this problem which was discovered under different names in group testing, coding theory and combinatorics. We consider variations of the problem, in particular, Renyi-Ulam search with a lie. Then we embed the problem into more general question: How to find unknown subset of a finite set?

 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.

 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.

 23 апреля 15:30

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

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

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