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)SpeakerTitle
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 blow-up phenomenon
11 September, 5:00pm Anurag Bishnoi Oddtowns, partial ovoids, and the rank-Ramsey 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^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)
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 high-dimensional 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 n-vertex graph G is a C-expander if |N(X)|≥C|X| 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 C-expander 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 tree-like 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 tree-like 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 blow-up phenomenon
Abstract: We establish a novel connection between the well-known 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 chi-boundedness result for (what we call) ultra maximal K_r-free graphs.
We further show that the graphs under study are blow-ups of constant size graphs, improving a result of Oberkampf and Schacht on homomorphism threshold of cliques. Our result unravels the cause underpinning such a blow-up 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 co-neighborhoods of vertices. More precisely, we show that if an n-vertex K_r-free graph G satisfies that the common neighborhood of every pair of non-adjacent vertices induces a subgraph with K_{r-2}-density at least ε>0, then G must be a blow-up of some K_r-free graph F on at most 2^{O((r/ε)log(1/ε))} vertices. Furthermore, this single exponential bound is optimal. We construct examples with no K_r-free 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 rank-Ramsey 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 2-ovoid 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 rank-Ramsey problem: for a given m, find the largest n for which there exists a triangle-free 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 triangle-free Cayley graph associated with the BCH codes. Moreover, by using a small triangle-free graph associated with a projective cap, we improve the best construction for this rank-Ramsey 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: