|
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).
|
|
2 September 2025, 5pm AEST
Natalie Behague (University of Warwick)
|
|
Colour-biased Hamilton cycles in subgraphs of the random graph
|
| Abstract:
Dirac's Theorem says that every n-vertex graph with minimum degree at least n/2 contains a Hamilton cycle. Lee and Sudakov extended Dirac's theorem to the setting of random graphs, showing that a random graph (above the threshold to contain a Hamilton cycle) typically has the property that every spanning subgraph with minimum degree at least (1/2 +o(1))np contains a Hamilton cycle.
In a different direction, we can ask for a discrepancy version of Dirac's theorem. In this setting, the edges of the graph G are coloured with r colours and we want to know whether there necessarily exists a colour-biased Hamilton cycle where some colour is used (a lot) more than n/r times. Heuristically, this implies there must be many intersecting Hamilton cycles. If G has minimum degree at least (1/2 + 1/2r + o(1))n then such a result holds.
This talk concerns a combination of the above lines of research to give a discrepancy Dirac-type result in the random graph. I will finish with a brief discussion of some generalisations and related problems.
This is joint work with Debsoumya Chakraborti and Jared Leon.
|
|
16 September 2025, 5pm AEST
Simona Boyadzhiyska (Alfréd Rényi Institute)
|
|
Almost-perfect colorful matchings in three-edge-colored bipartite graphs
|
| Abstract:
The well-known Ryser-Brualdi-Stein Conjecture states that any proper edge-coloring of the complete bipartite graph K_{n,n} contains a rainbow matching of size n-1. In this talk, we will discuss a multiplicity extension of this conjecture, proposed recently by Anastos, Fabian, Müyesser, and Szabó, and prove a special case of it. More precisely, we will show that, for all positive integers n,a_1, a_2, a_3 satisfying a_1+a_2+a_3 = n-1, every bipartite graph on 2n vertices that is the union of three perfect matchings M_1, M_2, and M_3 contains a matching M such that |M ∩ M_i| =a_i for i ∈ {1,2,3}.
This is joint work with Micha Christoph and Tibor Szabó.
|
|
7 October 2025, 5pm AEDT
Alberto Espuny Díaz (University of Barcelona)
|
|
Building structures in the budget-constrained random graph process
|
| Abstract:
We consider a version of the random graph process where, starting with the empty graph on n vertices, a player called Builder is iteratively offered uniformly random edges. Each time an edge is offered, Builder must immediately decide whether to ‘purchase’ this edge (and add it to the graph) or let it go forever. Builder's goal is to end up with a graph which satisfies some desired property, but there are two constraints: a maximum number of steps t for which the process will run, and a budget b which bounds the total number of edges that Builder is allowed to purchase. With these constraints, when can Builder reach their goal with high probability?
In this talk, I will present this budget-constrained random graph process, which was recently introduced by Frieze, Krivelevich and Michaeli, and survey the results in the area. I will later present some new results, involving both spanning and small structures, and discuss some of the ideas that go into their proofs.
This is based on joint works with Frederik Garbe, Tássio Naia and Zak Smith, and with Sylwia Antoniuk, Kalina Petrova and Miloš Stojaković.
|
|
21 October 2025, 5pm AEDT
Gábor Somlai (Eötvös Loránd University)
|
|
New polynomial method to treat versions of the direction problem
|
| Abstract:
Rédei proved that a set of p points in AG(2,p) is either a line or determines at least (p+3)/2 directions. The old treatment of this theorem uses Rédei’s polynomials and lacunary polynomials. We introduced the notion of projection polynomial which is more of Fourier analytic flavour. This allowed us to give a short proof of Rédei’s result which also revealed a strange connection between Rédei’s theorem and the cylindrical set conjecture. Furthermore we reproved a result of Lovász and Schrijver on the uniqueness of sets determining exactly (p+3)/2 directions. I also plan to talk about a generalisation of the direction problem for sets of size kp and describe sets with few directions.
|