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:
Time (NSW/Vic)  Speaker  Title 
6 Mar, 11:00am

Huy Tuan Pham 
Random Cayley graphs and Additive combinatorics without groups

20 Mar, 11:00am

Ahad Zehmakan 
Random Majority Opinion Diffusion: Stabilization Time, Absorbing States, and Influential Nodes

10 Apr, 11:00am

Abdul Basit 
On the shatter function of semilinear set systems

24 Apr, 10:00am
(note different time)

Rose McCarty 
Prime distances in colorings of the plane

8 May, 5:00pm

Valentina Pepe 
On some finite geometry structures related to extremal graphs

22 May, 5:00pm

Mihyun Kang 
Supercritical percolation and isoperimetric inequalities

31 July, 5:00pm

Nemanja Draganić 
Hamiltonicity in Expanders

14 August, 12:30pm
(note different time)

David Wood 
Graph Product Structure: Theory and Applications

28 August, 11:00am

Hong Liu 
Beyond chromatic threshold via the (p,q)theorem, and a sharp blowup phenomenon

11 September, 5:00pm

Anurag Bishnoi 
Oddtowns, partial ovoids, and the rankRamsey problem

25 September, 5:00pm

Kalina Petrova 
TBA

9 October, 11:00am

Barbara Maenhaut 
TBA

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.

31 July 2024, 5pm AEDT
Nemanja Draganić (Oxford) 
Hamiltonicity in Expanders

Abstract:
An nvertex graph G is a Cexpander if N(X)≥CX for every X ⊆ V(G) with X< n/2C
and there is an edge between every two disjoint sets of at least n/2C vertices. We show that there is some constant C > 0 for which every Cexpander is Hamiltonian.
In particular, this implies the well known conjecture of Krivelevich and Sudakov from 2003 on Hamilton cycles in (n,d,λ)graphs. This completes a long line of research on the Hamiltonicity of sparse graphs, and has many applications. If time permits, we will discuss upcoming related work, and open questions in the area.
Joint with R. Montgomery, D. Munhá Correia, A. Pokrovskiy and B. Sudakov

14 August 2024, 12:30pm AEDT
David Wood (Monash) 
Graph Product Structure: Theory and Applications

Abstract:
Graph product structure theory describes graphs in
complicated classes as subgraphs of products of much simpler treelike
graphs. There has been an explosion of interest in this field since
2019, when the speaker and his colleagues proved that every planar
graph is contained in the product of a treelike graph and a path.
This result opened up a new research direction, and has been the key
tool in solving a number of longstanding open problems. This talk will
introduce graph product structure theory, describing the main results
and several of the applications.

28 August 2024, 11:00am AEDT
Hong Liu (IBS South Korea) 
Beyond chromatic threshold via the (p,q)theorem, and a sharp blowup phenomenon

Abstract:
We establish a novel connection between the wellknown chromatic threshold problem in extremal combinatorics and the celebrated (p,q)theorem in discrete geometry. In particular, for a graph G with bounded clique number and a natural density condition, we prove a (p,q)theorem for an abstract convexity space associated with G. Our result strengthens those of Thomassen and Nikiforov on the chromatic threshold of cliques. Our (p,q)theorem can also be viewed as a chiboundedness result for (what we call) ultra maximal K_rfree graphs.
We further show that the graphs under study are blowups of constant size graphs, improving a result of Oberkampf and Schacht on homomorphism threshold of cliques. Our result unravels the cause underpinning such a blowup phenomenon, differentiating the chromatic and homomorphism threshold problems for cliques. It implies that for the homomorphism threshold problem, rather than the minimum degree condition usually considered in the literature, the decisive factor is a clique density condition on coneighborhoods of vertices. More precisely, we show that if an nvertex K_rfree graph G satisfies that the common neighborhood of every pair of nonadjacent vertices induces a subgraph with K_{r2}density at least ε>0, then G must be a blowup of some K_rfree graph F on at most 2^{O((r/ε)log(1/ε))} vertices. Furthermore, this single exponential bound is optimal. We construct examples with no K_rfree homomorphic image of size smaller than 2^{Ω_r(1/ε)}.
This is joint work with Chong Shangguan, Jozef Skokan, Zixiang Xu.

11 September 2024, 5:00am AEDT
Anurag Bishnoi (TU Delft) 
Oddtowns, partial ovoids, and the rankRamsey problem

Abstract:
What is the largest size of a family of subsets of {1, ..., m} such that every set in the family has odd cardinality and among any three distinct sets there is at least one pair that intersects in an even number of elements? We'll show that this generalisation of the classic Oddtown problem is equivalent to finding the largest size of a partial 2ovoid in a binary symplectic space and that of finding the largest set of nearly orthogonal vectors in F_2^m. Moreover, we show that it's intimately linked to the following rankRamsey problem: for a given m, find the largest n for which there exists a trianglefree graph whose adjacency matrix satisfies rank(A+I) <= m. If we consider the rank over the binary field, then the problem is equivalent to the previous problems.
We give new constructions, improving the state of art, using a trianglefree Cayley graph associated with the BCH codes. Moreover, by using a small trianglefree graph associated with a projective cap, we improve the best construction for this rankRamsey problem over the reals.
Joint work with John Bamberg and Ferdinand Ihringer.

25 September, 5:00pm AEDT
Kalina Petrova (IST Austria) 

Abstract:

9 October 2024, 11:00am AEDT
Barbara Maenhaut (University of Queensland) 

Abstract:
