John Urschel: Old and New Results on the Spread of the Spectrum of a Graph

6th December, 2021

The spread of a matrix is defined as the diameter of its spectrum. This quantity has been well-studied for general matrices and has recently grown in popularity for the specific case of the adjacency matrix of a graph. Most notably, Gregory, Herkowitz, and Kirkland proved a number of key results for the spread of a graph and made two key conjectures regarding graphs that maximize spread. In particular, they conjectured that the maximum spread over all graphs with a fixed number of vertices is given by the join of a clique and independent set and that the maximum spread over all graphs with a fixed number of vertices and edges is given by a bipartite graph if one exists. In this talk, I will review some of the key results regarding the spread of a general matrix, some known results for the specific case of an adjacency matrix, and give a high-level outline of a recent paper regarding these two conjectures.

Tim Susse: Geometric Properties of Random Right-angled Coxeter Groups

15th April, 2021

Given a finite simplicial graph, we can generate a right-angled Coxeter group (RACG): each vertex corresponds to a generator and two generators commute if and only if the corresponding vertices are adjacent. This assignment is unique up to isomorphism, which allows us to characterize geometric and algebraic properties of the RACG using combinatorial properties of its generating graph. This also allows us to use a model of random graphs to study random RACGs.

In this talk we will focus on the divergence of a RACG. Using the Erdös-Renyi random graph model, we show that at a wide range of densities a random RACG asymptotically almost surely has quadratic divergence. We will also give a sharp threshold, below which a random RACG has (almost surely) at least cubic divergence, and above which its divergence is (almost surely) at most quadratic. This is joint work with Jason Behrstock, Victor Falgas-Ravry and Mark Hagen.

Corrine Yap: A Topological Turán Problem

15th March, 2021

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 greater than 2. In this talk, we give an answer for general k using dependent random choice - a method that has produced powerful results in extremal graph theory, additive combinatorics, and Ramsey theory.

Harald Helfgott: Expansion, divisibility and parity

5th March, 2021

We will discuss a graph that encodes the divisibility properties of integers by primes. We show that this graph is shown to have a strong local expander property almost everywhere. We then obtain several consequences in number theory, beyond the traditional parity barrier. For instance: for λ the Liouville function (that is, the completely multiplicative function with λ(p) = -1 for every prime), (1/log x) ∑n ≤ x λ(n) λ(n+1)/n = O(1/√(log log x)), which is stronger than a well-known result by Tao. We also manage to prove, for example, that λ(n+1) averages to 0 at almost all scales when n restricted to have a specific number of prime divisors Ω(n)=k, for any "popular" value of k (that is, k = log log N + O(√(log log N)) for n ≤ N. We will give a quick overview of the combinatorial ideas behind the proof.

Cosmin Pohoata: New lower bounds for the Erdős box problem

14th December, 2020

We discuss some new lower bounds for the Erdős box problem, the problem of estimating the extremal number of the complete d-partite d-uniform hypergraph with two vertices in each part, thereby improving on work of Gunderson, Rödl and Sidorenko.

Sean Eberhard: Diameter of high-rank classical groups with random generators

22nd November, 2020

Babai's conjecture asserts that the diameter of the Cayley graph of any finite simple group G is bounded by (log |G|)O(1). This conjecture has been resolved for groups of bounded rank, but for groups of unbounded rank such as SLn(2) it is wide open. Even for random generators, only the case of alternating groups is resolved. In this talk we sketch the proof of Babai's conjecture for SLn(p), p = O(1), with at least three random generators. The proof extends to other classical groups over 𝔽q if we have at least q100 random generators. The heart of the proof consists of showing that the Schreier graph of SLn(q) acting on 𝔽qn with respect to q100 random generators is an expander graph.

Annalisa Massaccesi: Currents with coefficients in groups and applications to network optimization problems

15th October, 2020

In this seminar I will review the theory of flat G-chains, as they were introduced by H. W. Fleming in 1966, and currents with coefficients in groups. One of the most recent development of the theory concerns its application to the Steiner tree problem and other minimal network problems which are related with a Eulerian formulation of the branched optimal transport. Starting from a 2016 paper by A. Marchese and myself, I will show how these problems are equivalent to a mass-minimization problem in the framework of currents with coefficients in a (suitably chosen) normed group.

David Conlon: The regularity method for graphs with few 4-cycles

12th October, 2020

We develop a sparse graph regularity method that applies to graphs with few 4-cycles, including new counting and removal lemmas for 5-cycles in such graphs. Some applications include:

   •  Every n-vertex graph with no 5-cycle can be made triangle-free by deleting o(n3/2) edges.
   •  For r ≥ 3, every n-vertex r-graph with girth greater than 5 has o(n3/2) edges.
   •  Every subset of [n] without a non-trivial solution to the equation x1 + x2 + 2x3 = x4 + 3x5 has size o(√n).

Gabriel Verret: Local actions in vertex-transitive graphs

18th September, 2020

A graph is vertex-transitive if its group of automorphism acts transitively on its vertices. A very important concept in the study of these graphs is that of local action, that is, the permutation group induced by a vertex-stabilizer on the corresponding neighbourhood. I will explain some of its importance and discuss some attempts to generalize it to the case of directed graphs.

Peter Keevash: Isoperimetric Stability

14th September, 2020

Understanding approximate minimisers for isoperimetric problems is of fundamental importance in Combinatorics, Analysis and Geometry. We will survey some recent progress on these problems in three settings: the Extremal Combinatorics setting of the discrete cube (joint with Eoin Long), the Additive Combinatorics setting of Cayley digraphs on lattices (joint with Ben Barber, Joshua Erde and Alexander Roberts) and the Discrete Analysis setting of Boolean functions with small influence, with applications to sharp thresholds and Extremal Combinatorics via the Junta Method (joint with Noam Lifshitz, Eoin Long and Dor Minzer).