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^2-p^3)n/(1-p+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 Vapnik-Chervonenkis 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 non-experts.
Joint work with Chieu-Minh 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 high-level 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) |
| TBA
|
|
22 May 2024, 5pm AEDT
Mihyun Kang (TU Graz) |
| TBA
|