Big Seminar of Laboratory

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:
Dec 2, 2021 19.00 MSK (UTC +3)

Pawel Pralat (Ryerson University)
Semi-random process

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.

Dec 9, 2021 Vishesh Jain 19.00 MSK (UTC +3)

Vishesh Jain

Dec 16, 2021 Dmitrii Zhelezov 19.00 MSK (UTC +3)

Dmitrii Zhelezov

Feb 10, 2022 Andrew Suk 19.00 MSK (UTC +3)

Andrew Suk

Feb 17, 2022 Irit Dinur 19.00 MSK (UTC +3)

Irit Dinur

March 3, 2022 David Ellis 19.00 MSK (UTC +3)

David Ellis

April 14, 2022 Richard Montgomery 19.00 MSK (UTC +3)

Richard Montgomery

Big Seminar Archive:
Nov 25, 2021 19.00 MSK (UTC +3)

Andrey Kupavskii (MIPT, Russia and CNRS, France)
Random restrictions and forbidden intersections

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 (UTC +3)

Pablo Soberón (Baruch College, CUNY)
Mass partitions, transversals, and Stiefel manifolds

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 (UTC +3)

Matthew Kwan (IST Austria)
Friendly bisections of random graphs

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 (UTC +3)

Alexey Pokrovskiy (University College London)
Rainbow matchings in coloured multigraphs

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

June 8, 2021 13.00 MSK (UTC +3)

Noga Alon (Princeton and Tel Aviv)
Splitting Random Necklaces

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 (UTC +3)

Alexander Gaifullin (Skoltech, Steklov Mathematical Institute of RAS)
"Flexible polytopes"

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 (UTC +3)

Alex Cohen (Yale University, US)
"Equivalence of 3-tensor ranks"

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.

April 29, 2021 19.00 MSK (UTC +3)

Avi Wigderson (Institute for Advanced Study, Princeton)
"Optimization, Complexity and Math (or, can we prove P ≠ NP using gradient descent)"

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.

April 22, 2021 19.00 MSK (UTC +3)

Liana Yepremyan (London School of Economics)
Size-Ramsey numbers of powers of hypergraph trees and long subdivisions

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.

April 15, 2021 19.00 MSK (UTC +3)

Alex Scott (University of Oxford)
Combinatorics in the exterior algebra and the Two Families Theorem

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

April 8, 2021 19.00 MSK (UTC +3)

Anuj Dawar (University of Cambridge)
Circuit Lower Bounds Assuming Symmetry

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.

April 1, 2021 19.00 MSK (UTC +3)

Yuval Wigderson (Stanford University)
Covering the hypercube with geometry and algebra

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.

March 25, 2021 19.00 MSK (UTC +3)

Igor Pak (University of California, Los Angeles)
Counting integer points in polytopes

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.

March 18, 2021 19.00 MSK (UTC +3)

Andrei Bulatov (Simon Fraser University, Canada)
On the Complexity of CSP-based Ideal Membership Problems

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.

March 11, 2021 19.00 MSK (UTC +3)

No talk
We'll be on the Workshop on Euclidean Ramsey Theory.

March 4, 2021 19.00 MSK (UTC +3)

Dömötör Pálvölgyi (Eötvös Loránd University, Hungary)
At most $4.47^n$ stable matchings

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.

February 25, 2021 19.00 MSK (UTC +3)

Alexander Kolpakov (University of Neuchâtel, Switzerland)
Space vectors forming rational angles

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.

February 11, 2021 19.00 MSK (UTC +3)

Misha Rudnev (University of Bristol, UK)
Erdös distance problem in positive characteristics

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.

December 17 19.00 MSK (UTC +3)

Sergey Avvakumov (University of Copenhagen, Denmark)
A subexponential size ${\mathbb R}P^n$

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.

December 10 19.00 MSK (UTC +3)

Xavier Pérez-Giménez (University of Nebraska-Lincoln)
The chromatic number of a random lift of $K_d$

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 $d\ge 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.)

December 3 19.00 MSK (UTC +3)

No talk
On December 2 - 4 we invite everyone to come to the online conference "Combinatorics and Geometry Days III"

November 19 19.00 MSK (UTC +3)

Noga Alon (Princeton and Tel Aviv)
Fair partitions: questions, results and algorithms

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.

November 12 19.00 MSK (UTC +3)

Andrei Vesnin (Tomsk State University)
Around right-angled hyperbolic polytopes

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.
November 5 19.00 MSK (UTC +3)

Wojciech Samotij (Tel Aviv University)
A sharp threshold for Ramsey's theorem

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.

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.

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 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)

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

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

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

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