Welcome! The CMSA seminar aims to bring together combinatorialists of Australasia and the world. It started during the COVID-19 lockdown days, and may continue afterwards. We plan to hold the seminar roughly every two weeks on Tuesday, during spring and autumn.

We will mainly be using one of the following two time slots, conversion to your time zone is available via the links:
11am Sydney time (AEDT/AEST) or 5pm Sydney time (AEDT/AEST) .

Subscribe: In order to subscribe mail daniel.horsley@monash.edu and ask to be added to the list. We send announcements and zoom details before every talk.

Organisers: Daniel Horsley and Binzhou Xia. Please email us with your feedback and suggestions.

Previous talks: 2020 2021 2022

Youtube playlist containing some past talks can be found here.

2023 talks:
Date (NSW/Vic)SpeakerTitle Video
14 Mar, 11:00am Jinyoung Park Thresholds
28 Mar, 5:00pm Catherine Greenhill Triangle switches, reconstruction and mixing
18 Apr, 11:00am Yoshiharu Kohayakawa Some problems and results on order types
2 May, 11:00am Michael Giudici 2-closed groups and automorphism groups of digraphs
16 May, 6:00pm Andrew Treglown The induced saturation problem for posets
30 May, 11:00am Karen Meagher Intersection theorems for uniform partitions
1 Aug, 11:00am Jessica McDonald On flows (and group-connectivity) in signed graphs
15 Aug, 11:00am Melissa Lee Computing with the monster and maximal subgroups
29 Aug, 5:00pm Mathias Schacht Canonical colourings in random graphs
12 Sep, 5:00pm Florian Lehner Tree structure, formal languages, and self-avoiding walks
3 Oct, 6:00pm Marcelo Campos An exponential improvement for diagonal Ramsey
17 Oct, 11:00am Anita Liebenau Universality for graphs of bounded degeneracy

17 October 2023, 11am AEDT Anita Liebenau (UNSW)
Universality for graphs of bounded degeneracy
Abstract: What is the smallest number of edges that a graph G can have if it contains all D-degenerate graphs on n vertices as subgraphs? A counting argument shows that this number is at least of order n^{2−1/D}, assuming n is large enough. We show that this is tight up to a polylogarithmic factor. Joint with Peter Allen and Julia Böttcher.

3 October 2023, 6pm AEDT Marcelo Campos (University of Oxford)
An exponential improvement for diagonal Ramsey
Abstract: The Ramsey number R(k) is the minimum n such that every red-blue colouring of the edges of the complete graph K_n on n vertices contains a monochromatic copy of K_k. We prove that R(k) ≤ (3.99)^k. This is the first exponential improvement over the upper bound of Erdős and Szekeres, proved in 1935. This is joint work with Simon Griffiths, Robert Morris, Julian Sahasrabudhe.

12 September 2023, 5pm AEDT Florian Lehner (University of Auckland)
Tree structure, formal languages, and self-avoiding walks
Abstract: A self-avoiding walk (SAW) in an infinite graph is a walk which visits no vertex more than once. Determining the number of SAWs of a given length starting at some fixed vertex is a notoriously difficult problem. For instance, even the exponential growth rate of the number of SAWs is only known in a small number of special cases. In this talk, we discuss a connection between formal languages and walks on edge-labelled graphs. This allows us to study SAWs on Cayley graphs of virtually free groups and various other graphs with a large-scale tree structure via (a generalisation of) context-free languages. This talk is based on joint work with Lindorfer.

29 August 2023, 5pm AEDT Mathias Schacht (University of Hamburg)
Canonical colourings in random graphs
Abstract: Rödl and Ruciński established Ramsey's theorem for random graphs. In particular, for fixed integers r, k ≥ 2 they showed that n^{-2/(k+1)} is a threshold for the Ramsey property that every r-colouring of the edges of the binomial random graph G(n,p) yields a monochromatic copy of K_k. We investigate how this result extends to arbitrary colourings of G(n,p) with an unbounded number of colours. In this situation Erdős and Rado showed that canonically coloured copies of K_k can be ensured in the deterministic setting. We transfer the Erdős-Rado theorem to the random environment and show that for k ≥ 4 both thresholds coincide. As a consequence the proof yields K_{k+1}-free graphs G for which every edge colouring yields a canonically coloured K_k. This is joint work with Nina Kamčev

15 August 2023, 11am AEDT Melissa Lee (Monash University)
Computing with the monster and maximal subgroups
Abstract: The monster group is the largest of the 26 sporadic simple groups with order approximately 8 x 10^53. Apart from its extremely large order, one of the challenges of computing with the monster is that it does not have a small matrix or permutation representation. In this talk, I will discuss the history of computing with the monster, some recent breakthroughs in this area, and some joint work on maximal subgroups with Heiko Dietrich and Tomasz Popiel.

1 August 2023, 11am AEDT Jessica McDonald (Auburn University)
On flows (and group-connectivity) in signed graphs
Abstract: In this talk we'll start by discussing flows in signed graphs and how it generalizes the usual notion of integer flows in graphs. In particular, flow-colouring duality of graphs in the plane can be re-interpreted using signed graphs in the projective plane. Also, where a flow in a graph can be viewed as a sum of flows on cycles, in a signed graph, positive cycles and barbells are the key structures to consider. We'll share a new result, joint with K. Nurse and A. Brewer-Castano, about flows in 3-edge-connected signed graphs. In fact, this result holds for the stronger notion of group-connectivity, which was introduced as a generalization of flows by Jaeger, Linial, Payan, and Tarsi in 1992. Building on their work and also on work by Li, Luo, Ma and Zhang (2018), we (mostly) establish a group-connected analog of Seymour's 6-flow Theorem for signed graphs.

30 May 2023, 11am AEDT Karen Meagher (University of Regina)
Intersection theorems for uniform partitions
Abstract: Recently there have been many results giving variations of the Erdos-Ko-Rado (EKR) theorem for different objects. These theorems typically describe the largest set of intersecting objects, and focus on when the largest set is the collection of all objects that intersect in the same place. In this talk I will focus on EKR-theorems for uniform partitions. A uniform (k,ℓ)-partition is a partition of {1,...,kℓ} with ℓ sets, each of size k. Since a partition is a set of sets, it is natural to say two uniform (k,ℓ)-partitions are intersecting if they contain a common set. In particular, partitions P = {P_1,P_2,...,P_ℓ} and Q= {Q_1,Q_2,...,Q_ℓ} are intersecting if P_i = Q_j for some i and j. In many cases a simple counting argument shows that the largest set of intersecting uniform partitions is the one with all partitions containing a common k-set. There is another type of intersection that can be considered for uniform partitions. Two partitions P = {P_1,P_2,...,P_ℓ} and Q= {Q_1,Q_2,...,Q_ℓ} are partially t-intersecting if there exist sets |P_i \cap Q_j| \geq t. If k=t, this definition is the same as intersecting, and for t=1, any two partitions are 1-partially intersecting. In this talk, I will consider 2-partially intersecting uniform partitions. If ℓ is large, relative to k, using an arguments from algebraic graph theory, it can be shown that the largest set of partially 2-intersecting partitions is the set of all partitions that contain a part with a common pair. This proof method has been used for many variations of the EKR theorem. In this method, the first step is to build a graph in which the cocliques (independent sets) correspond to intersecting sets of partitions. The next step is to find the largest and smallest eigenvalues of the graph. Finally the size of the cocliques is bounded using these two eigenvalues. This is joint work with Chris Godsil, Lucia Moura, Mahsa Shirazi and Brett Stevens.

16 May 2023, 6pm AEDT Andrew Treglown (University of Birmingham)
The induced saturation problem for posets
Abstract: For a fixed poset P, a family F of subsets of [n] is induced P-saturated if F does not contain an induced copy of P, but for every subset S of [n] not in F, adding S to F results in an induced copy of P. The problem of determining the size of the smallest induced P-saturated family of subsets of [n] has received significant attention recently. After giving a gentle introduction to the topic, I will describe a recent general bound on this problem. Our proof makes use of a Turán-type result for digraphs. This is joint work with Andrea Freschi, Simón Piga and Maryam Sharifzadeh.

2 May 2023, 11am AEDT Michael Giudici (University of Western Australia)
2-closed groups and automorphism groups of digraphs
Abstract: Wielandt introduced the notion of the 2-closure of a permutation group $G$ on a set $\Omega$. This is the largest subgroup of $\mathrm{Sym}(\Omega)$ with the same set of orbits on ordered pairs as $G$. We say that $G$ is 2-closed if $G$ is equal to its 2-closure. The automorphism group of a graph or digraph is a 2-closed group and so is any regular permuation group. The famous DRR problem was to determine which regular groups are not the automorphism group of some digraph and this was settled by Babai in 1980 by showing that there are only 5 such groups. Until recently these were the only known examples of 2-closed groups that are not the automorphism group of some digraph. In this talk I will discuss some recent work with Luke Morgan and Jin-Xin Zhou on other families of 2-closed groups that are not the automorphism group of a graph or digraph.

18 April 2023, 11am AEDT Yoshiharu Kohayakawa (University of São Paulo)
Some problems and results on order types
Abstract: A configuration is a finite set of points on the plane. Two configurations A and B have the same order type if there exists a bijection between them preserving the orientation of every ordered triple. We investigate extremal, probabilistic and property testing problems related to configurations in general position. We focus on problems involving forbidden configurations. Thus, we typically have a given configuration B and we consider the property of being "B-free": a configuration A is B-free if no subset of points of A has the same order type as B. We shall discuss some results obtained in joint work with J. Han, M. T. Sales and H. Stagni.

28 March 2023, 5pm AEDT Catherine Greenhill (UNSW Sydney)
Triangle switches, reconstruction and mixing
Abstract: In a uniformly random graph with a given degree sequence, if the maximum degree is constant then the number of triangles in the graph is asymptotically Poisson with constant mean. In particular, this implies that a uniformly random graph is not well-suited as a model for a network which contains many triangles, such as a social network. The switch chain is a well-studied Markov chain on the set of all graphs with given degrees, with a uniform stationary distribution. I will discuss variations of the switch chain, called triangle switch chains, which only perform switches that change the set of triangles in the graph. We have proved that triangle switches connect the state space of graphs with a given degree sequence, whenever the minimum degree is at least 3. We have also studied the mixing rate of a Metropolis implementation of the switch chain, in which a graph $G$ has stationary distribution proportional to $\lambda^{t(G)}$ for some $\lambda > 1$, where $t(G)$ is the number of triangles in $G$. Such a chain could be used to sample graphs with many more triangles than expected in a uniformly random graph with the same degree sequence. We have proved that this Metropolis triangle switch chain is rapidly mixing whenever the corresponding switch chain is rapidly mixing, so long as $\lambda$ and the maximum degree of the chain are not too large. Joint work with Colin Cooper and Martin Dyer.

14 March 2023, 11am AEDT Jinyoung Park (New York University)
Thresholds
Abstract: For a finite set X, a family F of subsets of X is said to be increasing if any set A that contains B in F is also in F. The p-biased product measure of F increases as p increases from 0 to 1, and often exhibits a drastic change around a specific value, which is called a "threshold." Thresholds of increasing families have been of great historical interest and a central focus of the study of random discrete structures (e.g. random graphs and hypergraphs), with estimation of thresholds for specific properties the subject of some of the most challenging work in the area. In 2006, Jeff Kahn and Gil Kalai conjectured that a natural (and often easy to calculate) lower bound q(F) (which we refer to as the “expectation-threshold”) for the threshold is in fact never far from its actual value. A positive answer to this conjecture enables one to narrow down the location of thresholds for any increasing properties in a tiny window. In particular, this easily implies several previously very difficult results in probabilistic combinatorics such as thresholds for perfect hypergraph matchings (Johansson–Kahn–Vu) and bounded-degree spanning trees (Montgomery). In this talk, I will present recent progress on this topic. Based on joint work with Keith Frankston, Jeff Kahn, Bhargav Narayanan, and Huy Tuan Pham.