Welcome! The CMSA seminar aims to bring together combinatorialists of Australasia and the world.
It started during the COVID19 lockdown days, and may continue afterwards.
We plan to hold the seminar roughly every two weeks on Wednesday, starting on the 20th of May.
Videos of some past talks can be found here.
Subscribe: Email cmsawebinar AT monash.edu with the subject "subscribe". We send announcements and zoom details before every talk.
Organisers: Anita Liebenau and Nina Kamčev.
Please email us with your feedback and suggestions.
We will mainly be using one of the following two time slots, conversion to your time zone is available via the links:
11:30am AEDT, 7:30pm ET or
5pm AEDT, 7am CET .
2021 talks:
2020 talks:
Date (NSW/Vic)  Speaker  Title  Video 
20 May '20, 11am
 Brendan McKay 
A scientist's adventure into pseudoscience: the strange case of the Bible Codes 

3 Jun '20, 4pm
 John Bamberg  Vanishing Krein Parameters in Finite Geometry 
Video 
17 Jun '20, 5pm
 Fiona Skerman  Branching processes with merges and locality of hypercube's critical percolation 

1 Jul '20, 5pm

Tibor Szabó 
Turán numbers, norm graphs, quasirandomness 

15 Jul '20, 11am

Daniel Horsley 
Generating digraphs with derangements 
Video 
22 Jul '20, 5pm
 Katherine Staden  Two conjectures of Ringel 
Video 
29 Jul '20, 5pm
 Annika Heckel  Nonconcentration of the chromatic number 
Slides 
19 Aug '20, 11am
 Tamás Makai  Majority dynamics in the dense binomial random graph 
Video 
26 Aug '20, 11am
 Tuan Tran  Singularity of random combinatorial matrices 
Video 
9 Sep '20, 11am
 Geertrui Van de Voorde  Sets with few intersection numbers in finite planes 

22 Sep '20, 5pm
 David Conlon  The random algebraic method 

6 Oct '20, 11am
 Tony Huynh  Idealness of kwise intersecting families 
Video 
27 Oct '20, 5pm
 Simone Linz  Reconstructing phylogenetic networks from trees 
Video 
10 Nov '20, 6pm
 Vida Dujmović  Product Structure Theory with applications 

24 Nov '20, 3pm
 Kevin Hendrey  Obstructions to bounded branchdepth in matroids 
Video 
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.

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.

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 nvertex, dregular 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 trianglefree (n, d, λ)graph with d=Θ(n^{2/3}) and λ = Θ(d^{2} /n). This construction is optimal as having λ = o(d^{2} /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(d^{2} /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 HallPaige 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ősHajnal conjecture for the fivecycle 
Abstract:
The ErdősHajnal conjecture states that for every graph H there exists c>0 such that every nvertex graph G either contains H as an induced subgraph, or has a clique or stable set of size at least n^{c}. I will talk about a proof of this conjecture for the case H = C_{5} (a fivecycle), 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 vertexpursuit game 
Abstract:
The vertexpursuit 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.

24 November 2020, 3pm AEDT Kevin Hendrey (Institute for Basic Science) 
Obstructions to bounded branchdepth in matroids 
Abstract:
DeVos, Kwon, and Oum introduced a notion of branchdepth of matroids as a natural analogue to treedepth of graphs, and conjectured that matroids of sufficiently large branchdepth contain either a large uniform matroid or the cycle matroid of a large fan graph as a minor. We prove that matroids with sufficiently large branchdepth either contain the cycle matroid of a large fan graph as a minor or have large branchwidth. I will discuss this result and some implications.
Joint work with Pascal Gollin, Dillon Mayhew and Sangil Oum.

10 November 2020, 6pm AEDT Vida Dujmović (University of Ottawa) 
Product Structure Theory with applications 
Abstract:
I will talk about product structure theory of graphs and its
application to various problems such as: graph adjacency encoding,
queue/stack number and graph colourings.

27 October 2020, 5pm AEDT Simone Linz (University of Auckland) 
Reconstructing phylogenetic networks from trees 
Abstract:
Recent advances in wholegenome studies provide increasingly strong evidence for a vital role of hybridization in the evolution of certain groups of species and allowing them to adapt to new environments. To represent such complex evolutionary histories as a web of life rather than a simple bifurcating tree of life, phylogenetic (evolutionary) networks have become a popular tool. In the context of reconstructing phylogenetic networks, the problem of characterizing and computing the minimum hybridization number for a set of phylogenetic trees has been investigated by many groups of researchers for the last 15 years. Roughly speaking, this minimum quantifies the number of hybridization events needed to explain a set of trees by simultaneously embedding them in a phylogenetic network. In this talk, we introduce cherrypicking sequences which are particular sequences on the leaves of the trees. We show how these sequences give a novel characterization of the minimum hybridization number for an arbitrarily large collection of phylogenetic trees. This is joint work with Peter Humphries and Charles Semple.

6 October 2020, 11am AEDT Tony Huynh (Monash University) 
Idealness of kwise intersecting families 
Abstract:
A clutter is a hypergraph such that no hyperedge is contained in another hyperedge. It is kwise intersecting if every k hyperedges intersect, but there is no vertex contained in all the hyperedges. We conjecture that every 4wise intersecting clutter is not ideal. Idealness is an important geometric property, which roughly says that the minimum covering problem for the clutter can be efficiently solved by a linear program. As evidence for our conjecture, we prove it for the class of binary clutters. Our proof combines ideas from the theory of clutters, graphs, and matroids. For example, it uses Jaeger's 8flow theorem for graphs, and Seymour's characterization of the binary matroids with the sums of circuits property. We also show that 4 cannot be replaced by 3 in our conjecture, where the counterexample of course comes from the Petersen Graph.
This is joint work with Ahmad Abdi, Gérard Cornuéjols, and Dabeen Lee.

22 September 2020, 5pm AEST David Conlon (Caltech) 
The random algebraic method 
Abstract:
The random algebraic method is a means of constructing examples in extremal combinatorics with some of the best properties of both algebraic constructions and probabilistic ones.
This method has seen a broad array of applications in recent years, some of which we will discuss in this talk.

9 September 2020, 11am AEST Geertrui Van de Voorde (University of Canterbury) 
Sets with few intersection numbers in finite planes 
Abstract:
Many problems in finite geometry follow the following pattern: say we have a set S of points in a plane, and require that a combinatorial property holds (e.g. that the number of points of S on every line is at most a fixed number). Does such a set exist? And if so, can we say something about the algebraic structure of this set? What if we impose some extra symmetry conditions?
By far the most famous example of such a theorem is Segre's beautiful characterisation of conics in a Desarguesian projective plane of odd order q: every oval (which is a set C of q+1 points such that no line contains more than 2 points of C) is the set of points on a conic.
We will look at some classical results about ovals, hyperovals and maximal arcs and present some more recent results of the same flavour about KMarcs (joint work with Maarten De Boeck).

26 August 2020, 11am AEST Tuan Tran (Institute for Basic Science) 
Singularity of random combinatorial matrices 
Abstract:
Let Q_{n} be a random n by n matrix with entries in {0,1} whose rows are independent vectors of exactly n/2 zero components. We show that the probability that Q_{n} is singular is exponentially small, which is optimal up to a multiplicative factor in the exponent.
We develop a general method to handle random matrices with dependent entries.

19 August 2020, 11am AEST Tamás Makai (UNSW Sydney) 
Majority dynamics in the dense binomial random graph 
Abstract:
Majority dynamics is a deterministic process on a graph which evolves in the following manner. Initially every vertex is coloured either red or blue. In each step of the process every vertex adopts the colour of the majority of its neighbours, or retains its colour if no majority exists.
We analyse the behaviour of this process in the dense binomial random graph when the initial colour of every vertex is chosen independently and uniformly at random. We show that with high probability the process reaches complete unanimity, partially proving a conjecture of Benjamini, Chan, O'Donnel, Tamuz and Tan.
This is joint work with N. Fountoulakis and M. Kang.

29 July 2020, 5pm AEST Annika Heckel (LMU Munich) 
Nonconcentration of the chromatic number 
Abstract:
There are many impressive results asserting that the chromatic number of a random graph is sharply concentrated. In 1987, Shamir and Spencer showed that for any function p=p(n), the chromatic number of G(n,p) takes one of at most about n^{1/2} consecutive values whp. For sparse random graphs, much sharper concentration is known to hold: Alon and Krivelevich proved two point concentration whenever p < n^{1/2ε}.
However, until recently no nontrivial lower bounds for the concentration were known for any p, even though the question was raised prominently by Erdős in 1992 and Bollobás in 2004.
In this talk, we show that the chromatic number of G(n,1/2) is not whp contained in any sequence of intervals of length n^{1/2o(1)}, almost matching Shamir and Spencer's upper bound.
Joint work with Oliver Riordan.

22 Jul 2020, 5pm AEST Katherine Staden (University of Oxford) 
Two conjectures of Ringel 
Abstract:
In a graph decomposition problem, the goal is to partition the edge set of a host graph into a given set of pieces. I will focus on the setting where the host graph and the pieces have a comparable number of vertices, and in particular on two conjectures of Ringel from the 60s on decomposing the complete graph: in the first (Ringel's conjecture) they are identical halfsized trees, and in the second (the Oberwolfach problem) they are identical 2factors. I will give some ideas from my recent proofs of the first problem and a generalised version of the second, for large graphs, in joint work with Peter Keevash. The first conjecture was proved independently by Montgomery, Pokrovskiy and Sudakov.

15 Jul 2020, 11am AEST Daniel Horsley (Monash University) 
Generating digraphs with derangements 
Abstract:
Let S be a collection of derangements (fixed pointfree permutations) of a possibly infinite set X. The derangement action digraph DA(X,S) is the digraph on vertex set X that has an arc from x to y if and only if some derangement in S maps x to y. We say that S generates DA(X,S). Derangement action digraphs were introduced by Iradmusa and Praeger in 2019, adapting the definition of a group action digraph due to Annexstein, Baumslag and Rosenberg.
I will discuss recent work by Iradmusa, Praeger and myself in which we characterise, for each positive integer k, the digraphs that can be generated by at most k derangements. Our result resembles the De BruijnErdős theorem in that it characterises a property of an infinite graph in terms of properties of its finite subgraphs.

1 Jul 2020, 5pm AEST Tibor Szabó (Freie Universität Berlin) 
Turán numbers, norm graphs, quasirandomness 
Abstract:
The Turán number of a (hyper)graph H, defined as the maximum number of (hyper)edges in an Hfree (hyper)graph on a given number of vertices, is a fundamental concept of extremal combinatorics. The behaviour of the Turán number is wellunderstood for nonbipartite graphs, but for bipartite H there are more questions than answers. A particularly intriguing halfopen case is the one of complete bipartite graphs.
The projective norm graphs NG(q,t) are algebraically defined graphs which provide tight constructions in the Turán problem for complete bipartite graphs H=K_{t,s} when s>(t–1)!. The K_{t,s}freeness of NG(q,t) is a very much atypical property: in a random graph with the same edge density a positive fraction of ttuples are involved in a copy of K_{t,s}. Yet, projective norm graphs are randomlike in various other senses. Most notably their second eigenvalue is of the order of the square root of
the degree, which, through the Expander Mixing Lemma, implies further quasirandom properties concerning the density of small enough subgraphs. In this talk we explore how far this quasirandomness goes. The main contribution of our proof is the estimation, and sometimes determination, of the number of solutions of certain norm equation system over finite fields.
Joint work with Tomas Bayer, Tamás Mészáros, and Lajos Rónyai.

17 Jun 2020, 5pm AEST Fiona Skerman (Uppsala University) 
Branching processes with merges and locality of hypercube's critical percolation 
Abstract:
We define a branching process to understand the locality or otherwise of the critical percolation in the hypercube; that is, whether the local structure of the hypercube can explain the critical percolation as a function of the dimension of the hypercube.
The branching process mimics the local behaviour of an exploration of a percolated hypercube; it is defined recursively as follows. Start with a single individual in generation 0. On an first stage, each individual has independent Poisson offspring with mean (1+p)(1q)^{k} where k depends on the ancestry of the individual; on the merger stage, each pair of cousins merges with probability q.
We exhibit evidence of a critical merger probability q_{c}=q_{c}(p) for extinction of the branching process. When p is sufficiently small, the first order terms of q_{c} coincide with those of the critical percolation for the hypercube, suggesting that percolation in the hypercube is dictated by its local structure. This is work in progress with Laura Eslava and Sarah Penington.

3 Jun 2020, 4pm AEST John Bamberg (University of Western Australia) 
Vanishing Krein Parameters in Finite Geometry 
Abstract:
The Krein condition on the parameters of a strongly regular graph (L. L. Scott 1973, 1977) is one of the most successful tools in ruling out sets of possible parameters of strongly regular graphs. DelsarteÃ¢â‚¬â„¢s generalisation for association schemes (1973) has also played an important role in the theory of association schemes and its applications: to coding theory, design theory, and finite geometry. In this talk, we give a brief introduction to the interplay between association schemes and finite geometry, and some recent results on vanishing Krein parameters of the speaker and his student Jesse Lansdown.

20 May 2020, 11am AEST Brendan McKay (Australian National University) 
A scientist's adventure into pseudoscience: the strange case of the Bible Codes 
Abstract:
Over the centuries, many claims have been made of numerical patterns of miraculous nature hidden within the text of sacred writings, including the Jewish, Christian and Islamic scriptures. Usually the patterns involve counting of letters and words, or calculations involving numerical equivalents of the letters.
Until recently, all such claims were made by people with little mathematical understanding and were easily explained. This situation changed when a highly respected Israeli mathematician Eliyahu Rips and two others published a paper in the academic journal Statistical Science claiming to prove that information about medieval Jewish rabbis was encoded in the Hebrew text of the Book of Genesis. The journal reported that its reviewers were "baffled".
The paper in Statistical Science spawned a huge "Bible Codes" industry, complete with best selling books, TV documentaries, and even an adventure movie.
The talk will reveal the inside story of the Codes and the people behind them, from their inception through to their refutation. 