Past webinars
Quasirandom graphs, permutations and Latin squares
Abstract: A combinatorial structure is said to be quasirandom if it resembles a random structure in a certain robust sense. The notion of quasirandom graphs, developed in the work of Rödl, Thomason, Chung, Graham and Wilson in 1980s, is particularly robust as several different properties of truly random graphs, e.g., subgraph density, edge distribution and spectral properties, are satisfied by a large graph if and only if one of them is. A closely related notion is the notion of common graphs, which are graphs whose number of monochromatic copies is minimized by the (quasi)random coloring of a host complete graph.
We will discuss quasirandom properties of permutations and Latin squares, and present several recent results obtained using analytic tools of the theory of combinatorial limits. We will also present some recent results on common and locally common graphs, in particular, we show that there exists common connected graphs with arbitrary large chromatic number, whose existence was an open problem for more than 20 years.
The talk is based on results obtained with different groups of collaborators, including Timothy F. N. Chan, Jacob W. Cooper, Robert Hancock, Matjaž Krnc, Ander Lamaison, Samuel Mohr, Jonathan A. Noel, Sergey Norin, Yanitsa Pehova, Oleg Pikhurko, Maryam Sharifzadeh, Jan Volec and Fan Wei.
LINK TO THE VIDEO (youtube), LINK TO THE VIDEO (bilibili)
The n-queens problem
Abstract: How many ways are there to place n queens on an n by n chessboard so that no two can attack one another? What if the chessboard is embedded on the torus? Let Q(n) be the number of ways on the standard chessboard and T(n) the number on the toroidal board. The toroidal problem was first studied in 1918 by Pólya who showed that T(n)>0 if and only if n is not divisible by 2 or 3. Much more recently Luria showed that T(n) is at most ((1+o(1))n/e3)n and conjectured equality when n is not divisible by 2 or 3. We prove this conjecture, prior to which no non-trivial lower bounds were known to hold for all (sufficiently large) n not divisible by 2 or 3. We also show that Q(n) is at least ((1+o(1))n/e3)n for all natural numbers n which was independently proved by Luria and Simkin and, combined with our toroidal result, completely settles a conjecture of Rivin, Vardi and Zimmerman regarding both Q(n) and T(n).
In this talk we'll discuss our methods used to prove these results. A crucial element of this is translating the problem to one of counting matchings in a 4-partite 4-uniform hypergraph. Our strategy combines a random greedy algorithm to count `almost' configurations with a complex absorbing strategy that uses ideas from the methods of randomised algebraic construction and iterative absorption.
This is joint work with Peter Keevash.
LINK TO VIDEO (youtube), LINK TO VIDEO (bilibili)
Local convergence of random planar graphs
Abstract: The study of random combinatorial structures and their limits is a growing field at the interface of combinatorics, probability theory, and mathematical physics. Planar graphs are a prominent example of such structures, yet important problems concerning their asymptotic shape remain open. This talk highlights open conjectures and reviews recent results, in particular the discovery of a Uniform Infinite Planar Graph (UIPG) as their quenched local limit
LINK TO THE VIDEO (youtube), LINK TO THEVIDEO (bilibili)
Maximum number of almost similar triangles in the plane
Abstract: A triangle T' is ε-similar to another triangle T if their angles pairwise differ by at most ε. Given a triangle T, ε>0 and n ∈ ℕ, Bárány and Füredi asked to determine the maximum number of triangles h(n,T,ε) being ε-similar to T in a planar point set of size n. We show that for almost all triangles T there exists ε=ε(T)>0 such that h(n,T,ε)=(1+o(1))n^3/24. Exploring connections to hypergraph Turán problems, we use flag algebras and stability techniques for the proof. This is joint work with József Balogh and Felix Christian Clemen.
LINK TO THE VIDEO (youtube)
November 15, 2021: Rajko Nenadov (Google):
A new proof of the KŁR conjecture
Abstract: We give a new, short and intuitive proof of the celebrated KŁR conjecture. Slightly rephrased, the conjecture states that if we condition on uniform edge distribution, the archetypal property of random graphs, the probability that the Erdős–Rényi random graph G(n,m) does not contain a copy of a fixed graph H becomes superexponentially small in m, for sufficiently large m > m(n, H). As its most prominent application, this conjecture implies that with high probability all subgraphs of the binomial random graph with appropriate parameters satisfy an embedding lemma which complements the sparse regularity lemma. The proof proceeds by induction and, in some way, can be considered a `deterministic' analogue of the multiple-exposure technique from random graph theory.
LINK TO THE VIDEO (youtube), LINK TO THE VIDEO (bilibili)
Hypergraphs with minimum positive uniform Turán density
Abstract: Reiher, Rödl and Schacht showed that the uniform Turán density of every 3-uniform hypergraph is either 0 or at least 1/27, and asked whether there exist 3-uniform hypergraphs with uniform Turán density equal or arbitrarily close to 1/27. We construct 3-uniform hypergraphs with uniform Turán density equal to 1/27. This is based on joint work with Frederik Garbe and Daniel Král’.
LINK TO THE VIDEO (youtube), LINK TO THE VIDEO (bilibili)
Uncommon systems of equations
Abstract: A system of linear equations L over F_q is common if the number of monochromatic solutions to L in any two-colouring of F_q^n is asymptotically at least the expected number of monochromatic solutions in a random two-colouring of F_q^n. Motivated by existing results for specific systems (such as Schur triples and arithmetic progressions), as well as extensive research on common and Sidorenko graphs, the systematic study of common systems of linear equations was recently initiated by Saad and Wolf. Building on earlier work of of Cameron, Cilleruelo and Serra, as well as Saad and Wolf, common linear equations have been fully characterised by Fox, Pham and Zhao.
In this talk I will discuss some recent progress towards a characterisation of common systems of two or more equations. In particular we prove that any system containing an arithmetic progression of length four is uncommon, confirming a conjecture of Saad and Wolf. This follows from a more general result which allows us to deduce the uncommonness of a general system from certain properties of one- or two-equation subsystems.
LINK TO THE VIDEO (youtube), LINK TO THE VIDEO (bilibili)
Tight bounds for powers of Hamilton cycles in tournaments
Abstract: A basic result in graph theory says that any n-vertex tournament with in- and out-degrees at least n/4 contains a Hamilton cycle, and this is essentially tight. In 1990, Bollobás and Häggkvist significantly extended this by showing that for any fixed k and ε >0, and sufficiently large n, all tournaments with degrees at least n/4+εn contain the k-th power of a Hamilton cycle. Given this, it is natural to ask for a more accurate error term in the degree condition. We show that if the degrees are at least n/4+cn^(1−1/⌈k/2⌉) for some constant c=c(k), then the tournament contains the k-th power of a Hamilton cycle. In particular, in order to guarantee the square of a Hamilton cycle, one only requires a constant additive term. We also present a construction which, modulo a well-known conjecture on Turán numbers for complete bipartite graphs, shows that the error term must be of order at least n^(1−1/⌈(k−1)/2⌉), which matches our upper bound for all even k. For odd k, we believe that the lower bound can be improved and we show that for k=3, there exist tournaments with degrees n/4+Ω(n^(1/5)) and no cube of a Hamilton cycle. Additionally we also show that the Bollobás-Häggkvist theorem already holds for n=ε^(−Θ(k)), which is best possible. This is joint work with Nemanja Draganic and Benny Sudakov.
LINK TO THE VIDEO (youtube), LINK TO THE VIDEO (bilibili)
Hamilton cycles above expectation in r-graphs and quasi-random r-graphs
Abstract: Let H_r(n,p) denote the maximum number of (tight) Hamilton cycles in an n-vertex r-graph with density p \in (0,1). The expected number of Hamilton cycles in the random r-graph G_r(n,p) is clearly E(n,p)=p^n(n-1)!/2 and in the random r-graph G_r(n,m) with m=p\binom{n}{r} it is, in fact, easily shown to be slightly smaller than E(n,p).
For graphs, H_2(n,p) it is proved to be only larger than E(n,p) by a polynomial factor and it is an open problem whether a quasi-random graph with density p can be larger than E(n,p) by a polynomial factor.
For hypergraphs the situation is drastically different. For all r >= 3 it is proved that H_r(n,p) is larger than E(n,p) by an {\em exponential} factor and, moreover, there are quasi-random r-graphs with density p whose number of Hamilton cycles is larger than E(n,p) by an exponential factor.
LINK TO THE VIDEO (youtube), LINK TO THE VIDEO (bilibili), SLIDES
Degree conditions for spanning structures in dense graphs
Abstract: A classic theorem of Dirac (1952) states that a graph in which every vertex is connected to at least half of the other vertices contains a Hamilton cycle. Over the years, this result has been generalised in several ways. Some generalisations weaken the assumptions (by not requiring every vertex to have large minimum degree), and other generalisations strenghten the outcome (by considering spanning structures which are not cycles). We investigate the combination of these two directions, and find cycles and other spanning structures under various degree conditions. Along the way, we recover known results and obtain many new ones. Joint work with Richard Lang.
LINK TO THE VIDEO (youtube), LINK TO THE VIDEO (bilibili)
The feasible region of hypergraphs
Abstract: Many extremal hypergraph problems seek to maximize the number of edges subject to some local constraints. We aim to gain a more detailed understanding of such problems by studying the maximum subject to an additional global constraint, namely the size of the shadow. Put differently, we seek the pairs (x,y) in the unit square such that there are F-free hypergraphs whose shadow density approaches x and edge density approaches y. I will give some general results about the shape of this "feasible region" and also extend and improve some classical Turan-type results for particular choices of F. This is joint work with Xizhi Liu.
LINK TO VIDEO (youtube), LINK TO VIDEO (bilibili)
Talk contributing to the Round the World Relay in Combinatorics
On Erdős' Unit Distances Problem
Abstract: In 1946, Paul Erdős published a paper in the American Mathematical Monthly "On sets of distances of n points". He proposed two problems in discrete geometry. What is the minimum number of distinct distances among n points in the plane, and among n points in the plane how many pairs of points could be at unit distance from each other? The first question was answered almost completely by Larry Guth and Netz Katz in 2010, but the second, on unit distances, resisted all attacks so far. I will talk about the unit distances problems, and related questions.
LINK TO VIDEO (youtube), LINK TO VIDEO (bilibili)
Enumerating independent sets in Abelian Cayley graphs
Abstract: We show that any Cayley graph on an Abelian group of order 2n and degree \tilde{Omega}(log n) has at most 2^{n+1}(1 + o(1)) independent sets. This bound is tight up to the o(1) term whenever the graph is bipartite. The proof is based on the container method and the Plünnecke-Rusza-Petridis inequality from additive combinatorics.
Joint work with Liana Yepremyan.
LINK TO VIDEO (youtube), LINK TO VIDEO (bilibili)
A unified approach to hypergraph stability
We present a method which provides a unified framework for many stability theorems that have been proved in graph and hypergraph theory. Our main result reduces stability for a large class of hypergraph problems to the simpler question of checking that a hypergraph H with large minimum degree that omits the forbidden structures is vertex-extendable. This means that if v is a vertex of H and H-v is a subgraph of the extremal configuration(s), then H is also a subgraph of the extremal configuration(s). In many cases vertex-extendability is quite easy to verify.
Our method always yields an Andrásfai-Erdős-Sós type result, which says if H has large minimum degree, then it must be a subgraph of one of the extremal configurations.
This is joint work with Dhruv Mubayi and Christian Reiher.
LINK TO THE VIDEO (youtube), LINK TO THE VIDEO (bilibili)
Generalized Turán problem for cycles
The generalized Turán problem asks for the largest number of copies of a graph H in an n-vertex graph not containing a graph F as a subgraph. In the talk we will discuss this problem in the case when both H and F are cycles. We will present known bounds and recent developments, including the first exact estimation in the sparse setting.
The talk is based on joint works with Bartłomiej Kielak and Mateusz Górski.
LINK TO THE VIDEO (youtube), SLIDES, LINK TO THE VIDEO (bilibili)
Ramsey properties of string graphs
Abstract: In this talk, I will give an outline of the proof of the following conjecture of Alon, Pach, Pinchasi, Radoicic and Sharir. There exists an absolute constant $c>0$ such that any collection of $n$ curves (or in general arcwise-connected sets) in the plane contains a subset of size $n^c$ in which any two elements intersect, or any two are disjoint. This generalizes many earlier results about the Ramsey properties of intersection graphs of geometric objects. The heart of our proof is a purely graph theoretic lemma, which turned out to be quite useful in other Erdos-Hajnal type results as well, see e.g. the recent proof of the Erdos-Hajnal conjecture for the cycle of length 5 by Chudnovsky, Scott, Seymour and Spirkl. For this talk, no knowledge of geometry is required.
LINK TO THE VIDEO (youtube), LINK TO THE VIDEO (bilibili)
Combinatorial generation via permutation languages
Abstract: In this talk I present a general and versatile algorithmic framework for exhaustively generating a large variety of different combinatorial objects, based on encoding them as permutations, which provides a unified view on many known results and allows us to prove many new ones. This talk gives an overview over three main applications of our framework: (1) the generation of pattern-avoiding permutations; (2) the generation of various classes of rectangulations; (3) the generation of lattice congruences of the weak order on the symmetric group and of graph associahedra.
This talk is based on joint work with Liz Hartung, Hung P. Hoang, and Aaron Williams (SODA 2020), and with Arturo Merino (SoCG 2021) and Jean Cardinal.
LINK TO THE VIDEO (youtube), LINK TO THE VIDEO (bilibili), SLIDES
April 19, 2021: Annie Raymond (University of Massachusetts)
Graph Density Inequalities, Sums of Squares and Tropicalization
Graph Density Inequalities, Sums of Squares and Tropicalization
Abstract: Establishing inequalities among graph densities is a central pursuit in extremal graph theory. One way to certify the nonnegativity of a graph density expression is to write it as a sum of squares or as a rational sum of squares. In this talk, we will explore how one does so and we will then identify simple conditions under which a graph density expression cannot be a sum of squares or a rational sum of squares. Tropicalization will play a key role for the latter, and will turn out to be an interesting object in itself. This is joint work with Greg Blekherman, Mohit Singh, and Rekha Thomas.
LINK TO THE VIDEO (youtube), LINK TO THE VIDEO (bilibili)
April 12, 2021: Stefan Glock (ETH Zurich)
Long induced paths in sparse random graphs
Abstract: The study of induced trees in random graphs was initiated by Erdős and Palka in the 80s. Many interesting questions remain unanswered, especially in the sparse case when the average degree is constant. For instance: what is the length of a longest induced path?
Natural algorithms produce an induced path of length roughly half the conjectured optimal value, which has not been improved in the last 30 years.
We show that one can do better than that, which answers a question of Fernandez de la Vega. Unfortunately, we only get halfway towards the upper bound. We will explain the main ideas and explore possible ways to close the remaining gap.
LINK TO THE VIDEO (YOUTUBE), LINK TO THE VIDEO (BILIBILI), SLIDES
April 5, 2021: Alexander Sidorenko (Rényi Institute of Mathematics)
On the asymptotic behavior of the classical Turán numbers
Abstract: A subset of vertices in a hypergraph H is called independent if it does not contain an edge of H. The independence number 𝛂(H) is the size of the largest independent set. The classical Turán number T(n,𝛂+1,r) is the minimum number of edges in an n-vertex r-uniform hypergraph H with 𝛂(H) ≤ 𝛂. In other words, \binom{n}{r} - T(n,k,r) is the largest number of edges in an n-vertex r-uniform hypergraph that does not contain a complete k-vertex subgraph.
The limit of T(n,k,r) / \binom{n}{r} with n→∞ is known as Turán density t(k,r). Pál Turán in 1941 proved that t(𝛂+1,2) = 1/𝛂. It is widely believed that t(𝛂+1,3) = 4/𝛂^2. I will discuss the asymptotic behavior of t(k,r) in respect to k and r. I will also cover similar topics for the codegree Turán problem.
LINK TO THE VIDEO (YOUTUBE), LINK TO THE VIDEO (BILIBILI)
Cliques and sunflowers under bounded VC-dimension
Abstract: The VC-dimension of a set system is one of the most useful combinatorial parameters that measures its complexity, and, apart from its geometric applications, it has proved to be relevant in many other areas such as statistics, logic, and learning theory. In this talk, I will discuss two well-known combinatorial problems under bounded VC-dimension: estimating multicolor Ramsey numbers and the sunflower problem. This talk is based on joint works with Jacob Fox and Janos Pach.
LINK TO THE VIDEO (youtube), LINK TO THE VIDEO (bilibili)
March 22, 2021: Abhishek Methuku (University of Birmingham):
A proof of the Erdős–Faber–Lovász conjecture
Abstract: The celebrated Erdős–Faber–Lovász conjecture (posed in 1972) states that the chromatic index of any linear hypergraph on n vertices is at most n. In this talk, I will sketch a proof of this conjecture for every large n.
History of the problem: Erdős problems, UCSD.
Joint work with D. Kang, T. Kelly, D.Kuhn and D. Osthus.
LINK TO THE VIDEO (youtube), LINK TO THE VIDEO (bilibili)
Popular differences for matrix patterns
Abstract: We study matrix patterns including those of the form $x,x+M_1d,x+M_2d,x+(M_1+M_2)d$ in abelian groups $G^k$ for integer matrices $M_1,M_2$. If $A\subseteq G^k$ has density $\alpha$, one might expect based on recent conjectures of Ackelsberg, Bergelson, and Best that there is $d\neq 0$ such that
\[\#\{x \in G^k: x, x+M_1d, x+M_2d, x+(M_1+M_2)d \in A\} \ge (\alpha^4-o(1))|G|^k\]
as long as $M_1,M_2,M_1\pm M_2$ define automorphisms of $G^k$. We show this conjecture holds in $G = \mathbb{F}_p^n$ for odd $p$ given an additional spectral condition, but is false without this condition. Explicitly, we show the ``rotated squares'' pattern is false over $\mathbb{F}_5^n$. This is in surprising contrast to the theory of popular differences of one-dimensional patterns.
LINK TO THE VIDEO (youtube), LINK TO THE VIDEO (bilibili)
On the Shape of Large Permutations
Abstract: What do large permutations look like? We can in some cases answer this question with the help of limit structures called "permutons," and a variational principle. Examples show nice apparent behavior and a contrast to the case of graphs and graphons.
Joint work with Rick Kenyon, Dan Kráľ and Charles Radin; later, with Chris Coscia, Sayan Das, Sumit Mukherjee and Martin Tassy.
LINK TO THE VIDEO (youtube), LINK TO THE VIDEO (bilibili)
Towards the sampling Lovász local lemma
Abstract: For a constraint satisfaction problem which satisfies the condition of the Lovász local lemma (LLL), the celebrated algorithm of Moser and Tardos allows one to efficiently find a satisfying assignment. In the past few years, much work has gone into understanding whether one can efficiently sample from approximately the uniform distribution on satisfying assignments, or approximately count the number of satisfying assignments, under LLL-like conditions.
I will discuss recent algorithmic progress on this problem, joint with Huy Tuan Pham (Stanford) and Thuy Duong Vuong (Stanford).
LINK TO THE VIDEO (youtube), LINK TO THE VIDEO (bilibili), SLIDES
Equiangular lines with a fixed angle
Abstract: A configuration of N lines through the origin in d-dimensional Euclidean space is called equiangular if the lines are pairwise separated by the same angle. A natural and long-standing problem in discrete geometry is to determine the maximum size of a configuration of equiangular lines in a given dimension.
We determine, for each fixed angle and in all sufficiently large dimensions, the maximum number of equiangular lines separated by this given angle. Surprisingly, this maximum depends on spectral graph theoretic properties of the fixed angle.
Our proof involves the following novel result that seems to be of independent interest: A bounded degree connected graph has sublinear second eigenvalue multiplicity (that is, the multiplicity of the second-largest eigenvalue of the adjacency matrix of the graph is sublinear in the number of vertices).
Joint work with Zilin Jiang, Yuan Yao, Shengtong Zhang, and Yufei Zhao.
LINK TO THE VIDEO (youtube), LINK TO THE VIDEO (bilibili)
Optimal high dimension geometric construction for Ramsey-Turan theory
Abstract: Combining two classical notions in extremal graph theory, the study of Ramsey-Turan theory seeks to determine, for integers m≤n and p≤q, the number RT_p(n,K_q,m), which is the maximum size of an n-vertex K_q-free graph in which every set of at least m vertices contains a K_p.
Two major open problems in this area from the 80s ask:
(1) whether the asymptotic extremal structure for the general case exhibits certain periodic behaviour, resembling that of the special case when p=2;
(2) to construct analogues of the Bollobás-Erdős graph with densities other than powers of 1/2.
We refute the first conjecture by witnessing asymptotic extremal structures that are drastically different from the p=2 case; and address the second problem by constructing Bollobás-Erdős-type graphs with any rational density up to 1/2 using high dimension complex sphere.
Joint work with Christian Reiher, Maryam Sharifzadeh and Katherine Staden.
LINK TO THE VIDEO (youtube), LINK TO THE VIDEO (bilibili)
Discrepancy of spanning trees
Abstract: Recently there has been some interest in discrepancy-type problems on graphs. Here we study the discrepancy of spanning trees. For a connected graph G and a number of colors r, what is the maximum d = d_r(G) such that in any r-coloring of the edges of G, there is a spanning tree with at least (n-1)/r + d edges of the same color? d_r(G) is called the r-color spanning-tree discrepancy of G, and has been recently studied by Balogh, Csaba, Jing and Pluhar. As our main result, we show that under very mild conditions (for example, if G is 3-connected), d_r(G) is equal, up to a constant factor, to the minimal integer s such that G can be separated into r equal parts V_1,...,V_r by deleting at most s vertices. This strong and perhaps surprising relation between these two parameters allows us to estimate d_r(G) for many graphs of interest. In particular, we reprove and generalize results of Balogh et al., as well as obtain new ones. Some tight asymptotic results for particular graph classes are also obtained.
Joint work with Michael Krivelevich and Peleg Michaeli.
LINK TO THE VIDEO (youtube), LINK TO THE VIDEO (bilibili)
Roots of random polynomials near the unit circle
Abstract: It is a well-known (but perhaps surprising) fact that a polynomial with independent random coefficients has most of its roots very close to the unit circle. Using a probabilistic perspective, we understand the behavior of roots of random polynomials exceptionally close to the unit circle and prove several limit theorems; these results resolve several conjectures of Shepp and Vanderbei. We will also discuss how our techniques provide a heuristic, probabilistic explanation for why random polynomials tend to have most roots near the unit circle. Based on joint work with Julian Sahasrabudhe.
LINK TO THE VIDEO (youtube), LINK TO THE VIDEO (bilibili)
A Topological Turán Problem
Abstract: The classical Turán problem asks: given a graph H, how many edges can an n-vertex graph have while containing no isomorphic copy of H? By viewing (k+1)-uniform hypergraphs as k-dimensional simplicial complexes, we can ask a topological version of this (first posed by Nati Linial): given a k-dimensional simplicial complex S, how many facets can an n-vertex k-dimensional simplicial complex have while containing no homeomorphic copy of S? Until recently, little was known for k > 2. In this talk, we give an answer for general k, by way of dependent random choice and the combinatorial notion of a trace-bounded hypergraph. Joint work with Jason Long and Bhargav Narayanan.
LINK TO THE VIDEO (youtube), LINK TO THE VIDEO (bilibili)
Flip processes on finite graphs and dynamical systems they induce on graphons
Abstract: We introduce a class of random graph processes, which we call flip processes. Each such process is given by a rule which is just a function R:Hk→Hk from all labelled k-vertex graphs into itself (k is fixed). Now, the process starts with a given n-vertex graph G0. In each step, the graph Gi is obtained by sampling k random vertices v1,…,vk of Gi-1 and replacing the induced graph Gi-1[v1,…,vk] by R(Gi-1[v1,…,vk]). This class contains several previously studied processes including the Erdos-Renyi random graph process and the random triangle removal.
Given a flip processes with a rule R we construct time-indexed trajectories Φ:W×[0,∞)→W in the space of graphons. We prove that with high probability, starting with a large finite graph G0 which is close to a graphon U, the flip process will follow the trajectory Φ(U,t), where t∈[0,∞), with appropriate rescaling of the time.
These graphon trajectories are then studied from the perspective of dynamical systems. We prove that two trajectories cannot form a confluence, give an example of a process with an oscillatory trajectory, and study stability and instability of fixed points.
Joint work with Frederik Garbe, Matas Sileikis and Fiona Skerman.
LINK TO THE VIDEO (youtube), LINK TO THE VIDEO (bilibili)
Splitting necklaces
Abstract: It is known that one can cut any opened necklace with beads of n types in at most (k-1)n points and partition the resulting intervals into k collections, each containing the same number of beads of each type (up to 1). This number of cuts is optimal. I will discuss some recent advances in the study of this problem focusing on its algorithmic aspects and on the case of random necklaces.
Based on joint work with Andrei Graur and on joint work in progress with Janos Pach and Gabor Tardos.
LINK TO VIDEO (youtube), LINK TO VIDEO (bilibili), SLIDES
Geodesic geometry on graphs
Abstract: We investigate a graph theoretic analogue of geodesic geometry. In a graph G=(V,E) we consider a system of paths P={Pu,v|u,v∈V} where Pu,v connects vertices u and v. This system is consistent in that if vertices y,z are in Pu,v, then the sub-path of Pu,v between them coincides with Py,z. A map w:E→(0,∞) is said to induce P if for every u,v∈V the path Pu,v is w-geodesic. We say that G is metrizable if every consistent path system is induced by some such w. As we show, metrizable graphs are very rare, whereas there exist infinitely many 2-connected metrizable graphs.
Joint work with my student Daniel Cizma.
LINK TO VIDEO (youtube), LINK TO VIDEO (bilibili)
Exponential improvements in Ramsey theory
Abstract: The Ramsey number r(t) is the smallest natural number n such that every two-colouring of the edges of K_n contains a monochromatic copy of K_t. It has been known for over seventy years that the Ramsey number lies between \sqrt{2}^t and 4^t, but improving either bound by an exponential factor remains a difficult open problem. In this lecture, we discuss several related problems where such an exponential improvement has been achieved.
This talk reflects joint work with many co-authors, including Asaf Ferber, Jacob Fox, Andrey Grinshpun, Xiaoyu He and Yuval Wigderson.
LINK TO VIDEO (youtube), LINK TO VIDEO (bilibili)
Avoiding arithmetic progressions or right angles
Abstract: In this talk we discuss some bounds about sets avoiding certain arithmetic or geometric configurations in F_p^n (or more generally, in Z_m^n). In particular, we will consider the case of 6-term arithmetic progressions in Z_6^n, and sets avoiding right angles in F_p^n. Our methods can also be used to bound the maximum possible size of a binary code where no two codewords have Hamming distance divisible by a fixed prime p.
Joint work with Palincza and with Bursics, Matolcsi and Schrettner.
LINK TO THE VIDEO (youtube), LINK TO THE VIDEO (bilibili)
Three problems on 3-chromatic intersecting hypergraphs
Abstract: The study of non-2-colorable hypergraphs has a long history going back almost 60 years to the famous problem of Erdos and Hajnal, who asked for the minimum number of edges in such a k-uniform hypergraph. In 1973 Erdos and Lovasz further asked what happens if in addition to non-2-colorability one requires the hypergraph to be intersecting. Their seminal paper, which introduced the local lemma, contains three intriguing problems on the properties of 3-chromatic intersecting hypergraphs. Despite these problems being reiterated several times over the years by Erdos and other researchers, remarkably they withstood any progress up until now. In this talk, we prove that in any 3-chromatic intersecting k-uniform hypergraph there are at least k^(1/2-o(1)) different intersection sizes among pairs of edges. This proves a conjecture of Erdos and Lovasz in a strong form and substantially improves their previously best bound of at least 3 different intersection sizes.
Joint work with M. Bucic and S. Glock
LINK TO THE VIDEO (youtube), LINK TO THE VIDEO (bilibili)
Large deviation principle for graphons
Abstract: In this talk we discuss the large deviation principle (LDP) for a sequence of measures on the graphon space which is obtained by sampling from a fixed graphon W. The large deviation theory for the Erdős–Rényi random graph (sampling from a constant graphon) and its applications were developed by Chatterjee and Varadhan. Particularly, the Erdős–Rényi random graph satisfies LDP with the speed 2/n^2.
We show that when sampling from a general graphon one can get LDPs with two interesting speeds, namely, 1/n and 2/n^2. We completely characterize the situation for the speed 1/n. In the case 2/n^2, we describe the LDP when sampling from a step graphon.
Time permitting, we compare our work with a recent result by Borgs, Chayes, Gaudio, Petti and Sen on LDP for block models.
This is a joint work with O.Pikhurko.
LINK TO THE VIDEO (youtube), LINK TO THE VIDEO (bilibili)
Some combinatorial games on rooted multi-type Galton-Watson trees
Abstract: In a rooted multi-type Galton-Watson branching process, the root is assigned a colour from a finite set Sigma of colours according to some probability distribution P, and a vertex of the tree, conditioned on its colour sigma from Sigma, gives birth to offspring according to some probability distribution chi(sigma) on N_0^Sigma. In particular, one may consider Sigma = {red, blue} and the resulting random tree, denoted T, can be viewed as a directed random graph if each edge is attributed a direction from parent to child. I consider the normal, misere and escape games on T, each played between P1 and P2, with P1 being allowed to move the token only along monochromatic directed edges and P2 being allowed to move the token only along non-monochromatic directed edges. I then investigate the probabilities of win, loss and (where pertinent) draw of each player as fixed points of distributional recursions, establish inequalities between win / loss / draw probabilities of the players across different games, seek possible phase transitions in win / loss / draw probabilities as the parameters involved in the offspring distributions are made to vary, study expected durations of the games etc.
LINK TO THE VIDEO (youtube), LINK TO THE VIDEO (bilibili), SLIDES
A remark on the transitive case of the union-closed conjecture
Abstract: We give a short proof that the union-closed conjecture holds in the special case where the union-closed family in question is generated by all translates of a fixed subset of an Abelian group. Joint work with James Aaronson (Oxford) and Imre Leader (Cambridge).
LINK TO THE VIDEO (youtube), LINK TO THE VIDEO (bilibili)
November 2, 2020: Andrey Kupavskii (Moscow Institute of Physics and Technology and CNRS Grenoble)
The extremal number of surfaces
Abstract: In 1973, Brown, Erdős and Sós proved that if H is a 3-uniform hypergraph on n vertices which contains no triangulation of the sphere, then H has at most O(n^{5/2}) edges, and this bound is the best possible up to a constant factor. Resolving a conjecture of Linial, also reiterated by Keevash, Long, Narayanan, and Scott, we show that the same result holds for triangulations of the torus. Furthermore, we extend our result to every closed orientable surface S. Joint work with Alexandr Polyanskii, István Tomon and Dmitriy Zakharov
LINK TO THE VIDEO (youtube), LINK TO THE VIDEO (bilibili)
On local Turán problems
Abstract: Since its formulation, Turán's hypergraph problems have been among the most challenging open problems in extremal combinatorics. One of them is the following: given a 3-uniform hypergraph F on n vertices in which any five vertices span at least one edge, prove that |F|>=(1/4 -o(1))\binom{n}{3}. The construction showing that this bound would be best possible is simply {X \choose 3} \cup {Y \choose 3} where X and Y evenly partition the vertex set. This construction satisfies the following more general (2p+1, p+1)-property: any set of 2p+1 vertices spans a complete sub-hypergraph on p+1 vertices.
In this talk, we will show that, quite surprisingly, for all p>2 the (2p+1,p+1)-property implies the conjectured lower bound. Furthermore, we will prove that for integers r, a >= 2, the minimum edge density of an r-uniform hypergraph satisfying the (ap+1, p+1)-property tends to 1/a^{r-1} when p tends to infinity.
Joint work with Peter Frankl and Vojtěch Rödl.
LINK TO THE VIDEO (youtube), LINK TO THE VIDEO (bilibili), SLIDES
October 19, 2020: Lisa Sauermann (IAS Princeton)
On polynomials that vanish to high order on most of the hypercube
Abstract: Motivated by higher vanishing multiplicity generalizations of Alon's Combinatorial Nullstellensatz and its applications, we study the following problem: for fixed k and n large with respect to k, what is the minimum possible degree of a polynomial P in R[x_1,...,x_n] such that P(0,…,0) is non-zero and such that P has zeroes of multiplicity at least k at all points in {0,1}^n except the origin? For k=1, a classical theorem of Alon and Füredi states that the minimum possible degree of such a polynomial equals n. We solve the problem for all k>1, proving that the answer is n+2k−3. Joint work with Yuval Wigderson.
LINK TO THE VIDEO (youtube), LINK TO THE VIDEO (bilibili)
October 12, 2020: Ferenc Bencs (Alfréd Rényi Institute of Mathematics)
Atoms of the matching measure
Abstract: We prove that the matching measure of an infinite vertex-transitive connected graph has no atoms. Generalizing the results of Salez, we show that for an ergodic non-amenable unimodular random rooted graph with uniformly bounded degrees, the matching measure has only finitely many atoms. Ku and Chen proved the analogue of the Gallai-Edmonds structure theorem for non-zero roots of the matching polynomial for finite graphs. We extend their results for infinite graphs. We also show that the corresponding Gallai-Edmonds decomposition is compatible with the zero temperature monomer-dimer model. Joint work with András Mészáros.
LINK TO THE VIDEO (youtube), LINK TO THE VIDEO (bilibili)
A solution to Erdős and Hajnal's odd cycle problem
Abstract: I will discuss how to construct cycles of many different lengths in graphs, in particular answering the following two problems on odd and even cycles. Erdős and Hajnal asked whether the sum of the reciprocals of the odd cycle lengths in a graph diverges as the chromatic number increases, before Erdős later asked whether there is a constant C such that every graph with average degree at least C contains a cycle whose length is a power of 2.
This is joint work with Hong Liu.
LINK TO THE VIDEO (youtube), LINK TO THE VIDEO (bilibili)
Non-bipartite k-common graphs
How many monochromatic copies of H must appear in a k-edge colouring of a large complete graph? The graph H is said to be "k-common" if the number of monochromatic H is asymptotically minimized by a random colouring. Recent progress on Sidorenko's Conjecture has provided many new examples of bipartite k-common graphs; however, it is not known if such graphs can have high chromatic number. We construct the first examples of non-bipartite k-common graphs for k >= 3, addressing a problem raised by Jagger, Šťovíček and Thomason in 1996. This talk is based on joint work with Daniel Kráľ, Sergey Norin, Jan Volec and Fan Wei.
LINK TO THE VIDEO (youtube), LINK TO THE VIDEO (bilibili)
Weak expansion and strong regularity
In previous work, embedding large graphs into subgraphs of random graphs is generally done vertex by vertex, using the Sparse Regularity Lemma, looking only one step ahead, and maintaining regularity properties throughout using a technical tool called inheritance of regularity. This approach cannot work for very sparse random graphs, even though it is believed that the embedding statements do remain true. We develop an alternative approach, showing that given a partial embedding and looking several steps ahead, the set of extensions has a weak expansion property; leveraging this one can perform vertex by vertex embedding without the need for inheritance of regularity, and as a result the approach works in sparser random graphs. In order to make this approach work, we need to use a strengthened version of the Sparse Regularity Lemma.
I will outline the new approach briefly, and explain how to use it to prove two new results.
(i) For any $\gamma>0$ and integers $r$, $D$ and $\Delta$, there is $c>0$ such that if $p\ge n^{-1/D+\gamma}$ then $\Gamma=G(n,p)$ with high probability has the following property. However $\Gamma$ is $r$-coloured, there is a colour class which contains all $cn$-vertex graphs with degeneracy at most $D$ and maximum degree at most $\Delta$.
(ii) If $p\ge n^{-1+o(1)}$, then the random $k$-uniform hypergraph $\Gamma=G^{(k)}(n,p)$ with high probability has the following property. Every subgraph $G$ of $\Gamma$ with minimum codegree at least $(\frac12+o(1))pn$ contains a tight Hamilton cycle.
Both these results are asymptotically optimal. This is joint work with Julia Böttcher and with Olaf Parczyk and Vincent Pfenninger.
LINK TO THE VIDEO (youtube), LINK TO THE VIDEO (bilibili)
Further progress towards Hadwiger's conjecture
Abstract: In 1943, Hadwiger conjectured that every graph with no K_t minor is (t-1)-colorable for every t\ge 1. In the 1980s, Kostochka and Thomason independently proved that every graph with no K_t minor has average degree O(t\sqrt{\log t}) and hence is O(t\sqrt{\log t})-colorable. Recently, Norin, Song and I showed that every graph with no K_t minor is O(t(\log t)^{\beta})-colorable for every \beta > 1/4, making the first improvement on the order of magnitude of the O(t\sqrt{\log t}) bound. Here we show that every graph with no K_t minor is O(t (\log t)^{\beta})-colorable for every \beta > 0; more specifically, they are O(t (\log \log t)^6)-colorable.
LINK TO THE VIDEO (youtube), LINK TO THE VIDEO (bilibili)
Extremal stationary values for directed random graphs
Abstract: In this talk, we will discuss the minimum positive value of the stationary distribution of a random walk on a directed random graph with given (bounded) degrees. While for undirected graphs the stationary distribution is simply determined by the degrees, the graph geometry plays a major role in the directed case. Understanding typical stationary values is key to determining the mixing time of the walk, as shown by Bordenave, Caputo, and Salez. However, typical results provide no information on the minimum value, which is important for many applications. Recently, Caputo and Quattropani showed that the stationary distribution exhibits logarithmic fluctuations provided that the minimum degree is at least 2. In this talk, we show that dropping the minimum degree condition may yield polynomially smaller stationary values of the form n^{-(1+C+o(1))}, for a constant C determined by the degree distribution. In particular, C is the combination of two factors: (1) the contribution of atypically thin in-neighborhoods, controlled by subcritical branching processes; and (2) the contribution of atypically "light" directed paths, controlled by large deviation rate functions. As a by-product of our proof, we also determine the mean hitting time in random digraphs. This is joint work with Xing Shi Cai.
LINK TO THE VIDEO (youtube), LINK TO THE VIDEO (bilibili)
On Turán exponents of graphs
Abstract: Given a family of graphs F, the Turán number ex(n,F) of F is the maximum number of edges in an n-vertex graph G that does not contain any member of F as a subgraph. In a relatively recent breakthrough, Bukh and Conlon verified a long-standing conjecture in extremal graph theory that was credited to Erdős and Simonovits and re-iterated by other authors by showing that for every rational number r between 1 and 2 there exists a family F of graphs such that ex(n,F)=Theta(n^r).
There is a stronger conjecture that states that for every rational r between 1 and 2 there exists a single bipartite graph F such that ex(n,F)=Theta(n^r). This conjecture is still open. In this talk, we survey recent progress on this stronger conjecture.
LINK TO THE VIDEO (youtube), LINK TO THE VIDEO (bilibili)
Local limit theorems for subgraph counts
Abstract: We introduce a general framework for studying anticoncentration and local limit theorems for random variables, including graph statistics. Our methods involve an interplay between Fourier analysis, decoupling, hypercontractivity of Boolean functions, and transference between ``fixed-size'' and ``independent'' models. We also adapt a notion of "graph factors" due to Janson.
As a consequence, we derive a local central limit theorem for connected subgraph counts in the Erdős-Rényi random graph G(n,p), building on work of Gilmer and Kopparty and of Berkowitz. These results improve an anticoncentration result of Fox, Kwan, and Sauermann and partially answers a question of Fox, Kwan, and Sauermann. We also derive a local limit central limit theorem for induced subgraph counts, as long as p is bounded away from a set of "problematic" densities, partially answering a question of Fox, Kwan, and Sauermann. We then prove these restrictions are necessary by exhibiting a disconnected graph for which anticoncentration for subgraph counts at the optimal scale fails for all constant p, and finding a graph H for which anticoncentration for induced subgraph counts fails in G(n,1/2). These counterexamples resolve anticoncentration conjectures of Fox, Kwan, and Sauermann in the negative.
Finally, we also examine the behavior of counts of k-term arithmetic progressions in subsets of Z/nZ and deduce a local limit theorem wherein the behavior is Gaussian at a global scale but has nontrivial local oscillations (according to a Ramanujan theta function). These results improve on results of and answer questions of the authors and Berkowitz, and answer a question of Fox, Kwan, and Sauermann.
LINK TO THE VIDEO (youtube), LINK TO THE VIDEO (bilibili)
Decompositions of Hypergraphs
Abstract: Several results on approximate decompositions of hypergraphs are presented including decompositions into tight Hamilton cycles under very mild assumptions on the host hypergraphs as well as further results on decompositions of quasirandom hypergraphs into bounded degree hypergraphs.
LINK TO THE VIDEO (youtube), LINK TO THE VIDEO (bilibili)
Convex holes in high-dimensional point sets
Abstract: It is well-known that every large enough set P in an Euclidean space contains k points in convex position. Such k points are called "hole" if their convex hull contains no other point of P. We present a new construction of k-hole-free sets in high-dimensional spaces. Surprisingly, the construction is based on non-trivial low-discrepancy sequences used for numerical integration. Joint work with Ting-Wei Chao and Ron Holzman.
LINK TO THE VIDEO (youtue), LINK TO THE VIDEO (bilibili)
Combinatorics of Circle Squaring
Abstract: Two sets in a metric space are called equidecomposable if one set can be partitioned into finitely many pieces that can be rearranged by isometries to form a partition of the other set. I will discuss how combinatorial ideas and methods helped in various results on "constructive" equidecompositions. In particular, I will present our joint result with Andras Mathe and Jonathan Noel that a disk and a square in the Euclidean plane are equidecomposable with Jordan measurable pieces.
LINK TO THE VIDEO (youtube), LINK TO THE VIDEO (bilibili)
Monochromatic triangle packings in 2-coloured complete graphs
Abstract: We show that every 2-coloured complete graph on n vertices contains n^2/12 + o(n^2) pairwise edge-disjoint monochromatic triangles. This confirms a conjecture of Erdős, and is asymptotically tight. This is joint work with Vytautas Gruslys.
LINK TO THE VIDEO (youtube), LINK TO THE VIDEO (bilibili)
Extension complexity of low-dimensional polytopes
Abstract: Sometimes, it is possible to represent a complicated polytope as a projection of a much simpler polytope. To quantify this phenomenon, the extension complexity of a polytope P is defined to be the minimum number of facets in a (possibly higher-dimensional) polytope from which P can be obtained as a linear projection. In this talk we discuss some extremal and probabilistic questions about this notion. This is a joint work with Lisa Sauermann and Yufei Zhao.
LINK TO THE VIDEO (youtube), LINK TO THE VIDEO (bilibili)
Extensions of Mantel’s Theorem
Abstract: 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 three recent results, including `stability’ and `supersaturation’ properties. The results are partly joined with Clemen, Katona, Lidicky, Linz, Pfender and Tuza.
This seminar was not recorded
A fast distributed algorithm for (Δ + 1)-edge-coloring
Abstract: A celebrated theorem of Vizing says that every graph G of maximum degree Δ is (Δ+1)-edge-colorable. In this talk I will describe a deterministic distributed algorithm in the LOCAL model that finds a (Δ+1)-edge-coloring in the number of rounds that is polynomial in Δ and log(n), where n is the number of vertices of G. This is the first distributed algorithm for (Δ + 1)-edge-coloring with running time better than O(diameter(G)).
LINK TO VIDEO (youtube), LINK TO VIDEO (bilibili)
Non-concentration of the chromatic number
Abstract: There are many impressive results asserting that the chromatic number of a random graph is sharply concentrated. In 1987, Shamir and Spencer showed that for any function p=p(n), the chromatic number of G(n,p) takes one of at most about n^(1/2) consecutive values whp. For sparse random graphs, much sharper concentration is known to hold: Alon and Krivelevich proved two point concentration whenever p < n^(-1/2-epsilon).
However, until recently no non-trivial lower bounds for the concentration were known for any p, even though the question was raised prominently by Erdős in 1992 and Bollobás in 2004.
In this talk, we show that the chromatic number of G(n, 1/2) is not whp contained in any sequence of intervals of length n^(1/2-o(1)), almost matching Shamir and Spencer's upper bound.
Joint work with Oliver Riordan.
LINK TO THE VIDEO (youtube), LINK TO THE VIDEO (bilibili)
Induced subgraphs with prescribed degrees mod q
Abstract: A classical result of Galai asserts that the vertex-set of every graph can be partitioned into two sets such that each induces a graph with all degrees even. Scott studied the (harder) problem of determining for which graphs can we find a partition into arbitrary many parts, each of which induces a graph with all odd degrees.
In this talk we discuss various extensions of this problem to arbitrary residues mod q>2. Among other results, we show that for every q, a typical graph G(n,1/2) can be equipartitioned (up to divisibility conditions) into q+1 sets, each of which spans a graph with a prescribed degree sequence.
Switching to a completely unrelated problem: based on idea of the main key lemma of the above results, we give non-trivial bound (but weaker than known results) on the singularity probability of a random symmetric Bernoulli matrix. The new argument avoids both decoupling and distance from random hyperplanes and it turns this problem into a simple and elegant exercise.
The first part of the talk is based on a joint work with Liam Hardiman (UCI) and Michael Krivelevich (Tel Aviv University).
LINK TO THE VIDEO (youtube), LINK TO THE VIDEO (bilibili)
A proof of the Upper Matching Conjecture for large graphs
Abstract: We show that the `Upper Matching Conjecture' of Friedland, Krop, and Markström and the analogous conjecture of Kahn for independent sets in regular graphs hold for all large enough graphs as a function of the degree. That is, for every d and every large enough n divisible by 2d, a union of n/(2d) copies of the complete d-regular bipartite graph maximises the number of independent sets and matchings of any given size over all d-regular graphs on n vertices. For the proof, we'll discuss two different approaches to these problems, both inspired by statistical physics. This is joint work with Ewan Davies and Will Perkins.
LINK TO THE VIDEO (youtube), LINK TO THE VIDEO (bilibili)
On tripartite common graphs
Abstract: A graph H is common if the number of monochromatic copies of H in a 2-edge-colouring of the complete graph K_N is minimised by the random colouring. Burr and Rosta, extending a famous conjecture by Erdős, conjectured that every graph is common, which was disproved by Thomason and by Sidorenko in late 1980s. Collecting new examples for common graphs had not seen much progress since then, although very recently, a few more graphs are verified to be common by the flag algebra method or the recent progress on Sidorenko's conjecture.
Our contribution here is to give a new class of tripartite common graphs. The first example class is so-called triangle trees, which generalises two theorems by Sidorenko and hence answers a question by Jagger, Šťovíček, and Thomason from 1996. We also prove that, somewhat surprisingly, given any tree T, there exists a triangle tree such that the graph obtained by adding T as a pendant tree is still common. Furthermore, we show that some complete tripartite graphs, e.g., the octahedron graph K_2,2,2, are common and conjecture that every complete tripartite graph is common.
Joint work with Andrzej Grzesik, Bernard Lidický, and Jan Volec.
LINK TO THE VIDEO (youtube), LINK TO THE VIDEO (bilibili)
Planar point sets determine many pairwise crossing segments
Abstract: What is the largest number f(n) such that n points in the plane (no three on a line) always determine f(n) pairwise crossing segments. This natural question was asked by Aronov, Erdős, Goddard, Kleitman, Klugerman, Pach, and Schulman in 1991 and they proved f(n)=Omega(sqrt(n)). The prevailing conjecture was that this bound is far from optimal and f(n) is probably linear in n. Nevertheless, this lower bound was not improved till last year, when we proved with János Pach and Natan Rubin an almost (but not quite) linear lower bound. Our result gives f(n)>n/exp(O(sqrt(log n))). Determining whether f(n) is truly linear is an intriguing open problem.
LINK TO THE VIDEO (youtube), LINK TO THE VIDEO (bilibili)
Counting extensions in random graphs
Abstract: 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, whip, 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 intriguing problems that remain open.
Joint work with Matas Sileikis, see arXiv:1911.03012
LINK TO THE VIDEO (youtube), LINK TO THE VIDEO (bilibili)
The number of maximal independent sets in the Hamming cube
Abstract: Let Q_n be the n-dimensional Hamming cube (hypercube) and N = 2^n . We prove that the number of maximal independent sets in Q_n is asymptotically 2n2^(N/4), as was conjectured by Ilinca and Kahn in connection with a question of Duffus, Frankl and Rödl. The value is a natural lower bound derived from a connection between maximal independent sets and induced matchings. The proof of the upper bound draws on various tools, among them “stability” results for maximal independent set counts and old and new results on isoperimetric behavior in Q_n. This is joint with Jeff Kahn.
LINK TO THE VIDEO (youtube), LINK TO THE VIDEO (bilibili)
Tournament quasirandomness from local counting
Abstract: A well-known theorem of Chung and Graham states that if h>3 then a tournament T is quasirandom if and only if T contains each h-vertex tournament the "correct number" of times as a subtournament. In this talk we investigate the relationship between quasirandomness of T and the count of a single h-vertex tournament H in T. We consider two types of counts, the global one and the local one.
We first observe that if T has the correct global count of H and h>6 then quasirandomness of T is only forced if H is transitive. The next natural question when studying quasirandom objects asks whether possessing the correct local counts of H is enough to force quasirandomness of T. A tournament H is said to be locally forcing if it has this property.
Variants of the local forcing problem have been studied before in both the graph and hypergraph settings. Perhaps the closest analogue of our problem was considered by Simonovits and Sós who looked at whether having "correct counts" of a fixed graph H as an induced subgraph of G implies G must be quasirandom, in an appropriate sense. They proved that this is indeed the case when H is regular and conjectured that it holds for all H (except the path on 3 vertices).
Contrary to the Simonovits-Sós conjecture, in the tournament setting we prove that a constant proportion of all tournaments are not locally forcing. In fact, any locally forcing tournament must itself be strongly quasirandom. On the other hand, unlike the global forcing case, we construct infinite families of non-transitive locally forcing tournaments.
This is joint work with E. Long, A. Shapira and B. Sudakov.
LINK TO THE VIDEO (youtube), LINK TO THE VIDEO (bilibili)
Proof of Ringel's conjecture
Abstract: Ringel conjectured that the edges of the complete graph on 2n+1 vertices can be decomposed into disjoint copies of any n-edge tree T. This talk will be about a recent proof of this conjecture for sufficiently large n. This is joint work with Richard Montgomery and Benny Sudakov.
LINK TO THE VIDEO (youtube), LINK TO THE VIDEO (bilibili)
Five and a half proofs of one theorem
Abstract: The Erdos-Ko-Rado theorem is the cornerstone of the modern field of extremal combinatorics. In this talk we consider one of the variants of this theorem, in the setting of the product measure on the discrete cube, and present (time permitting) several different proofs of it, using a surprisingly eclectic set of tools.
LINK TO THE VIDEO (youtube), LINK TO THE VIDEO (bilibili)
Overlap Gap Property: a Provable Barrier to Fast Optimization in Probabilistic Combinatorial Structures
Abstract: Many combinatorial optimization problems defined on random instances, such as random graphs, exhibit an apparent gap between the optimal values, which can be computed by non-constructive means, and the best values achievable by fast (polynomial time) algorithms. Through a combined effort of mathematicians, computer scientists and statistical physicists, it became apparent that a potential, and in some cases, a provable barrier for designing fast algorithms bridging this gap is an intricate topology of nearly optimal solutions, in particular the presence of a certain Overlap Gap Property (OGP), which we will introduce in this talk. We will demonstrate how for many such problems the onset of the OGP phase transition indeed nearly coincides with algorithmically hard regimes and provides a provable barrier to a broad class of polynomial time algorithms. Our examples will include the problem of finding a largest independent set of a random graph, finding a largest cut in a random hypergraph, the problem of finding a ground state of a p-spin model, and also many models in high-dimensional statistics and machine learning fields. The classes of algorithms ruled out by the OGP include local algorithms, Markov Chain Monte Carlo, Approximate Message Passing and low-degree polynomial based algorithms.
Joint work with Madhu Sudan, Wei-Cuo Chen, Dmitry Panchenko, Mustazee Rahman, Aukosh Jagannath and Alex Wein.
LINK TO THE VIDEO (youtube), LINK TO THE VIDEO (bilibili)
Asymmetric containers and additive combinatorics
Abstract: The method of hypergraph containers has found a large number of applications in probabilistic combinatorics since its introduction in 2015. However, it does not seem possible to apply the usual container lemma to counting problems that involve sumsets. Recently, however, Campos discovered that (surprisingly) an asymmetric variant of the container lemma, introduced recently by Morris, Samotij and Saxton, can be applied to such problems.
In this talk I will describe Campos' original application, which resolved a conjecture of Alon, Balogh, Morris and Samotij, and a further application, which determines very precisely the typical structure of sets with small sumset. I will also mention some related work on random matrices.
This talk is based on joint work with Marcelo Campos, Mauricio Collares, Leticia Mattos, Natasha Morrison, and Victor Souza.
LINK TO THE VIDEO (youtube), LINK TO THE VIDEO (bilibili)