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 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)  Speaker  Title  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  2closed 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 groupconnectivity) 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 selfavoiding 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 Ddegenerate 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 redblue 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 selfavoiding walks

Abstract:
A selfavoiding 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 edgelabelled graphs. This allows us to study SAWs on Cayley graphs of virtually free groups and various other graphs with a largescale tree structure via (a generalisation of) contextfree 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 rcolouring 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ősRado 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 groupconnectivity) 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, flowcolouring duality of graphs in the plane can be reinterpreted 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. BrewerCastano, about flows in 3edgeconnected signed graphs. In fact, this result holds for the stronger notion of groupconnectivity, 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 groupconnected analog of Seymour's 6flow 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 ErdosKoRado (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 EKRtheorems 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 kset.
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 tintersecting 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 1partially intersecting. In this talk, I will consider 2partially 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 2intersecting 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 Psaturated 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 Psaturated 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ántype 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) 
2closed groups and automorphism groups of digraphs

Abstract:
Wielandt introduced the notion of the 2closure 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 2closed if $G$ is equal to its 2closure. The automorphism group of a graph or digraph is a 2closed 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 2closed groups that are not the automorphism group of some digraph. In this talk I will discuss some recent work with Luke Morgan and JinXin Zhou on other families of 2closed 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 "Bfree": a configuration A is Bfree 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 wellsuited as a model for a network which contains many triangles, such as a social network.
The switch chain is a wellstudied 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 pbiased 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 “expectationthreshold”) 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 boundeddegree 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.
