Welcome! The CMSA seminar aims to bring together combinatorialists from Australasia and around the world.
The seminar is held roughly every two weeks during spring and autumn, usually at either 11am or 5pm AEDT.
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 Rajko Nenadov.
Please email us with your feedback and suggestions.
Previous talks:
2020
2021
2022
2023
2024 talks:
6 March 2024, 11am AEDT
Huy Tuan Pham (Stanford University)

Random Cayley graphs and Additive combinatorics without groups

Abstract:
Cayley graphs provide interesting bridges between graph theory, additive combinatorics and group theory. Motivated by considerations in Ramsey theory, we study random Cayley graphs, which are constructed by fixing a finite group and choosing a generating set at random. These graphs reflect interesting symmetries and properties of the group, at the cost of inducing complex dependencies. I will discuss results on clique and independence numbers of random Cayley graphs of general groups, a proof of a conjecture of Alon and Orlitsky, as well as progress towards a conjecture of Alon on existence of Ramsey Cayley graphs in arbitrary groups. These questions are naturally connected with some fundamental problems in additive combinatorics. Surprisingly, our insights suggest that in many of these problems the group structure is superfluous and can be replaced by much more general combinatorial structures. In particular, this leads to some interesting combinatorial generalizations of important structural results in additive combinatorics. Based on joint work with David Conlon, Jacob Fox and Liana Yepremyan.

20 March 2024, 11am AEDT
Ahad Zehmakan (ANU) 
Random Majority Opinion Diffusion: Stabilization Time, Absorbing States, and Influential Nodes

Abstract:
Consider a graph G with n nodes and m edges, and assume that initially each node is blue or white. In each round, all nodes simultaneously update their color to the most frequent color in their neighborhood. This is called the Majority Model (MM) if a node keeps its color in case of a tie and the Random Majority Model (RMM) if it chooses blue with probability 1/2 and white otherwise.
We prove that there are graphs for which RMM needs exponentially many rounds to reach a stable configuration in expectation, and such a configuration can have exponentially many states (i.e., colorings). This is in contrast to MM, which is known to always reach a stable configuration with one or two states in o(m) rounds.
We also study the minimum size of a winning set, which is a set of nodes whose agreement on a color in the initial coloring enforces the process to end in a coloring where all nodes share that color. We present tight bounds on the minimum size of a winning set for both MM and RMM.
Furthermore, we analyze our models for a random initial coloring, where each node is colored blue independently with some probability p and white otherwise. We prove that the expected final number of blue nodes is equivalent to (2p^2p^3)n/(1p+p^2) and pn in MM and RMM on a cycle graph C_n.

10 April 2024, 11am AEDT
Abdul Basit (Monash University) 
On the shatter function of semilinear set systems

Abstract:
The shatter function of a family of sets (referred to as a set system) is an important measure of its combinatorial complexity. For example, it is related to the popular notion of VapnikChervonenkis dimension. We will consider the shatter functions of geometric set systems, where it is conjectured that the shatter function must have simple behavior. We verify this conjecture for set systems which can be defined by systems of linear equalities and inequalities. We will also discuss connections of these results to combinatorial geometry and model theory. No background is assumed, and the talk will be accessible to nonexperts.
Joint work with ChieuMinh Tran.

24 April 2024, 10am AEDT
Rose McCarty (Georgia Tech) 
Prime distances in colorings of the plane

Abstract:
We prove that in any coloring of the plane with finitely many colors, there exist two points of the same color so that the distance between them is a prime number. Our approach is based on a breakthrough result of Davies which solved the odd distance problem. In this talk, we give a highlevel overview of the approach. As we will discuss in the talk, the key idea is to apply a spectral bound for infinite Cayley graphs, and to estimate the eigenvalues by approximating sums with integrals. This is joint work with James Davies and Michał Pilipczuk.

8 May 2024, 5pm AEDT
Valentina Pepe (Sapienza University of Rome) 
On some finite geometry structures related to extremal graphs

Abstract:
The aim of this talk is to enlighten the “geometric” picture behind some extremal graphs: this can be fascinating itself and it can also suggest new ways to tackle the problems. Some new constructions will be presented.

22 May 2024, 5pm AEDT
Mihyun Kang (TU Graz) 
Supercritical percolation and isoperimetric inequalities

Abstract:
In their seminal paper Erdős and Rényi discovered that a random graph undergoes phase transitions. For example, typically all the components are at most of logarithmic order when the average degree is smaller than one, while there is a unique giant component of linear order when the average degree is larger than one. Ajtai, Komlós and Szemerédi showed that a random subgraph obtained by bond percolation on the hypercube undergoes a similar phase transition. In this talk we will briefly overview these classical results and discuss recent results on typical properties of the giant component in random subgraphs of highdimensional product graphs and isoperimetric inequalities. This talk is based on joint work with Sahar Diskin, Joshua Erde, and Michael Krivelevich.
