Big Seminar of Laboratory new

Big Seminar of the Laboratory

Thursdays
19.00 (MSK +3 UTC)
Online
Held in zoom
Upcoming talks
Click to scroll
Archive
Click to scroll
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 an email to Alexander Polyanskii (alexander.polyanskii@yandex.ru) or Maksim Zhukovskii (zhukmax@gmail.com) 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 MathSeminars.org

Upcoming talks
Considering the events in Ukraine and Russia we believe that it is appropriate to take a pause of the lab's Big Seminar. Mathematical research does never stop. We plan to resume the Big Seminar meetings in the Fall. If you feel like giving a talk in the seminar, please do contact us (through the list of organizers above). We will do our best to create a safe and comfortable space for learning, sharing, and collaborating. Truly yours, lab admins.
mar 3, 2022 19.00 MSK
Cancelled
David Ellis University of Bristol, UK
Some results around the Union Closed Conjecture
Abstract Abstract Video Slides

The celebrated Union Closed Conjecture of Peter Frankl states that if $F$ is a (non-trivial) union-closed family of subsets of a finite set $X$, then there exists an element of $X$ contained in at least half of the sets in $F$. Despite the efforts of many researchers over the last fifty years, and a recent Polymath project aimed at resolving it, the conjecture remains wide open. We discuss some recent results which demonstrate the limits of certain natural approaches to proving the conjecture (or to improving the known bounds for it). For example, we can show that for any positive integer $k$, there exists a finite union-closed family in which the (unique) smallest set has size $k$, but where each element of this set is contained in at most a $(((1+o(1))log_2(k))/(2k))$-fraction of all the sets in the family. This is asymptotically sharp, by results of Balla and of Wójcik. We will also discuss (if time permits) a strong counterexample to an approach (using 'average overlap densities') suggested in the Polymath project, and a newish (simple) proof of a very special case of the Union Closed Conjecture, viz., for union-closed families generated by all cyclic translates of a fixed subset of $Z/(nZ)$. Based on joint works with (subsets of) James Aaronson (Oxford), Maria-Romina Ivan (Cambridge) and Imre Leader (Cambridge).

Mar 17, 2022 19.00 MSK
Natan Rubin
Mar 24, 2022 19.00 MSK
Yaroslav Nešetřil
Mar 31, 2022 19.00 MSK
Ashwin Sah
Apr 7, 2022 19.00 MSK
Benny Sudakov
Apr 14, 2022 19.00 MSK
Cancelled
Richard Montgomery
Apr 21, 2022 19.00 MSK
Boris Bukh
Apr 28, 2022 19.00 MSK
Imre Ruzsa
May 12, 2022 19.00 MSK
Mehtaab Sawhney
May 19, 2022 19.00 MSK
Cosmin Pohoata
May 26, 2022 19.00 MSK
Cancelled
Lisa Sauermann

Testing Utreon

At the moment we are testing Utreon platform for publishing videos in order to get rid of unwanted advertisement. Utreon embeds sometimes may lead to increasing loading time or other performance issues on our website. If you are facing problems with loading video, please visit directly Labs' Channels on platforms:

Utreon page Youtube Channel
We apologize for the inconvenience!
Big Seminar Archive All202220212020
Feb 24, 2022 19.00 MSK
‪Géza Tóth Alfréd Rényi Institute of Mathematics
Abstract Abstract Video

The disjointness graph of a set system is a graph whose vertices are the sets, two being connected by an edge if and only if they are disjoint. It is known that the disjointness graph $G$ of any system of segments in the plane is $\chi$-bounded, that is, its chromatic number $\chi(G)$ is upper bounded by a function of its clique number $\omega(G)$.

We show that this statement does not remain true for systems of polygonal chains of length $2$. Moreover, for polygonal chains of length $3$ the disjointness graph have arbitrarily large girth and chromatic number. We discuss some other, related results.

Joint work with János Pach and Gábor Tardos.

Feb 17, 2022 19.00 MSK
Irit Dinur Weizmann institute of science, Israel
Abstract Abstract Video Slides

A locally testable code (LTC) is an error-correcting code that admits a very efficient membership test. The tester reads a constant number of (randomly - but not necessarily uniformly - chosen) bits from a given word and rejects words with probability proportional to their distance from the code.

LTCs were initially studied as important components of PCPs, and since then the topic has evolved on its own. High rate LTCs could be useful in practice: before attempting to decode a received word, one can save time by first quickly testing if it is close to the code.

An outstanding open question has been whether there exist LTCs that are "good" in the coding theory sense of having both constant relative distance and rate, and at the same time testable with a constant number of queries.

In this talk, I will describe a construction of such codes based on a new object called a left-right Cayley complex, which is a graph with squares. We will see how the expansion of this graph plays a key role.

Joint work with Shai Evra, Ron Livne, Alex Lubotzky, and Shahar Mozes.

Feb 10, 2022 19.00 MSK
Andrew Suk University of California San Diego
Abstract Abstract Video

The Ramsey number $r_k(s,n)$ is the minimum integer $N$, such that for any red/blue coloring of the $k$-tuples of ${1,2,...,N}$, there are s integers such that every $k$-tuple among them is red, or there are $n$ integers such that every $k$-tuple among them is blue. In this talk, I will discuss known upper and lower bounds for $r_k(s,n)$. I will also discuss another closely related function that was introduced by Erdős and Hajnal in 1972.

Dec 16, 2021 19.00 MSK
Dmitrii Zhelezov RICAM, Linz, Austria
Abstract Abstract Video

Rephrasing the celebrated Freiman lemma in additive combinatorics, one can show that a finite set in $Z^d$ containing a $K$-dimensional simplex has additive doubling at least ~$K$. We will discuss a novel framework for studying how such induced doubling can be inherited from a more general class of multi-dimensional subsets. It turns out that subsets of so-called quasi-cubes induce large doubling no matter the dimension of the ambient set. Time permitting, we will discuss how it allows to deduce a structural theorem for sets with polynomially large additive doubling and an application to the ”few products, many sums” problem of Bourgain and Chang.

This is joint work with I.Ruzsa, D. Matlosci, G. Shakan and D. Palvölgyi.

Dec 9, 2021 19.00 MSK
Vishesh Jain Stanford University
Abstract Abstract Video

Let $M_n$ be an $ntimes n$ random matrix whose entries are i.i.d copies of a discrete random variable $xi$. It has been conjectured that the dominant reason for the singularity of $M_n$ is the event that a row or column of $M_n$ is zero, or that two rows or columns of $M_n$ coincide (up to a sign). I will discuss joint work with Ashwin Sah (MIT) and Mehtaab Sawhney (MIT), towards the resolution of this conjecture.

Dec 2, 2021 19.00 MSK
Pawel Pralat Ryerson University
Abstract Abstract Video

The semi-random graph process is a single-player game that begins with an empty graph on n vertices. In each round, a vertex u is presented to the player independently and uniformly at random. The player then adaptively selects a vertex v and adds the edge uv to the graph. For a fixed monotone graph property, the objective of the player is to force the graph to satisfy this property with high probability in as few rounds as possible.

During the talk, we will focus on the following problems: a) perfect matchings, b) Hamilton cycles, c) constructing a subgraph isomorphic to an arbitrary fixed graph G. We will also consider a natural generalization of the process to s-uniform hypergraphs.

Nov 25, 2021 19.00 MSK
Andrey Kupavskii MIPT, Russia and CNRS, France
Abstract Abstract Video

Random restrictions is a powerful tool that played a central role in the breakthrough result by Alweiss et al. on the famous Erdos-Rado sunflower conjecture. In this talk, I will describe a new approach to getting a junta-type approximation for families of sets based on random restrictions. Such approximations have several exciting consequences, and I will present a couple of them. The first one is an upper bound on the size of regular k-uniform intersecting families similar to the one obtained by Ellis, Kalai and Narayanan for intersecting families under a much stronger restriction of being transitive. The second one is significant progress on the t-intersection (and the Erdos-Sos forbidden one intersection) problem for permutations. Improving and simplifying previous results, we show that the largest family of permutations [n] -> [n] avoiding pairs of permutations with intersection exactly t-1, has size at most (n-t)!, for t polynomial in n. Previously, this was only known for fixed t.

Joint work with Dmitriy Zakharov.

Nov 11, 2021 19.00 MSK
Pablo Soberón Baruch College, CUNY
Abstract Abstract Video

We study mass partition problems related to geometric transversals. In this talk, we focus on two problems. In the first, given a measure in $R^d$, we seek to split $R^d$ into few convex sets of equal measure so that every hyperplane misses the interior of many regions. In the second, we extend recent ham sandwich results on Grassmannians to impose geometric constraints on the dividing subspaces. The topological backbone of both problems is the same, and relies on extensions of the Borsuk—Ulam theorem to Stiefel manifolds. The contents of this talk are joint work with Ilani Axelrod-Freed and Michael Manta.

Nov 4, 2021 19.00 MSK
Matthew Kwan IST Austria
Abstract Abstract Video

Resolving a conjecture of Füredi, we prove that almost every n-vertex graph admits a partition of its vertex set into two parts of equal size in which almost all vertices have more neighbours on their own side than across. Our proof involves some new techniques for studying processes driven by degree information in random graphs, which may be of general interest.

Oct 28, 2021 19.00 MSK
Alexey Pokrovskiy University College London
Abstract Abstract Video

This talk will be about taking a coloured multigraph and finding a rainbow matching using every colour. There's a variety of conjectures that guarantee a matching like this in various classes of multigraphs (eg the Aharoni-Berger Conjecture). In the talk, I'll discuss an easy technique to prove asymptotic versions of conjectures in this area.

This is joint work with David Munhá Correia and Benny Sudakov.

Jun 8, 2021 13.00 MSK
Noga Alon Princeton and Tel Aviv
Abstract Abstract Video

Let N be a random necklace with km beads of each of t types. What is the typical minimum number of points in which one can cut N so that it will be possible to partition the resulting intervals of beads into k collections, each containing exactly m beads of each type? It is known that this number is at most (k-1)t with probability 1; is it typically significantly smaller?

I will discuss a recent joint work with Dor Elboim, Janos Pach and Gabor Tardos addressing this problem and showing that it is connected to several seemingly unrelated topics, including matchings in nearly regular hypergraphs and random walks in Euclidean spaces.

Please note the unusual time and day for our Big Seminar. The talk is a part of the online event Round the World Relay in Combinatorics - follow the link to see the schedule, there are lots of other interesting talks.

May 20, 2021 19.00 MSK
Alexander Gaifullin Skoltech, Steklov Mathematical Institute of RAS
Abstract Abstract Video

Flexible polyhedra are polyhedral surfaces with rigid faces and hinges at edges that admit non-trivial deformations, that is, deformations not induced by ambient isometries of the space. Main steps in theory of flexible polyhedra are: Bricard’s construction of self-intersecting flexible octahedra (1897), Connelly’s construction of flexors, i.e., non-self-intersecting flexible polyhedra (1977), and Sabitov’s proof of the Bellows conjecture claiming that the volume of any flexible polyhedron remains constant during the flexion (1996). In my talk I will give a survey of these classical results and ideas behind them, as well as of several more recent results by the speaker, including the proof of Strong Bellows conjecture claiming that any flexible polyhedron in Euclidean three-space remains scissors congruent to itself during the flexion (joint with Leonid Ignashchenko, 2017).

May 6, 2021 19.00 MSK
Alex Cohen Yale University, US
Abstract Abstract Video

We prove that the slice rank of a 3-tensor (a combinatorial notion introduced by Tao in the context of the cap-set problem), the analytic rank (a Fourier-theoretic notion introduced by Gowers and Wolf), and the geometric rank (a recently introduced algebro-geometric notion) are all equivalent up to an absolute constant. The proof uses tools from algebraic geometry to argue about tangent spaces to certain determinantal varieties corresponding to the tensor. Our result settles open questions of Haramaty and Shpilka [STOC 2010], and of Lovett [Discrete Anal., 2019] for 3-tensors.

Joint work with Guy Moshkovitz.

Apr 29, 2021 19.00 MSK
Avi Wigderson Institute for Advanced Study, Princeton
Abstract Abstract Video

This talk aims to summarize the status and goals of a broad research project. The main messages of this project are summarized below; I plan to describe, through examples, many of the concepts they refer to, and the evolution of ideas leading to them. No special background is assumed.

  1. We extend some basic algorithms of convex optimization from Euclidean space to the far more general setting of Riemannian manifolds, capturing the symmetries of non-commutative group actions. The main tools for analyzing these algorithms combine central results from invariant and representation theory.
  2. One main motivation for studying these problems and algorithms comes from algebraic complexity theory, especially attempts to separate Valiant’s algebraic analogs of the P and NP. Symmetries and group actions play a key role in these attempts.
  3. The new algorithms give exponential (or better) improvements in run-time for solving algorithmic many specific problems across CS, Math and Physics. In particular, in algebra (testing rational identities in non-commutative variables), in analysis (testing the feasibility and tightness of Brascamp-Lieb inequalities), in quantum information theory (to the quantum marginals problem), optimization (testing membership in “moment polytopes”), and others. This work exposes old and new connections between these diverse areas.

Based on many joint works in the past 5 years, with Zeyuan Allen-Zhu, Peter Burgisser, Cole Franks, Ankit Garg, Leonid Gurvits, Pavel Hrubes, Yuanzhi Li, Visu Makam, Rafael Oliveira and Michael Walter.

Apr 22, 2021 19.00 MSK
Liana Yepremyan London School of Economics
Abstract Abstract Video

The $s$-colour size-Ramsey number of a hypergraph $H$ is the minimum number of edges in a hypergraph $G$ whose every $s$-edge-colouring contains a monochromatic copy of $H$.

We show that the $s$-colour size-Ramsey number of the $t$-power of the $r$-uniform tight path on $n$ vertices is linear in $n$, for every fixed $r, s, t$, thus answering a question of Dudek, La Fleur, Mubayi, and Rödl (2017).

In fact, we prove a stronger result that allows us to deduce that powers of bounded degree hypergraph trees and of `long subdivisions' of bounded degree hypergraphs have size-Ramsey numbers that are linear in the number of vertices. This extends recent results about the linearity of size-Ramsey numbers of powers of bounded degree trees and of long subdivisions of bounded degree graphs.

This is joint work with Shoham Letzter and Alexey Pokrovskiy.

Apr 15, 2021 19.00 MSK
Alex Scott University of Oxford
Abstract Abstract Video

The Two Families Theorem of Bollobas says the following: Let $(A_i,B_i)$ be a sequence of pairs of sets such that the $A_i$ have size a, the $B_i$ have size $b$, and $A_i$ and $B_j$ intersect if and only if i and j are distinct. Then the sequence has length at most $binom{a+b}{a}$.

This beautiful result has many applications and has been generalized in two distinct ways. The first (which follows from the original result of Bollobas) allows the sets to have different sizes, and replaces the cardinality constraint with a weighted sum. The second uses an elegant exterior algebra argument due to Lovasz and allows the intersection condition to be replaced by a skew intersection condition. However, there are no previous results that have versions of both conditions.

In this talk, we will explain and extend the exterior algebra approach. We investigate the combinatorial structure of subspaces of the exterior algebra of a finite-dimensional real vector space, working in parallel with the extremal combinatorics of hypergraphs. As an application, we prove a new extension of the Two Families Theorem that allows both (some) variation in set sizes and a skew intersection condition.

This is joint work with Elizabeth Wilmer (Oberlin).

Apr 8, 2021 19.00 MSK
Anuj Dawar University of Cambridge
Abstract Abstract Video

It is a long-standing open question in complexity theory to show that the permanent of a matrix cannot be computed by a polynomial-size arithmetic circuit. We proved an exponential lower bound on the size of any family of symmetric arithmetic circuits for computing the permanent. Here, symmetric means that the circuit is invariant under simultaneous row and column permutations of the matrix. In this talk, I will explain the game-based lower-bound methods and show how they can be used for deriving further lower bounds, varying symmetry groups and other matrix polynomials, such as the determinant.

Joint work with Gregory Wilsenach.

Apr 1, 2021 19.00 MSK
Yuval Wigderson Stanford University
Abstract Abstract Video Slides

What is the smallest number of hyperplanes needed to cover the vertices of the hypercube ${0, 1}^n$? At least two hyperplanes are needed, and since we may take the parallel hyperplanes $x_1=0$ and $x_1=1$, we see that two hyperplanes suffice.

Although the question above is not particularly interesting, there are many interesting variants of it, with connections to discrete geometry, infinite Ramsey theory, theoretical computer science, extremal combinatorics, and beyond. One such question is the following: how many hyperplanes are needed to cover all vertices of the hypercube except the origin, while not covering the origin? Here, Alon and Füredi proved that at least $n$ hyperplanes are needed, and it is easy to see that $n$ hyperplanes also suffice.

Although these problems are geometric in nature, all known proofs of the Alon–Füredi theorem use algebraic techniques, relating the hyperplane covering problem to a polynomial covering problem and then resolving this latter problem. Miraculously, the geometric problem and its algebraic relaxation turn out to have the same answer. In this talk, I will survey some results and questions about covers of the hypercube, and then discuss a recent result showing that for a natural higher-multiplicity version of the Alon–Füredi theorem proposed by Clifton and Huang, the geometric and algebraic problems (probably) have very different answers.

Joint work with Lisa Sauermann.

Mar 25, 2021 19.00 MSK
Igor Pak University of California, Los Angeles
Abstract Abstract Video

I will give a broad survey of the recent progress on counting integer points in polytopes of bounded dimension. I will emphasize both computational complexity aspects and applications which range from graph enumeration to Kronecker coefficients. The talk is aimed at a general audience.

Mar 18, 2021 19.00 MSK
Andrei Bulatov Simon Fraser University, Canada
Abstract Abstract Video

We consider the Ideal Membership Problem (IMP for short), in which we are given real polynomials $f_0,f_1,..., f_k$ and the question is to decide whether $f_0$ belongs to the ideal generated by $f_1,...,f_k$. In the more stringent version the task is also to find a proof of this fact. The IMP underlies many proof systems based on polynomials such as Nullstellensatz, Polynomial Calculus, and Sum-of-Squares. In the majority of such applications the IMP involves so called combinatorial ideals that arise from a variety of discrete combinatorial problems. This restriction makes the IMP significantly easier and in some cases allows for an efficient algorithm to solve it.

In 2019 Mastrolilli initiated a systematic study of IMPs arising from Constraint Satisfaction Problems (CSP) of the form CSP(G), that is, CSPs in which the type of constraints is limited to relations from a set G. He described sets G on a 2-element set that give rise to polynomial time solvable IMPs and showed that for the remaining ones the problem is hard. We continue this line of research.

First, we show that many CSP techniques can be translated to IMPs thus allowing us to significantly improve the methods of studying the complexity of the IMP. We also develop universal algebraic techniques for the IMP that have been so useful in the study of the CSP. This allows us to prove a general necessary condition for the tractability of the IMP, and three sufficient ones. The sufficient conditions include IMPs arising from systems of linear equations over GF(p), p prime, and also some conditions defined through special kinds of polymorphisms.

Mar 4, 2021 19.00 MSK
Dömötör Pálvölgyi Eötvös Loránd University, Hungary
Abstract Abstract Video

We improve the upper bound for the maximum possible number of stable matchings among n men and n women from $O(131072^n)$ to $O(4.47^n)$. To establish this bound, we develop a novel formulation of a probabilistic technique that is easy to apply and may be of independent interest in counting other combinatorial objects. Joint work with Cory Palmer.

Feb 25, 2021 19.00 MSK
Alexander Kolpakov University of Neuchâtel, Switzerland
Abstract Abstract Video

We classify all sets of nonzero vectors in $mathbb{R}^3$ such that the angle formed by each pair is a rational multiple of $pi$. The special case of four-element subsets lets us classify all tetrahedra whose dihedral angles are multiples of $pi$, solving a 1976 problem of Conway and Jones: there are $2$ one-parameter families and $59$ sporadic tetrahedra, all but three of which are related to either the icosidodecahedron or the $B_3$ root lattice. The proof requires the solution in roots of unity of a $W(D_6)$-symmetric polynomial equation with $105$ monomials (the previous record was only $12$ monomials). This is a joint work with Kiran S. Kedlaya, Bjorn Poonen, and Michael Rubinstein.

Feb 11, 2021 19.00 MSK
Misha Rudnev University of Bristol, UK
Abstract Abstract Video

We'll review the state of the art of the finite field version of the Erdös distinct distance problem and its variations. Recently there has been some interesting work in two and three dimensions. In particular, it was shown that in order that a point set in $F_p^2$ define a positive proportion of the feasible $p$ distances, its cardinality needs to be bigger than $p^{5/4}$. This improved the earlier lower bound $q^{4/3}$, which holds over $F_q$, and for $q$ non-prime cannot be improved. Coincidentally, the same quantitative improvement was recently made as to the Falconer problem in $R^2$, using decoupling, which seems to be very far from the incidence geometric approach over $F_p$ to be outlined.

Dec 17, 2020 19.00 MSK
Sergey Avvakumov University of Copenhagen, Denmark
Abstract Abstract Video

A practical way to encode a manifold is to triangulate it. Among all possible triangulations it makes sense to look for the minimal one, which for the purpose of this talk means using the least number of vertices.

Consider now a family of manifolds such as $S^n$, ${mathbb R}P^n$, $SO_n$, etc. A natural question is how the size of the minimal triangulation depends on $n$? Surprisingly, except for the trivial case of $S^n$, our best lower and upper bounds are very far apart.

For ${mathbb R}P^n$ the current best lower and upper bounds are around $n^2$ and $phi^n$, respectively, where $phi$ is the golden ratio. In this talk I will present the first triangulation of ${mathbb R}P^n$ with a subexponential, $e^{(frac{1}{2}+o(1))sqrt{n}{log n}}$, number of vertices. I will also state several open problems related to the topic.

This is a joint work with Karim Adiprasito and Roman Karasev.

Dec 10, 2020 19.00 MSK
Xavier Pérez-Giménez University of Nebraska-Lincoln
Abstract Abstract Video

An $n$-lift of a graph $G$ is a graph from which there is an $n$-to-$1$ covering map onto $G$. Amit, Linial, and Matoušek (2002) raised the question of whether the chromatic number of a random $n$-lift of $K_5$ is concentrated on a single value. We consider a more general problem, and show that for fixed $dge 3$ the chromatic number of a random lift of $K_d$ is (asymptotically almost surely) either $k$ or $k+1$, where $k$ is the smallest integer satisfying $d < 2k log k$. Moreover, we show that, for roughly half of the values of $d$, the chromatic number is concentrated on $k$. The argument for the upper-bound on the chromatic number uses the small subgraph conditioning method, and it can be extended to random $n$-lifts of $G$, for any fixed $d$-regular graph $G$. (This is joint work with JD Nir.)

Nov 19, 2020 19.00 MSK
Noga Alon Princeton and Tel Aviv
Abstract Abstract Video

A substantial number of results and conjectures deal with the existence of a set of prescribed type which contains a fair share from each member of a finite collection of objects in a space, or the existence of partitions in which this is the case for every part. Examples include the Ham-Sandwich Theorem in Measure Theory, the Hobby-Rice Theorem in Approximation Theory, the Necklace Theorem and the Ryser Conjecture in Discrete Mathematics, and more. The techniques in the study of these results combine combinatorial, topological, geometric and algebraic tools.

I will describe the topic, focusing on several recent existence results and their algorithmic aspects.

Nov 12, 2020 19.00 MSK
Andrei Vesnin Tomsk State University
Abstract Abstract Video

We will consider a class of polytopes which can be realized in a hyperbolic space with all dihedral angled equal to $pi/2$. Since this class contains fullerene polytopes, we will describe fullerene graphs with maximal Wiener index. We will discuss combinatorics and volumes of right-angles polytopes, construction of 3-manifolds from right-angled blocks, and knots and links related to such manifolds.

Talk is based on joint works with A. Dobrynin [1] and A. Egorov [2,3].

References:

  1. A. Dobrynin, A. Vesnin, On the Wiener Complexity and the Wiener Index of Fullerene Graphs, Mathematics, 2019, 7(11), 1071, 16 pp.
  2. A. Egorov, A. Vesnin, Volume estimates for right-angled hyperbolic polyhedra, preprint arXiv:2010.11147, 12pp.
  3. A. Egorov, A. Vesnin, On correlation of hyperbolic volumes of fullerenes with their properties, submitted, 24 pp.
Nov 5, 2020 19.00 MSK
Wojciech Samotij Tel Aviv University
Abstract Abstract Video Slides

Given graphs $G$ and $H$ and an integer $r ge 2$, we write $G to (H)_r$ if every $r$-colouring of the edges of $G$ contains contains a monochromatic copy of $H$. It follows from Ramsey's theorem that, when $n$ is sufficiently large, $G to (H)_r$ is a nontrivial, monotone property of subgraphs $G$ of $K_n$. The celebrated work of Rödl and Ruciński from the 1990s located the threshold for this property in the binomial random graph $G_{n,p}$ for all $H$ and $r$. We prove that this threshold is sharp when $H$ is a clique or a cycle, for every number of colours $r$; this extends earlier results of Friedgut, Rödl, Ruciński, and Tetali and of Schacht and Schulenburg.

This is joint work with Ehud Friedgut, Eden Kuperwasser, and Mathias Schacht.

Oct 29, 2020 19.00 MSK
Julian Sahasrabudhe University of Cambridge
Abstract Abstract Video

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.

Oct 22, 2020 19.00 MSK
Robert Robere McGill University
Abstract Abstract Video

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.

Oct 15, 2020 19.00 MSK
Alexey Garber The University of Texas Rio Grande Valley
Abstract Abstract Video Slides + Notes

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.

Oct 8, 2020 19.00 MSK
Márton Naszódi Loránd Eötvös University, Budapest
Abstract Abstract Video

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.

Oct 1, 2020 19.00 MSK
Robert Morris IMPA
Abstract Abstract Video

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.

Sep 10, 2020 19.00 MSK
Lutz Warnke Georgia Institute of Technology
Abstract Abstract Video

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

Sep 3, 2020 19.00 MSK
Zoltán Füredi Rényi Institute, Budapest and University of Illinois, Urbana-Champaign
Abstract Abstract Video

The notion of cross intersecting set pair system (SPS) of size $m$, $Big({A_i}_{i=1}^m, {B_i}_{i=1}^mBig)$ with $A_icap B_i=emptyset$ and $A_icap B_jneemptyset$, was introduced by Bollobás and it became an important tool of extremal combinatorics. His classical result states that $mle {a+bchoose 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_icap B_j|=1$ for all $ine 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.

Aug 13, 2020 19.00 MSK
Yufei Zhao MIT, Boston
Abstract Abstract Video Slides

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.

Jul 30, 2020 19.00 MSK
Pavel Valtr Charles University, Prague
Abstract Abstract Video

For $dge 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!{nchoose 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.

Jul 16, 2020 19.00 MSK
Jozsef Solymosi University of British Columbia
Abstract Abstract Video

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.

Jul 9, 2020 19.00 MSK
Fedor Petrov Steklov Mathematical Institute of Russian Academy of Sciences
Abstract Abstract Video

Let $G=C_ntimes 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.

Jul 2, 2020 19.00 MSK
József Balogh University of Illinois
Abstract Abstract Video

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.

Jun 25, 2020 19.00 MSK
Alexander Razborov University of Chicago and Steklov Mathematical Institute
Abstract Abstract Video

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.

Jun 18, 2020 19.00 MSK
Jacob Fox Stanford University
Abstract Abstract Video

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.

Jun 11, 2020 19.00 MSK
Grigory Kabatiansky Skoltech, Moscow
Abstract Abstract Video

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?

Jun 4, 2020 19.00 MSK
Daniel Korandi University of Oxford, UK
Abstract Abstract Video

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, 2020 19.00 MSK
David Conlon Caltech
Abstract Abstract Video

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, 2020 19.00 MSK
Dor Minzer IAS, Princeton
Abstract Abstract Video

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 $mgeq 3$.

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

May 14, 2020 19.00 MSK
Will Perkins UIC Chicago
Abstract Abstract Video Slides

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, 2020 19.00 MSK
Oleg R. Musin University of Texas Rio Grande Valley
Abstract Abstract Video

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.

Apr 30, 2020 19.00 MSK
Bhargav Narayanan Rutgers University, USA
Abstract Abstract Video

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.

Apr 23, 2020 19.00 MSK
Brendan McKay Australian National University
Abstract Abstract Video

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$.

Apr 9, 2020 19.10 MSK
Александр Эмилевич Гутерман МГУ
Функция перманента матриц и ее значения
Abstract Abstract

Доклад основан на работах [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.
Mar 26, 2020 19.10 MSK
Владимир Юрьевич Протасов L'Aquila, МГУ и Высшая Школа Экономики
Abstract Abstract Video Slides

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

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

Mar 12, 2020 19.10 MSK
Мощевитин Николай Германович МГУ
Abstract Abstract Video

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

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

Mar 5, 2020 19.10 MSK
Верещагин Н.К. МГУ и ВШЭ
Abstract Abstract Video

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

Feb 27, 2020 19.10 MSK
Шкредов И.Д. МИАН, МГУ, МФТИ
Abstract Abstract Video

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