2021 talks:

Date (NSW/Vic)	Speaker	Title	Video
17 Feb, 11:30am	Rosalind Cameron	Surrounding cops and robber: a vertex-pursuit game	Video
3 Mar, 11:30am	Sophie Spirkl	The Erdős-Hajnal conjecture for the five-cycle	Video
17 Mar, 6pm	Rudi Mrazović	An asymptotic for the Hall--Paige conjecture	Video
31 Mar, 5pm	Patrick Morris	Triangle factors in pseudorandom graphs	Video
14 Apr, 11:30am	Mike Steel	Combinatorics of evolution
28 Apr, 5pm	Abhishek Methuku	A proof of the Erdős–Faber–Lovász conjecture
8 June, 3pm	Gordon Royle	Real chromatic roots of planar graphs (Part of the Round the World Relay in Combinatorics!)
15 Sep, 5pm	Matthew Kwan	Friendly bisections of random graphs
29 Sep, 5pm	Nina Kamčev	Common linear patterns are rare
13 Oct, 11am	Michelle Delcourt	Reducing Linear Hadwiger's Conjecture to Coloring Small Graphs
27 Oct, 10am	Rajko Nenadov	A new proof of the KŁR conjecture
10 Nov, 11am	Lutz Warnke	Does the degree-restricted random graph process have uniform distribution?
24 Nov, 11am	Maya Stein	Towards a Pósa-Seymour conjecture for hypergraphs

24 November 2021, 11am AEDT Maya Stein (University of Chile)

Towards a Pósa-Seymour conjecture for hypergraphs

Abstract: A central problem in extremal graph theory is to study degree conditions that force a graph G to contain a copy of some large or even spanning graph F. One of the most classical results in this area is Dirac's theorem on Hamilton cycles. An extension of this theorem is the Pósa-Seymour conjecture on powers of Hamilton cycles, which has been proven for large graphs by Komlós, Sárközy and Szemerédi. Extension of these results to hypergraphs, using codegree conditions and tight (powers of) cycles, have been studied by various authors. We give an overview of the known results, and then show a codegree condition which is sufficient for ensuring arbitrary powers of tight Hamilton cycles, for any uniformity. This could be seen as an approximate hypergraph version of the Pósa-Seymour conjecture. On the way to our result, we show that the same codegree conditions are sufficient for finding a copy of every spanning hypergraph of bounded tree-width which admits a tree decomposition where every vertex is in a bounded number of bags. This is joint work with Nicolás Sanhueza-Matamala and Matias Pavez-Signé.

10 November 2021, 11am AEDT Lutz Warnke (UC San Diego)

Does the degree-restricted random graph process have uniform distribution?

Abstract: The random d-process corresponds to a natural algorithmic model for generating d-regular graphs: starting with an empty graph on n vertices, it evolves by sequentially adding new random edges so that the maximum degree remains at most d. In 1999 Wormald conjectured that the final graph of the random d-process is "similar" to a uniform random d-regular graph. We show that this conjecture does not extend to a natural generalization of this process with mixed degree restrictions, i.e., where each vertex has its own degree restriction (under some mild technical assumptions). Our proof uses the method of switchings, which is usually only applied to uniform random graph models -- rather than to stochastic processes. Based on joint work in progress with Mike Molloy and Erlang Surya.

27 October 2021, 10am AEDT Rayko Nenadov (Google Zürich)

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.

13 October 2021, 11am AEDT Michelle Delcourt (Ryerson University)

Reducing Linear Hadwiger's Conjecture to Coloring Small Graphs

Abstract: In 1943, Hadwiger conjectured that every graph with no Kt minor is (t-1)-colorable for every t≥1. In a recent breakthrough, Norin, Song, and Postle proved that every graph with no Kt minor is O(t(log t)c)-colorable for every c>0.25. Subsequently Postle showed that every graph with no Kt minor is O(t(log log t)6)-colorable. We improve upon this further, showing that every graph with no Kt minor is O(t log log t)-colorable. Our main technical result yields this as well as a number of other interesting corollaries. A natural weakening of Hadwiger's Conjecture is the so called Linear Hadwiger's Conjecture that every graph with no Kt minor is O(t)-colorable. We prove that Linear Hadwiger's Conjecture reduces to small graphs as well as that Linear Hadwiger's Conjecture holds for the class of Kr-free graphs (provided t is sufficiently large). This is joint work with Luke Postle.

29 September 2021, 5pm AEST Nina Kamčev (University of Zagreb)

Common linear patterns are rare

Abstract: A linear system L over Fq is common if the number of monochromatic solutions to L=0 in any two-colouring of Fqn is asymptotically at least the expected number of monochromatic solutions in a random two-colouring of Fqn. 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. Fox, Pham and Zhao characterised common linear equations. I will talk about recent progress towards a classification of common systems of two or more linear equations. In particular, any system containing a four-term arithmetic progression is uncommon. 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. Joint work with Anita Liebenau and Natasha Morrison.

15 September 2021, 5pm AEST Matthew Kwan (IST Austria)

Friendly bisections of random graphs

Abstract: Resolving a conjecture of Füredi, we prove that almost every n-vertex graph admits a partition of its vertex set into two parts of equal size in which almost all vertices have more neighbours on their own side than across. Our proof involves some new techniques for studying processes driven by degree information in random graphs, which may be of general interest. This is joint work with Asaf Ferber, Bhargav Narayanan, Ashwin Sah and Mehtaab Sawhney.

8 June 2021, 3pm AEST Gordon Royle (University of Western Australia)

Real chromatic roots of planar graphs

(Part of the Round the World Relay in Combinatorics!)

Abstract: The chromatic polynomial P(G,q) of a graph G is the function that, for positive integer q, counts the number of proper q-colourings of the graph. The resulting function is a polynomial so, whether or not it makes any combinatorial sense, we can evaluate it at any complex number and therefore find its roots which may be integer, real of complex. The overall aim of this heavily studied topic is to understand the relationship between the properties of a graph and the location of its chromatic roots. In this talk, I will focus on the real roots of the chromatic polynomials of planar graphs. I will start by giving some of the history, background and basic results, before focussing on efforts (by myself and others) to show that planar chromatic roots are dense in the real interval (3,4). The talk is mostly at a general level and anyone familiar with the basic concepts of graphs, proper colourings of graphs and polynomials will be able to follow the gist of it.

28 April 2021, 5pm AEST 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. A brief history of the problem can be found here. Joint work with D. Kang, T. Kelly, D. Kühn and D. Osthus.

14 April 2021, 11:30am AEST Mike Steel (University of Canterbury)

Combinatorics of evolution

Abstract: In the 161 years since Darwin’s Origin of Species, biologists have developed sophisticated ways to uncover and study the hidden shared ancestry of life from genomic data. While Darwin was able to formulate his ideas without using mathematics, he later wrote how he regretted not having studied that subject further. In this talk, I will explain how ideas from combinatorics and probability theory can answer some fundamental questions arising in the reconstruction and analysis of evolutionary (phylogenetic) trees and networks.

31 March 2021, 5pm AEDT Patrick Morris (Freie Universität Berlin and Berlin Mathematical School)

Triangle factors in pseudorandom graphs

Abstract: An (n, d, λ)-graph is an n-vertex, d-regular graph with second eigenvalue in absolute value λ. When λ is small compared to d, such graphs have pseudorandom properties. A fundamental question in the study of pseudorandom graphs is to find conditions on the parameters that guarantee the existence of a certain subgraph. A celebrated construction due to Alon gives a triangle-free (n, d, λ)-graph with d=Θ(n2/3) and λ = Θ(d2 /n). This construction is optimal as having λ = o(d2 /n) guarantees the existence of a triangle in an (n, d, λ)-graph. Krivelevich, Sudakov and Szabó (2004) conjectured that if n is divisible by 3 and λ = o(d2 /n) then an (n, d, λ)-graph G in fact contains a triangle factor: vertex disjoint triangles covering the whole vertex set. In this talk, we discuss a solution to the conjecture of Krivelevich, Sudakov and Szabó. The result can be seen as a clear distinction between pseudorandom graphs and random graphs, showing that essentially the same pseudorandom condition that ensures a triangle in a graph actually guarantees a triangle factor. In fact, even more is true: as a corollary to this result and a result of Han, Kohayakawa, Person and the author, we can conclude that the same condition actually guarantees that such a graph G contains every graph on n vertices with maximum degree at most 2.

17 March 2021, 6pm AEDT Rudi Mrazović (University of Zagreb)

An asymptotic for the Hall-Paige conjecture

Abstract: Hall and Paige conjectured in 1955 that a finite group G has a complete mapping (a permutation F such that xF(x) is also a permutation) if and only if it satisfies a straightforward necessary condition. This was proved in 2009 by Wilcox, Evans, and Bray using the classification of finite simple groups and extensive computer algebra. I will discuss joint work with Sean Eberhard and Freddie Manners in which we approach the problem in a more analytic way that enables us to asymptotically count complete mappings.

3 March 2021, 11:30am AEDT Sophie Spirkl (University of Waterloo)

The Erdős-Hajnal conjecture for the five-cycle

Abstract: The Erdős-Hajnal conjecture states that for every graph H there exists c>0 such that every n-vertex graph G either contains H as an induced subgraph, or has a clique or stable set of size at least nc. I will talk about a proof of this conjecture for the case H = C5 (a five-cycle), and related results. The proof is based on an extension of a lemma about bipartite graphs due to Pach and Tomon. This is joint work with Maria Chudnovsky, Alex Scott, and Paul Seymour.

17 February 2021, 11:30am AEDT Rosalind Cameron (University of Canterbury)

Surrounding cops and robber: a vertex-pursuit game

Abstract: The vertex-pursuit game of cops and robbers, introduced by Nowakowski and Winkler (1983), is played on a graph where a team of cops aim to occupy the same vertex as the robber. The cop number of a graph is the least number of cops required to guarantee capture, and this is conjectured to be O(\sqrt{n}) for a graph on n vertices. In search of an upper bound on the cop number of a graph, we introduce a variant of the original game whereby the cops aim to occupy each of the robber's neighbouring vertices. The surrounding cop number \sigma(G) of a graph G is the least number of cops required to surround a robber in G. In this talk I will present a number of results and open problems regarding the surrounding cop number. Results include general bounds as well as exact values for several classes of graphs. Particular classes of interest include product graphs, graphs arising from combinatorial designs, and generalised Petersen graphs. Joint work with Andrea Burgess, Nancy Clarke, Peter Danziger, Stephen Finbow, Caleb Jones and David Pike.