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).
Join Zoom Meeting
https://us02web.zoom.us/j/82963632253?pwd=Q0psYyt0MURYSy9haWROQzhXRmMwQT09
Meeting ID: 829 6363 2253
Passcode: WC2021
Term 3
Date  Name  Title  Note 

30 Apr  Agnes Backhausz (Budapest)  Typicality and entropy of processes on infinite trees  
7 May  Gwen McKinley (San Diego)  Counting integer partitions with the method of maximum entropy  5:30pm UK time 
14 May  Pascal Schweitzer (Darmstadt)  Automorphisms of graphs with a forbidden minor  
21 May  Gabor Elek (Lancaster)  Uniform amenability  
28 May  PierreLoïc Méliot (Orsay)  Dependency graphs, upper bounds on cumulants and singular graphons  
4 Jun  Gabor Kun (Budapest)  Graphings without measurable perfect matchings  
11 Jun  Nicholas Cook (Duke)  Regularity method and large deviation principles for the Erdős–Rényi hypergraph  
18 Jun  Vishesh Jain (Stanford)  Towards the sampling Lovász Local Lemma  
25 Jun  Tom Kelly (Birmingham)  A proof of the Erdős–Faber–Lovász conjecture  
2 Jul  Will Perkins (Chicago)  Polymer models, cluster expansion, and local limit theorems: counting independent sets in the hypercube 
Typicality and entropy of processes on infinite trees (Agnes Backhausz), 14:00, ZOOM
When we study random dregular graphs from the point of view of graph limit theory, the notion of typical processes arise naturally. These are certain invariant families of random variables indexed by the infinite regular tree. Since this tree is the local limit of random dregular graphs when d is fixed and the number of vertices tends to infinity, we can consider the processes that can be approximated with colorings (labelings) of random dregular graphs. These are the socalled typical processes, whose properties contain useful information about the structure of finite random regular graphs. In earlier works, various necessary conditions have been given for a process to be typical, by using correlation decay or entropy inequalities. In the work presented in the talk, we go in the other direction and provide sufficient entropy conditions in the special case of edge Markov processes. This condition can be extended to unimodular GaltonWatson random trees as well. Joint work with Charles Bordenave and Balázs Szegedy (https://arxiv.org/abs/2102.02653).
Counting integer partitions with the method of maximum entropy (Gwen McKinley), 17:30, ZOOM, slides
We give an asymptotic formula for the number of partitions of an integer n where the sums of the kth powers of the parts are also fixed, for some collection of values k. To obtain this result, we reframe the counting problem as an optimization problem, and find the probability distribution on the set of all integer partitions with maximum entropy among those that satisfy our restrictions in expectation (in essence, this is an application of Jaynes' principle of maximum entropy). This approach leads to an approximate version of our formula as the solution to a relatively straightforward optimization problem over realvalued functions. To establish more precise asymptotics, we prove a local central limit theorem using an equidistribution result of Green and Tao.
A large portion of the talk will be devoted to outlining how our method can be used to rederive a classical result of Hardy and Ramanujan, with an emphasis on the intuitions behind the method, and limited technical detail. This is joint work with Marcus Michelen and Will Perkins.
Automorphisms of graphs with a forbidden minor (Pascal Schweitzer), 14:00, ZOOM
According to Frucht’s classic theorem, every finite group is the automorphism group of a finite graph (up to isomorphism). We say the class of all graphs is universal. Babai proved in 1974 that graph classes with a forbidden minor, such as planar graphs, graphs of bounded genus, and graphs of bounded tree width, are not universal. He also made three conjectures regarding automorphisms of such graphs. I will describe a structure theorem of automorphism groups of such graphs, affirming these conjectures.
This is joint work with Martin Grohe and Daniel Wiebking.
Uniform amenability (Gabor Elek), 14:00, ZOOM
According to the classical result of Connes, Feldman and Weiss, measured hyperfiniteness of a group action is equivalent to measured amenability. In the Borel category it is known that hyperfiniteness implies amenability and it is conjectured that the converse is true. Based on the work of AnantharamanDelaroche and Renault, one can introduce the notion of uniform amenability, a strengthening of measured amenability (it is a sort of exactness in the category of measurable actions, so the famous GromovOsajda groups have no free uniformly amenable actions). One can also introduce the notion of uniform hyperfiniteness in a rather natural way. We prove that the two notions are equivalent provided that the measurable action satisfies a boundedness condition for the RadonNikodym derivative (e.g. in the case of Poisson boundaries).
Dependency graphs, upper bounds on cumulants and singular graphons (PierreLoïc Méliot), 14:00, ZOOM, slides
Consider a sum of random variables S = ∑_{v∈ V} A_{v}. If the variables A_{v} are weakly dependent, then it is well known that under mild assumptions, the distribution of S is close to a normal distribution. The theory of dependency graphs enables one to make this statement precise. In this framework, we shall present new bounds on the cumulants of S, which enable one to have a combinatorial approach of this probabilistic results. One of the main application is the study of the fluctuations of the densities of subgraphs in a random graph chosen according to a graphon model. We shall see that two behavior are possible, according to whether the graphon is generic or singular. In the latter case, the limiting distributions that appear are nonGaussian.
Graphings without measurable perfect matchings (Gabor Kun), 14:00, ZOOM
Measurable matchings of graphings (this is, probability measure preserving Borel graphs) have attracted a great deal of attention in the last decades. The BanachTarski paradox shows that the Hall condition does not guarantee the existence of a measurable perfect matching in a bipartite graphing. Laczkovich gave an example when the measurable Hall condition is not sufficient either. We discuss the few such counterexamples.
Regularity method and large deviation principles for the Erdős–Rényi hypergraph (Nicholas Cook), 14:00, ZOOM
In recent years there has been intense activity on the problem of estimating the upper tail for counts of a fixed subgraph in a sparse Erdős–Rényi graph, combining tools and perspectives from diverse areas such as extremal graph theory, statistical physics, stochastic analysis and spectral theory. I will discuss some recent extensions of these results to the hypergraph setting. Our approach rests on new decomposition theorems and counting lemmas for sparse Bernoulli tensors, extending classic results from the regularity method for dense graphs. These results are formulated in terms of a new class of cuttype norms specially tailored for the sparse setting. Based on joint work with Amir Dembo and Huy Tuan Pham.
Towards the sampling Lovász Local Lemma (Vishesh Jain), 14:00, ZOOM
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 under LLLlike conditions. I will discuss recent progress on this problem, joint with Huy Tuan Pham (Stanford) and Thuy Duong Vuong (Stanford).
A proof of the Erdős–Faber–Lovász conjecture (Tom Kelly), 14:00, ZOOM
The 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 joint work with Dong Yeap Kang, Daniela Kühn, Abhishek Methuku, and Deryk Osthus, we proved this conjecture for every sufficiently large n. In this talk, I will present the history of this conjecture and sketch our proof in some special cases.
Polymer models, cluster expansion, and local limit theorems: counting independent sets in the hypercube (Will Perkins), 14:00, ZOOM
I'll discuss how local central limit theorems can be used in combination with two tools from statistical physics, polymer models and the cluster expansion, to asymptotically enumerate independent sets of a given size in the hypercube. Joint work with Matthew Jenssen and Aditya Potukuchi (arxiv:2106.09709)
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)  On polynomials that vanish to high order on most of the hypercube  
12 Feb  Gábor Pete (Budapest)  The Free Uniform Spanning Forest is disconnected in some virtually free groups, depending on the generating set  
19 Feb  Jan Kurkofka (Hamburg) 
Every infinitely edgeconnected graph contains the Farey graph or T_{ℵ_{0}}*t as a minor 

26 Feb  Lutz Warnke (Georgia Tech)  Prague dimension of random graphs  
5 Mar  Louis Esperet (Grenoble)  Asymptotic dimension of graphs  1:30pm UK time 
12 Mar  Annie Raymond (Massachusetts Amherst)  Graph Density Inequalities, Sums of Squares and Tropicalization  
19 Mar  Daniel Spielman (Yale)  Finite Free Probability and Ramanujan Graphs  5:30pm UK time 
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.
On polynomials that vanish to high order on most of the hypercube (Lisa Sauermann), 14:00, ZOOM
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 nonzero 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.
The Free Uniform Spanning Forest is disconnected in some virtually free groups, depending on the generating set (Gábor Pete), 14:00, ZOOM
The uniform random spanning tree of a finite graph is a classical object in probability and combinatorics. In an infinite graph, one can take any exhaustion by finite subgraphs, with some boundary conditions, and take the limit measure. The Free Uniform Spanning Forest (FUSF) is one of the natural limits, but it is less understood than the wired version, the WUSF. Taking a finitely generated group, several properties of WUSF and FUSF have been known to be independent of the chosen Cayley graph of the group: the average degree in WUSF and in FUSF; the number of ends in the components of the WUSF and of the FUSF; the number of trees in the WUSF. Lyons and Peres asked if this latter should also be the case for the FUSF.
In joint work with Ádám Timár, we give two different Cayley graphs of the same group such that the FUSF is connected in one of them but has infinitely many trees in the other. Since our example is a virtually free group, this is also a counterexample to the general expectation that such "treelike" graphs would have connected FUSF. Many open
questions are inspired by the results.
Every infinitely edgeconnected graph contains the Farey graph or T_{ℵ_{0}} * t as a minor (Jan Kurkofka), 14:00, ZOOM
The Farey graph plays a role in a number of mathematical fields ranging from group theory and number theory to geometry and dynamics. Curiously, graph theory is not among these. We show that the Farey graph plays a central role in graph theory too: it is one of two infinitely edgeconnected graphs that must occur as a minor in every infinitely edgeconnected graph. Previously it was not known that there was any set of graphs determining infinite edgeconnectivity by forming a minorminimal list in this way, let alone a finite set.
Prague dimension of random graphs (Lutz Warnke), 14:00, ZOOM
The Prague dimension of graphs was introduced by Nesetril, Pultr and Rodl in the 1970s: as a combinatorial measure of complexity, it is closely related to clique edges coverings and partitions. Proving a conjecture of Furedi and Kantor, we show that the Prague dimension of the binomial random graph is typically of order n/(log n) for constant edgeprobabilities. The main new proof ingredient is a PippengerSpencer type edgecoloring result for random hypergraphs with large uniformities, i.e., edges of size O(log n).
Based on joint work with He Guo and Kalen Patton, see https://arxiv.org/abs/2011.09459.
Asymptotic dimension of graphs (Louis Esperet), 13:30, ZOOM
The asymptotic dimension of a metric space is a notion introduced by Gromov in the 90s, in connection with geometric group theory. In the special case of the shortest path metric associated to a graph, a related notion, called "weak network decomposition" has been independently considered by theoretical computer scientists, with a different motivation. I will also explain some links with the classical notion of graph coloring, and some variants that have been studied since the end of the 90s.
A class of graphs is minorclosed if any graph obtained from a graph in the class by deleting vertices or edges, or contracting edges, is still in the class. A typical example is the class of all graphs embeddable on a fixed surface. We prove that every proper minorclosed family of graphs has asymptotic dimension at most 2, which gives optimal answers to a question of Fujiwara and Papasoglu and to a problem raised by Ostrovskii and Rosenthal on minor excluded groups.
Joint work with M. Bonamy, N. Bousquet, C. Groenland, C.H. Liu, F. Pirot, and A. Scott.
Graph Density Inequalities, Sums of Squares and Tropicalization (Annie Raymond), 14:00, ZOOM
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.
Finite Free Probability and Ramanujan Graphs (Daniel Spielman), 17:30, ZOOM
We introduce a finite analog of Voiculescu's Free Probability that allows us to compute the expected characteristic polynomials of certain random matrices and to prove bounds on the locations of the roots of those polynomials. We sketch how this theory may be used to prove that there exist bipartite Ramanujan graphs of every degree and number of vertices.
No prior knowledge of free probability or Ramanujan graphs will be assumed.
This is joint work with Adam Marcus and Nikhil Srivastava.
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.