Skip to main content Skip to navigation

Combinatorics Seminar 2021-22

Seminar organisers: Jan Grebík and Oleg Pikhurko

Warwick's combinatorics seminar in 2021-22 will be held in a hybrid format 2-3pm UK time on Wednesdays, occasionally 4-5pm UK time on Wednesdays (see the notes below), in the room B3.02 and on ZOOM.

Join Zoom Meeting
https://zoom.us/j/99265174877?pwd=Q3RSZVNxUWx5RGtYUGhOQ0wvd2pSdz09

Meeting ID: 992 6517 4877
Passcode: WC2021

Term 1

Date Name Title Note
6 Oct Allan Sly (Princeton) Factor of IID for the Ising model on the tree online
20 Oct Henry Towsner (Pennsylvania) Regularity Lemmas as Structured Decompositions online
27 Oct Rob Silversmith (Warwick) Cross-ratios and perfect matchings  
3 Nov Joseph Hyde (Warwick) Progress on the Kohayakawa-Kreuter conjecture  
10 Nov Łukasz Grabowski (Lancaster) Directed analogues of expander graphs and random compact subsets of Rn  
17 Nov Natasha Morrison (Victoria) Uncommon systems of equations online only, 4pm
24 Nov Carla Groenland (Utrecht) Asymptotic dimension of graph classes online
1 Dec Martin Winter (Warwick) Some modern open problems on polytopes with symmetries and regularities  
8 Dec George Kontogeorgiou (Warwick) Equivariant Cayley Complex Embeddings  

Factor of IID for the Ising model on the tree (Allan Sly), 14:00, B3.02+ZOOM

It's known that there are factors of IID for the free Ising model on the d-regular tree when it has a unique Gibbs measure and not when reconstruction holds (when it is not extremal). We construct a factor of IID for the free Ising model on the d-regular tree in (part of) its intermediate regime, where there is non-uniqueness but still extremality. The construction is via the limit of a system of stochastic differential equations.

Regularity Lemmas as Structured Decompositions (Henry Towsner), 14:00, B3.02+ZOOM

One way of viewing Szemerédi's regularity lemma is that it gives a way of decomposing a graph (approximately) into a structured part (the "unary" data) and a random part. Then hypergraph regularity, the generalization to k-uniform hypergraphs, can be viewed as a decomposition into multiple "tiers" of structure - a unary part as well as a binary part and so on, and then finally a random part.

We'll discuss how an analytic approach can make these decompositions exact instances of the conditional expectation in probability, and how these analytic proofs relate to combinatorial proofs with explicit bounds. Finally, we'll discuss regularity lemmas for other mathematical objects, focusing on the example of ordered graphs and hypergraphs, and show how the "tiers of structures" perspective makes it possible to see regularity lemmas for other mathematical objects as examples of the regularity lemma for hypergraphs.

(No prior knowledge of the regularity lemma and its variants is assumed.)

Cross-ratios and perfect matchings (Rob Silversmith), 14:00, B3.02+ZOOM

I’ll describe a simple process from algebraic geometry that takes in a collection of 4-element subsets S1,S2,…,Sn-3 of [n], and outputs a nonnegative integer called a cross-ratio degree. I’ll discuss several interpretations of cross-ratio degrees in algebra, algebraic geometry, and tropical geometry, and present a combinatorial algorithm for computing them, due to C. Goldner. I’ll then present a perhaps-surprising upper bound for cross-ratio degrees in terms of matchings.

Progress on the Kohayakawa-Kreuter conjecture (Joseph Hyde), 14:00, B3.02+ZOOM

Let H1, ..., Hr be graphs. We write G(n,p) → (H1, ..., Hr) to denote the property that whenever we colour the edges of G(n,p) with colours from the set [r] := {1, ..., r} there exists some 1 ≤ i ≤ r and a copy of Hi in G(n,p) monochromatic in colour i.
 

There has been much interest in determining the asymptotic threshold function for this property. Rödl and Ruciński (1995) determined the threshold function for the general symmetric case; that is, when H1 = ... = Hr. A conjecture of Kohayakawa and Kreuter (1997), if true, would effectively resolve the asymmetric problem. Recently, the 1-statement of this conjecture was confirmed by Mousset, Nenadov and Samotij (2021+). The 0-statement however has only been proved for pairs of cycles, pairs of cliques and pairs of a clique and a cycle.

 

In this talk we introduce a reduction of the 0-statement of Kohayakawa and Kreuter's conjecture to a certain deterministic, natural subproblem. To demonstrate the potential of this approach, we show this subproblem can be resolved for almost all pairs of regular graphs (satisfying properties one can assume when proving the 0-statement).

Directed analogues of expander graphs and random compact subsets ot Rn (Lukasz Grabowski), 14:00, B3.02+ZOOM

I will talk about two separate projects. The first one is a joint work with Endre Csoka (published in "Combinatorics, Probability and Computing"), where we construct "extender" graphs - sparse directed graphs with the property that it is impossible to remove a small amount of edges and obtain a graph which does not have long directed paths (long is
|V|δ, where δ>0 is an absolute constant). Extenders are a directed analogue of expander graphs, since the latter ones are characterised by the property that it is impossible to remove a small amount of edges and obtain graphs which have small connected components. I'll discuss some conjectures in circuit complexity which motivated us to introduce extenders.

The second project is a joint work with Tomasz Ciesla (preprint available on arxiv). We construct compacts subsets of R2 which are not "domains of expansion", which answers a question about spectral properties of group actions, raised by Adrian Ioana.

Apart from the general theme of "expansion", both projects are related by the method which is used to construct suitable examples - in both cases the construction is probabilistic, and the required properties follow from entropy estimates.

Uncommon systems of equations (Natasha Morrison), 16:00, ZOOM only

A system of linear equations L over Fq is common if the number of monochromatic solutions to L in any two-colouring of (Fq)n is asymptotically at least the expected number of monochromatic solutions in a random two-colouring of (Fq)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.

Asymptotic dimension of graph classes (Carla Groenland), 14:00, B3.02+ZOOM

The notion of asymptotic dimension of graph classes is borrowed from an invariant of metric spaces introduced by Gromov in the context of geometric group theory. In the talk, I will try to give some intuition for the definition and our proof techniques. Our main result is that each minor-closed family of graphs has asymptotic dimension at most 2. I will also mention some corollaries to clustered colouring and CS notions such as weak sparse partition schemes and weak diameter network decompositions. A special case of our main result also implies that complete Riemannian surfaces have asymptotic dimension (even Assouad-Nagata dimension) at most 2 (which was previously unknown).

This is based on joint work with M. Bonamy, N. Bousquet, L. Esperet, C.-H. Liu, F. Pirot and A. Scott.

Some modern open problems on polytopes with symmetries and regularities (Martin Winter), 14:00, B3.02+ZOOM

Polytope theory has itself established as a modern field of mathematics with deep connections to geometry, combinatorics, and algebra. Convex polytopes with many symmetries and regularities however have thereby played only a secondary role and are often considered as a fascinating, yet esoteric subject of the past. In this talk I want to rectify this by presenting up to three modern open problems that connect the study of such polytopes to representation theory, hyperplane arrangements and Weyl groupoids, as well as spectral graph theory. More specifically, the three topics are the possible symmetries of orbit polytopes, inscribed and simple zonotopes, and the reconstruction of polytopes from graphs via spectral graph theory.

Equivariant Cayley Complex Embeddings (George Kontogeorgiou), 14:00, B3.02+ZOOM

In recent years, a lot of progress has been made in high-dimensional combinatorics, i.e. extending concepts from graph theory to higher dimensional CW-complexes. Two such concepts of particular interest are (i) group actions and (ii) embeddings. In this talk we will prove that every finite group which admits a faithful topological action over S3 has a generalised Cayley complex which embeds equivariantly in S3. In the process, we will see some recent theorems and lemmas concerning 2-complex embeddings and group actions over 2-complexes, and we will derive a new combinatorial characterization of finite groups acting faithfully and topologically over S3.