Schedule

Schedule

See the schedule for each day of the conference below.

Materials

The videos of the talks are available on the labs' YouTube channel and you may also find the links on this page in the schedule below.

Sept 23Sept 24Sept 25
11.50 - 12.00 MSK (UTC +3)
Welcome
Section 1
12.00 - 12.55 MSK (UTC +3)
Alexey Pokrovskiy University College London
Rota's Basis Conjecture holds asymptotically
Video Slides
Rota's Basis Conjecture is a well known problem, that states that for any collection of $n$ bases in a rank $n$ matroid, it is possible to decompose all the elements into $n$ disjoint rainbow bases. Here an asymptotic version of this is will be discussed - that it is possible to find $n − o(n)$ disjoint rainbow independent sets of size $n − o(n)$.
13.00 - 13.55 MSK (UTC +3)
Brendan McKay Australian National University
Some remarks on the method of switchings
Video Slides
The method of switchings has become a standard tool for combinatorial enumeration and probability problems. We will discuss some old and new applications and techniques. First, we discuss how switchings make a very general tool for bounding upper tails of distributions. Second, we illustrate how switchings can be used to study subgraphs of random graphs. Finally, we enumerate linear hypergraphs with a given number of edges.
14.00 - 14.25 MSK (UTC +3)
Nicholas Wormald Monash University
Fast uniform generation of regular graphs and contingency tables
joint work with Andrii Arman and Jane Gao
Video Slides
We present a new technique for use in switching-based random generation of graphs with given degrees. For graphs with m edges and maximum degree $D=O(m^4)$, the "best" existing uniform sampler, given by McKay and Wormald in 1990, runs in time $O(m^2D^2)$. Our new one runs in time $O(m)$, which is effectively optimal. For $d$-regular graphs with $d =o(\sqrt n)$, the best existing ones run in time $O(nd^3)$. This is now improved to $O(nd+d^4)$. Similar results are obtained for generating random contingency tables with given marginals (equivalently, bipartite multigraphs with given degree sequence) in the sparse case.
14.30 - 16.00 MSK (UTC +3)
Break
Section 2
16.00 - 16.55 MSK (UTC +3)
Benjamin Sudakov ETH, Zurich
Large independent sets from local considerations
joint work with Matija Bucic
Video Slides
How well can global properties of a graph be inferred from observations that are purely local? This general question gives rise to numerous interesting problems. One such very natural question was raised independently by Erdos-Hajnal and Linial-Rabinovich in the early 90's. How large must the independence number $\alpha(G)$ of a graph $G$ be whose every $m$ vertices contain an independent set of size $r$? In this talk we discuss new methods to attack this problem which improve many previous results.
17.00 - 17.55 MSK (UTC +3)
Pawel Pralat Ryerson University
Localization Game for Random Graphs
Video Slides
We consider the localization game played on graphs in which a cop tries to determine the exact location of an invisible robber by exploiting distance probes. The corresponding graph parameter is called the localization number. The localization number is related to the metric dimension of a graph, in a way that is analogous to how the cop number is related to the domination number. Indeed, the metric dimension of a graph is the minimum number of probes needed in the localization game so that the cop can win in one round. We investigate both graph parameters for binomial random graphs.
18.00 - 19.00 MSK (UTC +3)
Break
Section 3
19.00 - 19.55 MSK (UTC +3)
Jane Gao University of Waterloo
Random graphs with specified degree sequences
Video Slides
Random graphs with specified degree sequences are popular random graph models not yet well understood, especially when the degree sequences are not "nice". Most problems in random graph theory eventually boil down to estimating subgraph probabilities. We will discuss the configuration model and the switching method that are tools commonly used to study such random graphs. Then we will discuss some recent results on subgraph probabilities and distributions, the chromatic number and the connectivity. Finally we discuss the relation between these random graphs and the well-known Erdős-Renyi graphs, and show how well the former can be approximated by the latter.
20.00 - 20.55 MSK (UTC +3)
David Gamarnik MIT Sloan School of Management
Low-Degree Hardness of Random Optimization Problems
joint work with Aukosh Jagannath and Alex Wein
Video Slides
We consider the problem of finding nearly optimal solutions of optimization problems with random objective functions. Two concrete problems we consider are (a) optimizing the Hamiltonian of a spherical or Ising p-spin glass model (to be introduced in the talk), and (b) finding a large independent set in a sparse Erdos-Renyi graph. We consider the family of algorithms based on low-degree polynomials of the input. This is a general framework that captures methods such as approximate message passing and local algorithms on sparse graphs, among others. We show this class of algorithms cannot produce nearly optimal solutions with high probability. Our proof uses two ingredients. On the one hand both models exhibit the Overlap Gap Property (OGP) of near-optimal solutions. Specifically, for both models, every two solutions close to optimality are either close or far from each other. The second proof ingredient is the stability of the algorithms based on low-degree polynomials: a small perturbation of the input induces a small perturbation of the output. By an interpolation argument, such a stable algorithm cannot overcome the OGP barrier, thus leading to the inapproximability. The stability property is established using concepts from Gaussian and Boolean Fourier analysis, including noise sensitivity, hypercontractivity, and total influence.
September 24
Section 1
12.00 - 12.55 MSK (UTC +3)
Michael Krivelevich Tel Aviv University
Color-biased Hamilton cycles in random graphs
joint work with Lior Gishboliner and Peleg Michaeli
Video Slides
We show that a random graph $G(n,p)$ with the edge probability $p(n)$ above the Hamiltonicity threshold is typically such that for any $r$-coloring of its edges, for a fixed $r\geq2$, there is a Hamilton cycle with at least $(2/(r+1)-o(1))n$ edges of the same color. This estimate is asymptotically optimal.
13.00 - 13.25 MSK (UTC +3)
Lior Gishboliner ETH Zürich
Very fast construction of bounded-degree spanning graphs via the semi-random graph process
joint work with Omri Ben-Eliezer, Danny Hefetz and Michael Krivelevich
Video Slides

Semi-random processes involve an adaptive decision-maker, whose goal is to achieve some predetermined objective in an online randomized environment. In this paper, we consider a recently proposed semi-random graph process, defined as follows: we start with an empty graph on $n$ vertices, and in each round, the decision-maker, called Builder, receives a uniformly random vertex $v$, and must immediately (in an online manner) choose another vertex $u$, adding the edge $\{u,v\}$ to the graph. Builder's end goal is to make the constructed graph satisfy some predetermined monotone graph property. There are also natural offline and non-adaptive variants of this setting.

It was asked by $N$. Alon whether for every bounded-degree (spanning) graph $H$, Builder can construct a copy of $H$ with high probability in $O(n)$ rounds. We answer this question positively in a strong sense, showing that any graph with maximum degree $\Delta$ can be constructed with high probability in $(3\Delta/2+o(\Delta))n$ rounds, where the $o(\Delta)$ term tends to zero as $\Delta$ tends to infinity. This is tight (even for the offline case) up to a multiplicative factor of $3+o_{\Delta}(1)$. Furthermore, for the special case where $H$ is a forest of maximum degree $\Delta$, we show that $H$ can be constructed with high probability in $O(\log\Delta)n$ rounds. This is tight up to a multiplicative constant, even for the offline setting. Finally, we show a separation between adaptive and non-adaptive strategies, proving a lower bound of $\Omega(n\sqrt{\log n})$ on the number of rounds necessary to eliminate all isolated vertices w.h.p. using a non-adaptive strategy. This bound is tight, and in fact there are non-adaptive strategies for constructing a Hamilton cycle or a $K_r$-factor, which are successful w.h.p. within $O(n\sqrt{\log n})$ rounds.

13.30 - 13.55 MSK (UTC +3)
Sergei Kiselev MIPT
Rainbow matchings in $k$-partite hypergraphs
joint work with Andrey Kupavskii
Video Slides

Let $[n]:=\{1,\ldots,n\}$. The following conjecture was made by Aharoni and Howard [1]:

Conjecture. Let $n\ge s$ and $k$ be positive integers. If $\mathcal F_1,\ldots,\mathcal F_s\subset [n]^k$ satisfy $\min_{i}|\mathcal F_i|>(s-1)n^{k-1}$ then there exist $F_1\in\mathcal F_1,\ldots, F_s\in \mathcal F_s,$ such that $F_i\cap F_j = \emptyset$ for any $1\le i < j\le s$.

In their paper, Aharoni and Howard proved this conjecture for $k=2,3$. Then, Lu and Yu [3] proved it for $n>3(s-1)(k-1).$

Our main result is the proof of the conjecture for all $s>s_0.$ The proof relies on the idea that intersection of any family with a random matching is highly concentrated around its expectation. This idea was introduced by the second author in the paper [2] in the context of the Erdős Matching Conjecture.

[1] R. Aharoni and D. Howard, A Rainbow $r$-Partite Version of the Erdős—Ko—Rado Theorem, Comb. Probab. Comput. 26 (2017), N3, 321—337.

[2] P. Frankl, A. Kupavskii, The Erdős os Matching Conjecture and Concentration Inequalities, arXiv:1806.08855.

[3] H. Lu and X. Yu, On rainbow matchings for hypergraphs, SIAM J. Disrete Math. 32 (2018), N1, 382—393.

14.00 - 16.00 MSK (UTC +3)
Break
Section 2
16.00 - 16.55 MSK (UTC +3)
Mihyun Kang Graz University of Technology
Topological aspects of random graphs
Video Slides
In this talk we will discuss various topological aspects of random graphs. How does the genus of a uniform random graph change as the number of edges increases? How does a topological constraint (such as imposing an upper bound on the genus) influence the structure of a random graph (such as the order of the largest component, the length of the shortest and longest cycles)?
17.00 - 17.25 MSK (UTC +3)
Will Perkins University of Illinois at Chicago
Finite-size scaling for the random cluster model on random graphs
joint work with Tyler Helmuth and Matthew Jenssen
Video Slides
The random cluster model is a probability measure on edge sets of a graph given by exponentially tilting edge percolation by the number of connected components an edge set induces. It generalizes the ferromagnetic Potts model, and like the Potts model it exhibits a phase transition as the temperature changes on many classes of graphs. Here we study the large q behavior of the random cluster model on random regular graphs and give detailed information about the phase transition, including the distribution of the log partition function, correlation decay, and local weak convergence. Our technique involves approximating the model by a mixture of abstract polymer models with convergent cluster expansions.
17.30 - 17.55 MSK (UTC +3)
Nikolaos Fountoulakis University of Birmingham
On the spectral gap and the expansion of random simplicial complexes
joint work with Michał Przykucki
Video Slides

In this talk, we will discuss the expansion properties and the spectrum of the combinatorial Laplace operator of a d-dimensional Linial-Meshulam random simplicial complex, above the cohomological connectivity threshold. The focus of our discussion will be the spectral gap of the Laplace operator and the Cheeger constant.

Furthermore, we will discuss a notion of a random walk on such a complex, which generalises the standard random walk on a graph, and consider its mixing time.

18.00 - 19.00 MSK (UTC +3)
Break
Section 3
19.00 - 19.55 MSK (UTC +3)
Lutz Warnke Georgia Institute of Technology
Prague Dimension of Random Graphs
joint work with He Guo and Kalen Patton
Video Slides

Various notions of dimension are important in many area of mathematics, and for graphs the Prague dimension was introduced in the late 1970s Nesetril, Pultr and Rodl.

We show that the Prague dimension of the binomial random graph $G(n,p)$ is typically of order $n/\log n$ for constant edge-probabilities $p$; this proves a conjecture of Furedi and Kantor.

One key ingredient of our proof is a randomized greedy edge-coloring algorithm, that allows us to bound the chromatic index of random subhypergraphs with large edge-uniformities.

20.00 - 20.55 MSK (UTC +3)
Matthew Kwan Stanford University
Perfect matchings in random hypergraphs
joint work with Asaf Ferber
Video Slides

For positive integers $d < k$ and $n$ divisible by $k$, let $m_{d}(k,n)$ be the minimum $d$-degree ensuring the existence of a perfect matching in a $k$-uniform hypergraph. In the graph case (where $k=2$), a classical theorem of Dirac says that $m_{1}(2,n)=\lceil n/2\rceil$. However, in general, our understanding of the values of $m_{d}(k,n)$ is still very limited, and it is an active topic of research to determine or approximate these values. In the first part of this talk, we discuss a new "transference" theorem for Dirac-type results relative to random hypergraphs. Specifically, we prove that a random $k$-uniform hypergraph $G$ with $n$ vertices and "not too small" edge probability $p$ typically has the property that every spanning subgraph with minimum $d$-degree at least $(1+\varepsilon)m_{d}(k,n)p$ has a perfect matching. One interesting aspect of our proof is a "non-constructive" application of the absorbing method, which allows us to prove a bound in terms of $m_{d}(k,n)$ without actually knowing its value.

The ideas in our work are quite powerful and can be applied to other problems: in the second part of this talk we highlight a recent application of these ideas to random designs, proving that a random Steiner triple system typically admits a decomposition of almost all its triples into perfect matchings (that is to say, it is almost resolvable).

September 25
Section 1
12.00 - 12.55 MSK (UTC +3)
Persi Diaconis Stanford University
A course on probabilistic combinatorics
Video Slides 1 Slides 2
This past April-June (2020) I gave a graduate course on probabilistic combinatorics at Stanford's departments of mathematics and statistics. This covered the usual topics: Let $X$ be a finite set, pick $x$ in $X$ uniformly, 'what does it look like?' With $X$ permutations, graphs, partitions, set partitions, matrices over a finite field. It also covered 'who cares?' That is, applications in statistics, computer science and physics/chemistry. Two features were lectures on 'from algorithm to theorem' and 'graph limit theory and its extensions'. The first emphasizes the place and usefulness of algorithms to actually pick $x$ uniformly (for example, there are many different ways to sample permutations, how does one efficiently sample partitions or set partitions? say when $n=10^6$?) Each such algorithm has an associated set of limit theorems that it 'makes transparent'. The second topic featured the work of Lovasz and Razborov and their coworkers. I will review the topics (stopping to be specific) and the course projects, some of which are turning into publishable papers.
13.00 - 13.25 MSK (UTC +3)
Alexander Semenov MIPT
Probability thresholds estimates for coloring properties of random hypergraphs
joint work with Dmitry Shabanov
Video Slides

Recall that for an integer $j$, a $j$-independent set in a hypergraph $H=(V,E)$ is a subset $W\subset V$ such that for every edge $e\in E: |e\cap W| \leqslant j$. A $j$-proper coloring of $H=(V,E)$ is a partition of the vertex set $V$ of $H$ into disjoint union of $j$-independent sets, so called colors. The $j$-chromatic number $\chi_j(H)$ of $H$ is the minimal number of colors needed for a $j$-proper coloring of $H$.

We will talk about our latest results on colorings of the k-uniform random hypergraph $H(n,k,p)$. We are interested in asymptotic properties of $H(n,k,p)$ to have its $j$-chromatic number equal to some fixed number $r$. By asymptotic properties of $H(n,k,p)$ we consider $n$ as tending to infinity, while $k$ and $r$ are kept constant.

It can be shown that the previously mentioned property of random hypergraph has a sharp threshold. For the classic case of $(k-1)$-chromatic number, upper and lower bounds for that threshold were investigated by different researchers. It should be also mentioned that the gap between these bounds in terms of the parameter $c=p{n\choose k}/n$ has a bounded order $O_k(1)$.

We are going to present the results from our last series of works where we found very tight bounds for the case of arbitrary $r$ and $1 < k-j=o(k^{1/4})$.

13.30 - 13.55 MSK (UTC +3)
Jakub Kozik Jagiellonian University
Bi-uniform Property B
Video Slides

How many edges do we need in order to construct a $k$-uniform hypergraph which is not two-colorable? This number, denoted by $m(k)$, has been intensively studied since its introduction by Erd\H{o}s and Hajnal in 1961. As a result, the lower bounds have been improved a number of times and nowadays we know that $m(k)=\Omega(\sqrt{k/\log(k)}\;2^k)$ (Radhakrishnan and Srinivasan 2000). The story of the upper bounds is much shorter. Bound $m(k)= O(k^2 \;2^k)$, obtained by Erdős in 1964, has not been improved since.

We are going to discuss what insights can be gained from considering analogous problem for non-uniform hypergraphs. We focus on an interesting class of bi-uniform hypergraphs, i.e. hypergraphs in which there are only two allowed sizes of edges. On the other hand, having only two sizes of edges eliminates a lot of technical difficulties.

14.00 - 16.00 MSK (UTC +3)
Break
Section 2
16.00 - 16.25 MSK (UTC +3)
Peleg Michaeli Tel-Aviv University
Greedy maximal independent sets via local limits
joint work with Michael Krivelevich, Tamás Mészáros and Clara Shikhelman
Video Slides

The random greedy algorithm for finding a maximal independent set in a graph has been studied extensively in various settings in combinatorics, probability, computer science — and even in chemistry. The algorithm builds a maximal independent set by inspecting the vertices of the graph one at a time according to a random order, adding the current vertex to the independent set if it is not connected to any previously added vertex by an edge.

In this talk, I will present a natural and general framework for calculating the asymptotics of the proportion of the yielded independent set for sequences of (possibly random) graphs, involving a useful notion of local convergence. We use this framework both to give short and simple proofs for results on previously studied families of graphs, such as paths and binomial random graphs, and to give new results for other models such as random trees.

16.30 - 16.55 MSK (UTC +3)
Felix Joos Heidelberg University
Dirac-type results for hypergraph decompositions into cycles
Video Slides
I will discuss recent joint work with Marcus Kühn and Bjarne Schülke on decompositions of hypergraphs into cycles. One of the results answers a question of Glock, Kühn and Osthus and another one is an extension of the well-known result due to Rödl and Rucinski on the minimum degree threshold for Hamilton cycles in k-uniform hypergraphs.
17.00 - 17.25 MSK (UTC +3)
Bhargav Narayanan Rutgers University
The threshold of the square of the Hamilton cycle
joint work with J. Kahn and J. Park
Video Slides
We show that the threshold for the appearance of the square of the Hamilton cycle in $G_{n,p}$ is $p = 1/\sqrt{n}$
17.30 - 17.55 MSK (UTC +3)
József Balogh University of Illinois at Urbana-Champaign
Extensions of Mantel’s Theorem
Video Slides

Mantel’s theorem is a basic classical theorem of extremal graph theory. There are many different extensions and generalizations investigated and many open questions remained.

I will talk about four recent results, including `stability’ and `supersaturation’ properties.

The results are partly joined with Clemen, Katona, Lavrov, Lidicky, Linz, Pfender and Tuza.

18.00 - 19.00 MSK (UTC +3)
Break
Section 3
19.00 - 19.55 MSK (UTC +3)
Allan Sly Princeton University
Local functions for the Ising model on the tree
joint work with Danny Nam and Lingfu Zhang
Video Slides
This talk will look at the question of what processes can or cannot be constructed using local randomness. Work of Gamarnik and Sudan and later Rahman and Virag showed that local algorithms on random $d$-regular graphs can only construct independent sets of size approximately half the maximal size when $d$ is large. Like the optimization problem, a closely related question arising in ergodic theory asks can a particular distribution such as a uniformly random colouring on the tree be constructed as a factor of IID, a type of local functions. I'll survey results in this area and describe new work constructing a factor of IID for the Ising model on the tree in its intermediate regime.
20.00 - 20.55 MSK (UTC +3)
Xavier Pérez-Giménez University of Nebraska-Lincoln
The chromatic number of a random lift of $K_d$
joint work with JD Nir
Video Slides
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\v sek (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$.