|
12 March 2025, 11am AEDT
Jeroen Schillewaert (University of Auckland)
|
|
Quasi-polar spaces
|
| Abstract:
Quasi-polar spaces are sets of points having the same intersection numbers with respect to hyperplanes as classical polar spaces. Non-classical examples of quasi-quadrics have been constructed using a technique called pivoting. We introduce a more general notion of pivoting, called switching, and also extend this notion to Hermitian polar spaces.
|
|
9 April 2025, 11am AEDT
Nick Brettel (Victoria University of Wellington)
|
|
Generalisations of Brooks’ Theorem for graphs with connectivity constraints
|
| Abstract:
Brooks' theorem states that a connected graph with maximum degree k is k-colourable provided it is not an odd wheel or a complete graph. Many variants and generalisations of Brooks' theorem appear in the literature; here, I'll focus on such results for graphs that can be described in terms of some connectivity constraint. In particular, a graph G has maximum local edge-connectivity k if the maximum number of edge-disjoint paths between any two distinct vertices of G is k. Stiebitz and Toft (2018) proved a characterisation of the k-colourable graphs with maximum local edge-connectivity k, which can be viewed as a generalisation of Brooks' theorem. In recent joint work with Sam Bastida, we proved a similar result regarding k-choosability for 2-connected graphs in the class, together with a hardness result when the "2-connected" condition is omitted. In this talk I will discuss these results and the broader context for this work.
|
|
30 April 2025, 11am AEDT
Ian Wanless (Monash)
|
|
Subsquares of Latin squares
|
| Abstract:
A Latin square is a matrix in which each row and column is a permutation of the same set of symbols. A subsquare is any submatrix which is itself a Latin square. Every Latin square of order n trivially has n^2 subsquares of order 1 and one subsquare of order n. Any subsquare between these two extremes is proper. Subsquares of order 2 are called intercalates. A Latin square without intercalates is said to be N_2 and a Latin square without proper subsquares is said to be N_\infty.
In this talk I will survey results and open questions relating to the number of subsquares in a Latin square. We might be trying to minimise or maximise this number, or to understand its distribution among all Latin squares of a given order. The existence question for N_2 Latin squares was settled a long time ago, but the corresponding question for N_\infty Latin squares has only recently been settled. There has also been exciting progress on understanding the distribution of subsquares among Latin squares of a given order. But some questions remain.
|
|
7 May 2025, 11am AEDT
Liana Yepremyan (Emory University)
|
|
Long rainbow paths in graphs and digraphs
|
| Abstract:
We study an old question in combinatorial group theory which can be traced back to a problem of Graham from 1971, restated by Erdos and Graham in 1980. Given a group G, and some subset S of G, is it possible to permute S as s1,s2,..., s_d so that the partial products s1, s1 s2, s1 s2 s3, ..., are all distinct? Most of the progress towards this problem has been in the case when G is a cyclic group. We show that for any group G and any subset S of G there is a permutation of S where all but a vanishing proportion of the partial products are distinct, thereby establishing the first asymptotic version of Graham's conjecture under no restrictions on G or S.
To do so, we explore a natural connection between Graham's problem and the following very natural question attributed to Schrijver. Given a d-regular graph G properly edge-coloured with d colours, is it always possible to find a rainbow path with d-1 edges? We settle this question asymptotically by showing one can find a rainbow path of length d-o(d). Certain natural directed analogue of Schrijver's question gives further implications on Graham's conjecture. This is based on joint work with Matija Bucic, Bryce Frederickson, Alp Müyesser and Alexey Pokrovskiy.
|
|
14 May 2025, 11am AEDT
Mikhail Isaev (UNSW)
|
|
Counting Eulerian Orientations
|
| Abstract:
The probability that every vertex in a random orientation of the edges of a given graph has the same in-degree and out-degree is equivalent to counting Eulerian orientations, a problem that is known to be #P-hard in general. This count also appears under the name residual entropy in physical applications, most famously in the study of the behaviour of ice. Using a new tail bound for the cumulant expansion series, we derive an asymptotic formula for graphs of sufficient density. The formula contains the inverse square root of the number of spanning trees, for which we do not have a heuristic explanation. We will also show a strong experimental correlation between the number of spanning trees and the number of Eulerian orientations even for graphs of bounded degree. This leads us to propose a new heuristic for the number of Eulerian orientations which performs much better than previous heuristics for graphs of chemical interest. The talk is based on two recent papers arXiv:2309.15473 and arXiv:2409.04989 joint with B.D.McKay and R.-R. Zhang.
|
|
28 May 2025, 4pm AEDT
António Girão (Oxford)
|
|
Ordered Ramsey numbers
|
| Abstract:
In this talk, I will provide a brief overview of the field of ordered Ramsey theory, whose systematic study began in 2017 in the work of Conlon, Fox, and Sudakov, as well as Balko, Cibulka, Král, and Kynčl. Interestingly, these numbers are closely connected to classical results in combinatorics, such as the Erdős–Szekeres theorem on monotone subsequences. I will also give a proof sketch of two recent results which answer two questions of Gishboliner, Jin and, Sudakov and Balko, Cibulka, Král, and Kynčl.
|
|
5 August 2025, 11am AEST
Stephen Glasby (UWA)
|
|
Counting the number of tournaments and "even" graphs
|
| Abstract:
In 2020, Pontus von Brömssen conjectured that the number of tournaments on n vertices equals the number of "even" graphs on n vertices. In 2022 a team of five of us proved the conjecture using elementary counting techniques and group theory.
|
|
19 August 2025, 11am AEST
Hao Huang (National University of Singapore)
|
|
A d-degree generalization of the Erdős-Ko-Rado Theorem
|
| Abstract:
Perhaps the most well-known theorem in extremal combinatorics, the Erdős-Ko-Rado (EKR) Theorem asserts that for n>=2k, an intersecting family of k-subsets of {1, ..., n} contains at most n-1 \choose k-1 sets. In 2017, Yi Zhao and I established a degree version of the EKR Theorem. In this talk, I will present a further generalization of these results to the setting of minimum d-degree, improving a result of Kupavskii. This is a joint work with Yi Zhang (BUPT).
|