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 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:
|