Combinatorics Seminar 202021
Seminar organisers: Jan Grebík and Oleg Pikhurko
Warwick's combinatorics seminar in 202021 will be held online 23pm UK time on Fridays, occasionally 5:306:30pm UK time on Fridays (see the notes below).
Zoom link:
https://us02web.zoom.us/j/87873561345
Meeting ID: 878 7356 1345
Passcode: WC2021
Term 2
Date  Name  Title  Note 

15 Jan  Pál Galicza (Budapest)  Sparse reconstruction for iid variables  
22 Jan  Alexander Razborov (Chicago)  Theons and quasirandomness  5:30pm UK time 
29 Jan  Lisa Sauermann (IAS)  TBA  
5 Feb  TBA  TBA  
12 Feb  
19 Feb  
26 Feb  
5 Mar  
12 Mar  
19 Mar 
Sparse reconstruction for iid variables (Pál Galicza), 14:00, ZOOM
We first show that, if the underlying measure is a product measure, then no sparse reconstruction is possible for any sequence of transitive functions. We discuss the question in different frameworks, measuring information content in L2 and with entropy. We also highlight some interesting connections with cooperative game theory.
Using our results for transitive sequences of functions, we answer a question posed by Itai Benjamini and show that the leftright crossing event for critical planar percolation on the square lattice does not admit sparse reconstruction either. Joint work with Gábor Pete.
Theons and quasirandomness (Alexander Razborov), 17:30, ZOOM
There are two known approaches to the theory of limits of discrete combinatorial objects: geometric (graph limits) and algebraic (flag algebras). In the first part of the talk we present a general framework intending to combine useful features of both theories and compare it with previous attempts of this kind. Our main objects are Tons, for a universal relational firstorder theory T; they generalize many previously considered partial cases, some of them (like permutons) in a nontrivial way.
In the second part we apply this framework to offer a new perspective on quasirandomness for combinatorial objects more complicated than ordinary graphs. Our quasirandomness properties are natural in the sense that they do not use ad hoc densities and they are preserved under the operation of defining combinatorial structures of one kind from structures of a different kind. One key concept in this theory is that of unique coupleability roughly meaning that any alignment of two objects on the same ground set should ``look like'' random.
Based on joint work with Leonardo Coregliano.
Term 1
Date  Name  Title 
9 Oct 
László Lovász (Budapest) 

16 Oct 
Marthe Bonamy (Bordeaux) 
Graph recolouring 
23 Oct 
Gábor Tardos (Budapest) 
Convergence and limits of finite trees 
30 Oct  Maria Chudnovsky (Princeton)  Evenhole free graphs of bounded degree have bounded treewidth 
6 Nov  Boris Bukh (Pittsburgh)  Empty axisparallel boxes 
13 Nov  Tibor Szabó (FU Berlin)  Maderperfect digraphs 
20 Nov  Benny Sudakov (ETH Zurich)  Large independent sets from local considerations 
27 Nov  Anton Bernshteyn (Georgia Tech)  Measurable colorings, the Lovász Local Lemma, and distributed algorithms 
4 Dec 
Bhargav Narayanan (Rutgers) 
Homeomorphs 
11 Dec  Hong Liu (Warwick)  Extremal density for sparse minors and subdivisions 
Graph limits, measures, and flows (László Lovász), 14:00, ZOOM
The theory of graph limits is only understood to a somewhat satisfactory degree in the cases of dense graphs and of bounded degree graphs. There is, however, a lot of interest in the intermediate cases. It appears that the most important constituents of graph limits in the general case will be Markov spaces (Markov chains on measurable spaces with a stationary distribution).
This motivates our goal to extend some important theorems from finite graphs to Markov spaces or, more generally, to measurable spaces. In this talk we show that much of flow theory, one of the most important areas in graph theory, can be extended to measurable spaces. In particular, the Hoffman Circulation Theorem, the MaxFlowMinCut Theorem, Multicommodity Flow Theorem, and several other results have simple and elegant extensions to measures.
Graph recolouring (Marthe Bonamy), 14:00, ZOOM
Given a solution to a problem, we can try and apply a series of elementary operations to it, making sure to remain in the solution space at every step. What kind of solutions can we reach this way? How fast? This is motivated by a variety of applications, from statistical physics to reallife scenarios, including enumeration and sampling. In this talk, we will discuss various positive and negative results, in the special case of graph colouring.
Convergence and limits of finite trees (Gábor Tardos), 14:00, ZOOM, slides
Seeing the success of limit theory of dense finite graphs with graphons as their limit objects we developed a similar (?) theory for finite trees. In order for the sampling limit to make sense we need to make the trees "dense"  we do this by considering them as metric spaces with the normalized graph distance. Using ultaproducts is a simple and elegant way to find unique limit objects (we call them dendrons) and also to highlight similarities and major differences from the theory of dense graph limits. For the underlying quantitative approximation results, one needs more "down to earth" techniques to be developed.
This is joint work with Gábor Elek.
Evenhole free graphs of bounded degree have bounded treewidth (Maria Chudnovsky), 14:00, ZOOM
Tree decompositions are a powerful tool in structural graph theory that is traditionally used in the context of forbidden graph minors. Connecting tree decompositions and forbidden induced subgraphs has so far
largely remained out of reach. Traditionally to bound the treewidth of a graph, one finds a way to decompose it by a socalled laminar collection of decompositions. Recently, in joint work with Tara Abrishami and Kristina
Vuskovic, we proved that evenhole free graphs of bounded degree have bounded treewidth. To do so we used "star cutset separations" that arise naturally in the context of evenholefree graphs. While the set of star cutset separations is far from being noncrossing, it turns out that one can partition it into a bounded number of laminar collections, and this is sufficient for our purposes.
In this talk we will present an outline of the proof.
Empty axisparallel boxes (Boris Bukh), 14:00, ZOOM
How to place n points inside the ddimensional unit cube so every large axisparallel box contains at least one point? We discuss the motivation as well as a partial solution to this problem. This is a joint work with TingWei Chao.
Maderperfect digraphs (Tibor Szabó), 14:00, ZOOM
We investigate the relationship of dichromatic number and subdivision containment in digraphs. We call a digraph Maderperfect if for every (induced) subdigraph F, any digraph of dichromatic number at least v(F) contains an Fsubdivision. We show that, among others, arbitrary orientated cycles, bioriented trees, and tournaments on four vertices are Maderperfect. The first result settles a conjecture of Aboulker, Cohen, Havet, Lochet, Moura, and Thomassé, while the last one extends Dirac's Theorem about 4chromatic graphs containing a K_{4}subdivision to directed graphs. The talk represents joint work with Lior Gishboliner and Raphael Steiner.
Large independent sets from local considerations (Benny Sudakov), 14:00, ZOOM
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 ErdosHajnal and LinialRabinovich in the early 90's. How large must the independence number α(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.
Measurable colorings, the Lovász Local Lemma, and distributed algorithms (Anton Bernshteyn), 14:00, ZOOM
In the past twenty or so years, a rich theory has emerged concerning the behavior of graph colorings, matchings, and other combinatorial notions under additional regularity requirements, for instance measurability. It turns out that this area is closely related to distributed computing, i.e., the part of computer science concerned with problems that can be solved efficiently by a decentralized network of processors. A key role in this relationship is played by the Lovász Local Lemma and its analogs in the measurable setting. In this talk I will outline this relationship and present a number of applications.
Homeomorphs (Bhargav Narayanan), 14:00, ZOOM
Nati Linial asked the following basic problem in 2006: Given a kdimensional simplicial complex S, how many facets can a kcomplex on n vertices have if it contains no topological copy of S? This is a beautiful and natural question, but results in low dimensions apart (k <= 2), very little was previously known. In this talk, I’ll provide an answer in all dimensions and take the scenic route to the answer, surveying many natural problems about simplicial complexes along the way.
Extremal density for sparse minors and subdivisions (Hong Liu), 14:00, ZOOM
How dense a graph has to be to necessarily contain (topological) minors of a given graph H? When H is a complete graph, this question is well understood by result of Kostochka/Thomason for clique minor, and result of BollobasThomason/KomlosSzemeredi for topological minor. The situation is a lot less clear when H is a sparse graph. We will present a general result on optimal density condition forcing (topological) minors of a wide range of sparse graphs. As corollaries, we resolve several questions of Reed and Wood on embedding sparse minors. Among others,
 (1+o(1))t^{2} average degree is sufficient to force the t x t grid as a topological minor;
 (3/2+o(1))t average degree forces every tvertex planar graph as a minor, and the constant 3/2 is optimal, furthermore, surprisingly, the value is the same for tvertex graphs embeddable on any fixed surface;
 a universal bound of (2+o(1))t on average degree forcing every tvertex graph in any nontrivial minorclosed family as a minor, and the constant 2 is best possible by considering graphs with given treewidth.
Joint work with John Haslegrave and Jaehoon Kim.