Welcome! The CMSA seminar aims to bring together combinatorialists of Australasia and the world.
It started during the COVID-19 lockdown days, and may continue afterwards.
We plan to hold the seminar roughly every two weeks on Tuesday, during spring and autumn.
29 November 2022, 5pm AEDT Michel Lavrauw (Sabancı University)
Combinatorial and geometric aspects of projective group actions arising from algebraic varieties
Abstract:
In combinatorics and finite geometry, the study of various actions of (subgroups of) the classical groups has often led to new constructions of interesting (rare) geometric objects. It is an essential feature of the interplay between groups and geometry. A well-known example, due to Jacques Tits from 1962, is the action of the Suzuki group on the points of a 3-dimensional projective space, giving rise to an ovoid (a notion introduced by Beniamino Segre): a set of points which has the same combinatorial and geometric properties as (but inequivalent to) an elliptic quadric. Since then, this idea has matured, and the availability of computer algebra systems has greatly contributed to recent developments; there are many authors who have used so-called “orbit-stitching” to obtain new constructions of desirable geometries. In this talk we will focus on the action of the projective stabiliser of (classical) algebraic varieties. The complete classification of the orbits on subspaces under these actions is a challenging task, and few classifications are complete. After a general introduction including some recent results and open problems, we will focus on a particular action of PGL(2,q) arising from a maximal rational curve embedded on a smooth Hermitian surface with some fascinating properties. The study of its orbits leads, via orbit-stitching, to a new construction of a quasi-Hermitian surface: a set of points with the same combinatorial and geometric properties as a non-degenerate Hermitian surface.
15 November 2022, 5pm AEDT Krystal Guo (Korteweg-de Vries Institute for Mathematics, University of Amsterdam)
Strongly regular graphs with a regular point
Abstract:
Arising from Hoffman and Singleton's study of Moore graphs, strongly regular graphs play an important role in algebraic graph theory. Strongly regular graphs can be constructed from geometric objects, such as generalized quadrangles and certain geometric properties, such as having a regular point, can be studied in the context of graphs. We study pseudo-geometric strongly regular graphs whose second subconstituent with respect to a vertex is a cover of a strongly regular graph or a complete graph. By studying the structure of such graphs, we characterize all graphs containing such a vertex, thereby, answering a question posed by Gardiner, Godsil, Hensel, and Royle. As a by-product of our characterisation, we are able to give new constructions of infinite families of strongly regular graphs and compute many small sporadic examples, in particular, we find 135 478 new strongly regular graphs with parameters (85,20,3,5) and 27 039 strongly regular graphs with parameters (156, 30, 4, 6).
1 November 2022, 11am AEDT Dillon Mayhew (Victoria University of Wellington)
Infinite groups and definable classes of matroids
Abstract:
Matroids are abstract objects that generalise finite collections of vectors. The first part of this talk will consist of a gentle introduction to matroids. Any matroid that arises from a finite collection of vectors is said to be representable, and understanding classes of representable matroids has been an important goal of matroid theory.
If a matroid is representable, then roughly speaking its elements can be given coordinates from a field. Another class of matroids arises when elements are given coordinates from a group. Such a class is said to be gain-graphic.
Monadic second-order logic is a formal language that we can use to express properties of matroids. Any property that can be expressed in this language is said to be definable. There are strong connections between definability in monadic logic and the theory of computation, as exemplified by Courcelle’s Theorem, which states that any graph property that can be expressed in the monadic second-order logic of graphs can be tested in polynomial-time, when the input is restricted to classes of graphs with bounded tree-width. This means that (usually NP-hard) properties such as Hamiltonicity can be tested quickly for classes of bounded tree-width. Matroid analogues of Courcelle’s Theorem have been proved by Hlineny, and also by Funk, Mayhew, Newman, and Whittle.
This gives us the incentive to understand which properties of matroids can be defined in monadic second-order logic. When applied to the class of gain-graphic matroids, this leads to a surprising, and apparently very hard, problem for infinite groups.
18 October 2022, 6pm AEDT Shoham Letzter (University College London)
Turán densities of tight cycles
Abstract:
The Turán density of an r-uniform hypergraph H, denoted \pi(H), is the limit of the maximum density of an n-vertex r-uniform hypergraph not containing a copy of H, as n approaches infinity.
Denote by C_k the 3-uniform tight cycle on k vertices. Mubayi and Rödl (2002) gave an 'iterated blow-up' construction showing that the Turán density of C_5 is at least 2\sqrt{3} - 3 \approx 0.464, and this bound is conjectured to be tight.
Their construction also does not contain C_k for larger k not divisible by 3, which suggests that it might be the extremal construction for these hypergraphs as well. We show that, for large k not divisible by 3, the Turán density of C_k is, indeed, 2\sqrt{3}-3.
4 October 2022, 5pm AEDT Alice Devillers (University of Western Australia)
J-groups
Abstract:
At the 2018 annual research retreat of the Centre for the Mathematics of Symmetry and Computation (UWA), visitor Tim Boykett introduced a peculiar group condition in the form of a functional equation:
We say a group G is a J-group if there exists an element k (called witness) and a function f from G to G such that f(xk)=xf(x) for all x in G.
I will explain what we found out about this property and the set of witnesses, as well as the twists and turns that led from the retreat to the publication of our results in 2022. In particular, we will be interested in the question of which p-groups are J-groups.
This is joint work with Dominik Bernhardt, Tim Boykett, Johannes Flake, Stephen Glasby.
20 September 2022, 5pm AEDT Candida Bowtell (University of Birmingham)
The n-queens problem
Abstract:
The n-queens problem asks how many ways there are to place n queens on an n x n chessboard so that no two queens can attack one another, and the toroidal n-queens problem asks the same question where the board is considered on the surface of a torus. Let Q(n) denote the number of n-queens configurations on the classical board and T(n) the number of toroidal n-queens configurations. The toroidal problem was first studied in 1918 by Pólya who showed that T(n)>0 if and only if n is not divisible by 2 or 3. Much more recently Luria showed that T(n) is at most ((1+o(1))ne^{-3})^n and conjectured equality when n is not divisible by 2 or 3. We prove this conjecture, prior to which no non-trivial lower bounds were known to hold for all (sufficiently large) n not divisible by 2 or 3. We also show that Q(n) is at least ((1+o(1))ne^{-3})^n for all natural numbers n which was independently proved by Luria and Simkin and, combined with our toroidal result, completely settles a conjecture of Rivin, Vardi and Zimmerman regarding both Q(n) and T(n).
In this talk we'll discuss our methods used to prove these results. A crucial element of this is translating the problem to one of counting matchings in a 4-partite 4-uniform hypergraph. Our strategy combines a random greedy algorithm to count `almost' configurations with a complex absorbing strategy that uses ideas from the methods of randomised algebraic construction and iterative absorption.
This is joint work with Peter Keevash.
12 April 2022, 11am AEDT Jane Gao (University of Waterloo)
Perfect matchings and sandwich conjectures of random regular graphs
Abstract:
In the first half of the talk I will survey results on the limiting distributions of small and large subgraphs of random regular graphs, and present a recent result on the limiting distribution of the number of perfect matchings.
In the second half of the talk, I will talk about the Kim-Vu sandwich conjecture of random regular graphs, recent progress, and new results.
29 March 2022, 5pm AEDT Letícia Mattos (Freie Universität Berlin)
Clique packings in random graphs
Abstract:
Let u(n,p,k) be the k-clique packing number of the random graph G(n,p), that is, the maximum number of edge-disjoint k-cliques in G(n,p). In 1992, Alon and Spencer conjectured that for p = 1/2 we have u(n,p,k) = Ω(n²/k²) when k = k(n,p) - 4, where k(n,p) is minimum t such that the expected number of t-cliques in G(n,p) is less than 1. This conjecture was disproved a few years ago by Acan and Kahn, who showed that in fact u(n,p,k) = O(n²/k³) with high probability, for any fixed p∈(0,1) and k = k(n,p) - O(1).
In this talk, we show a lower bound which matches Acan and Kahn's upper bound on u(n,p,k) for all p∈(0,1) and k = k(n,p) - O(1). To prove this result, we follow a random greedy process and use the differential equation method. This is a joint work with Simon Griffiths and Rob Morris.
15 March 2022, 5pm AEDT Binzhou Xia (University of Melbourne)
Digraphs with non-diagonalizable adjacency matrix
Abstract:
The fact that the adjacency matrix of every finite graph is diagonalizable plays a fundamental role in spectral graph theory. Since this fact does not hold in general for digraphs, it is natural to ask whether it holds for digraphs with certain level of symmetry. Interest on this question dates back to early 1980s, when P. J. Cameron asked for the existence of arc-transitive digraphs with non-diagonalizable adjacency matrix. This was answered in the affirmative by L. Babai in 1985. Then Babai posed the open problem of constructing a 2-arc-transitive digraph and a vertex-primitive digraph whose adjacency matrices are not diagonalizable. In this talk, we will give a solution to Babai's problem by constructing an infinite family of 2-arc-transitive digraphs and of vertex-primitive digraphs, respectively, both of whose adjacency matrices are non-diagonalizable.
This talk is based on joint work with Yuxuan Li, Sanming Zhou and Wenying Zhu.
01 March 2022, 5pm AEDT Gabriel Verret (University of Auckland)
(k, t)-regular graphs
Abstract:
A graph is called (k, t)-regular if it is k-regular and the induced subgraph on the neighbourhood of every vertex is t-regular. We are interested in the following question: For which pairs (k, t) does there exist a (k, t)-regular graph? This is a very simple yet interesting question about which little was known. I will discuss previous knowledge as well as some new results obtained with Marston Conder and Jeroen Schillewaert.
15 February 2022, 11am AEDT Mehtaab Sawhney (MIT)
High Girth Steiner Triple Systems
Abstract: We prove a 1973 conjecture due to Erdős on the existence of Steiner triple systems with arbitrarily high girth. Our proof builds on the method of iterative absorption for existence of designs by Glock, Kühn, Lo, and Osthus while incorporating a "high girth triangle removal process". In particular, we develop techniques to handle triangle-decompositions of polynomially sparse graphs, construct efficient high girth absorbers for Steiner triple systems, and introduce a moments technique to understand the probability our random process includes certain tuples of triples. In this talk we will also give a high-level overview of iterative absorption.
This work is joint with Matthew Kwan, Ashwin Sah, and Michael Simkin.