Open University Discrete Mathematics Seminar Series

This is the home page of the discrete mathematics seminar series organised by the combinatorics group at the OU. Seminars are (roughly) every two weeks, usually on Wednesday afternoons at 2pm UK time.

All current and former OU researchers are welcome to attend. To be added to the circulation list for meeting invitations, or to suggest speakers, please email Grahame Erskine.

Upcoming Talks

The programme for the 2021/22 academic year is now complete.

Previous Talks

Wed 8 Jun 2022 1400 UK
Chimere Anabanti (University of Pretoria, South Africa )
Which finite groups are filled? Slides (pdf)

A non-empty subset \(S\) of a group \(G\) is called a product-free set if \(S\) and \(SS\) have no element in common. Let \(S\) be a maximal by inclusion product-free set in a finite group \(G\). We say that \(S\) fills \(G\) if every non-identity element of \(G\) is contained in the union of \(S\) and \(SS\). A finite group \(G\) is called a filled group if every maximal by inclusion product-free set in \(G\) fills \(G\). In this talk, we shall give an application of product-free sets to combinatorics, as well as discuss the known finite filled groups.

Part of this presentation is a joint work with Sarah Hart and Grahame Erskine.

Wed 25 May 2022 1400 UK
Olivia Jeans (Open University)
Edge-biregular maps of every feasible type exist Slides (pdf)

An edge-biregular map is a highly symmetric map with an automorphism group which partitions the flag set of the map into two orbits in such a way that the action is not edge-transitive. Such maps necessarily have even valency and even face length, and are equivalent to groups generated by two pairs of commuting involutions. In this talk we will use permutation diagrams to prove that edge-biregular maps exist for every type \((2k,2l)\), focussing especially on those whose underlying group is alternating or symmetric.

Wed 27 Apr 2022 1400 UK
Klara Stokes (Umeå University, Sweden)
Rigid and flexible rod configurations of points and lines Slides (pdf)

A rod configuration is a geometric realization of a rank two incidence geometry (a hypergraph) in terms of points and line segments of Euclidean space, together with a notion of motion that treats the line segments as rigid bodies (rods). In this talk I will explain how to use combinatorics to decide if a rod configuration is rigid in the plane. I will also talk about flexible rod configurations and discuss some open problems.

This is joint work with Signe Lundqvist and Lars-Daniel Öhman.

Wed 2 Mar 2022 1400 UK
Casey Tompkins (Rényi Institute, Budapest)
The Ramsey number of Boolean lattices Slides (pdf)

The poset Ramsey number \(R(Q_{m},Q_{n})\) is the smallest integer \(N\) such that any blue-red coloring of the elements of the Boolean lattice \(Q_{N}\) has a blue induced copy of \(Q_{m}\) or a red induced copy of \(Q_{n}\). The weak poset Ramsey number \(R_{w}(Q_{m},Q_{n})\) is defined analogously, with weak copies instead of induced copies. It is easy to see that \(R(Q_{m},Q_{n})\ge R_{w}(Q_{m},Q_{n})\).

Axenovich and Walzer showed that \(n+2\le R(Q_{2},Q_{n})\le2n+2\). Recently, Lu and Thompson improved the upper bound to \(\frac{5}{3}n+2\). In this talk, we solve this problem asymptotically by showing that \(R(Q_{2},Q_{n})=n+O(n/\log n)\).

This is work with Daniel Grosz and Abhishek Methuku.

Wed 16 Feb 2022 1400 UK
Katherine Staden (Open University)
The Erdős-Rothschild problem Notes (pdf)

Questions about forbidden subgraphs form a central part of extremal graph theory. In this talk I will discuss a colourful problem of this sort: the Erdős-Rothschild problem from 1974. Consider an \(n\)-vertex graph \(G\) whose edges are coloured with \(s\) colours so that there is no monochromatic clique of size \(k\), and call such a colouring of \(G\) valid. The problem is to determine the maximum number of valid colourings over all \(n\)-vertex graphs \(G\). It is in general wide open and an exact (or even asymptotic) answer is only known for a few pairs \((k,s)\). In this talk I will discuss new exact results, and intriguing connections to algebra and designs.

Joint work with Oleg Pikhurko.

Wed 2 Feb 2022 1400 UK
Margaret Stanier (Open University)
Spectra of Farey maps and graphs Slides (pdf)

We determine the spectra of a class of cartographic maps called Farey maps, which are regular maps on oriented surfaces defined by congruence subgroups of the modular group. Our strategy is to find some general results for those maps which are regular coverings of other maps whose spectrum is known. Then we apply the same techniques to find the spectra of the underlying graphs of Hecke maps, which are defined, in the same way as Farey maps, by certain subgroups of Hecke groups.

Wed 19 Jan 2022 1400 UK
Grahame Erskine (Open University)
Small 3-regular graphs and 3-uniform hypergraphs of given girth Slides (pdf)

The cage problem is a long-standing topic in extremal graph theory, with the object being to determine the smallest possible d-regular graph of given girth g. As the girth g becomes large, the best constructions we have are asymptotically very far from the theoretical bound.

There is a natural extension of this problem to the realm of hypergraphs, where in our case the girth is defined to be the length of the shortest Berge cycle in the hypergraph. We concentrate primarily on the case of 3-uniform hypergraphs, where each hyperedge contains exactly 3 vertices. By using analogues of techniques used in the graph version of the cage problem such as Cayley graphs, we find small examples of 3-uniform hypergraphs of given girth.

By considering duality in the hypergraph problem, we are able to apply our methods to different parameter sets. As a concrete example, our 3-uniform hypergraphs can be used to find new record smallest cubic (3-regular) graphs for a number of girths in the classical cage problem.

This is joint work with James Tuite (Open University).

Wed 15 Dec 2021 1400 UK
Nick Gill (Open University)
The relational complexity of a finite permutation group Slides (pdf)

Let \(G\) be a group acting on a set \(X\). The relational complexity of this action is a positive integer that indicates how efficiently one can represent \(G\) as the automorphism group of a homogeneous relational structure with vertex set \(X\). This horrible-sounding definition can actually be rather easily understood by thinking about groups acting on graphs, and for the first third of the talk we will explore this point of view.

In the middle third of the talk we will discuss some of the theorems that model theorists have proved using the idea of relational complexity. These theorems concern the structure and organisation of "the universe of finite permutation groups". In the final third of the talk we will discuss recent attempts by a variety of authors to calculate and/or bound the relational complexity of specific families of finite permutation groups.

I will probably mention joint work with various people including Dalla Volta, Hudson, Hunt, Liebeck, Loda and Spiga.

Wed 17 Nov 2021 1400 UK
Stoyan Dimitrov (University of Illinois Chicago)
Moments of permutation statistics and central limit theorems Slides (pdf)

We show that if a permutation statistic can be written as a linear combination of bivincular patterns, then its moments can be expressed as a linear combination of factorials with constant coefficients. This generalizes a result of Zeilberger. We use an approach of Chern, Diaconis, Kane and Rhoades, previously applied on set partitions and matchings. In addition, we give a new proof of the central limit theorem (CLT) for the number of occurrences of classical patterns, which uses a lemma of Burstein and Hästö. We give a simple interpretation of this lemma and an analogous lemma that would imply the CLT for the number of occurrences of any vincular pattern. Furthermore, we obtain explicit formulas for the moments of the descents and the minimal descents statistics. The latter is used to give a new direct proof of the fact that we do not necessarily have asymptotic normality of the number of pattern occurrences in the case of bivincular patterns.

This talk is based on joint work with Niraj Khare.

Wed 10 Nov 2021 1530 UK
Vladislav Taranchuk (University of Delaware)
On a new family of algebraically defined graphs with small automorphism group Slides (pdf)

Over the past few decades, algebraically defined graphs have gained a lot of attention due to their applications to Turán type problems in graph theory and their connections to finite geometries. In this talk, we discuss how the algebraically defined graphs have been used to tackle a long standing question regarding the existence of new generalized quadrangles. Furthermore, we demonstrate a new family of algebraically defined graphs whose existence implies that there are potentially many new families of graphs yet to be studied that may provide a new generalized quadrangle. This talk is based on joint work with Felix Lazebnik (University of Delaware).

Wed 30 Jun 2021 1400 UK
James Tuite (Open University and Rényi Institute, Budapest)
Turán problems in digraphs Slides (pdf)

A Turán-type problem asks for the largest possible number of edges in a graph not containing some forbidden subgraphs. A problem of particular interest is to determine the largest size of a graph not containing short cycles; even for small values of the girth the asymptotic behaviour of the size of extremal graphs is not well understood. In this talk we will discuss a generalisation of this problem to directed graphs using a parameter called geodetic girth. For small values of the geodetic girth we classify the extremal digraphs and for larger values we present upper and lower bounds on the extremal size.

Wed 2 Jun 2021 1400 UK
Edita Máčajová (Slovak Technical University, Bratislava)
Cubic graphs that cannot be covered with four perfect matchings Slides (pdf)

A conjecture of Berge suggests that every bridgeless cubic graph can have its edges covered with at most five perfect matchings. Since three perfect matchings suffice only when the graph in question is 3-edge-colourable, the rest of cubic graphs falls into two classes: those that can be covered with four perfect matchings, and those that need at least five. Cubic graphs that require more than four perfect matchings to cover their edges are particularly interesting as potential counterexamples to several profound and long-standing conjectures including the celebrated cycle double cover conjecture. However, so far they have been extremely difficult to find.

In this talk we build a theory that describes coverings with four perfect matchings as flows whose flow values and outflow patterns form a configuration of six lines spanned by four points of the 3-dimensional projective space \(P_3(\mathbb{F}_2)\) in general position. This theory provides powerful tools for investigation of graphs that do not admit such a cover and offers a great variety of methods for their construction. As an illustrative example we produce a rich family of snarks (nontrivial cubic graphs with no 3-edge-colouring) that cannot be covered with four perfect matchings. The family contains all previously known graphs with this property.

In the second part of the talk we discuss the fact that all known snarks that cannot be covered with four perfect matchings have circular flow number 5. It has been suggested [Electron. J. Combin. 23 (2016), #P3.54] that this is always the case. We dispel these hopes and present a family of cyclically 4-edge-connected cubic graphs of girth at least 5 (snarks) which cannot be covered with four perfect matchings and have circular flow number at most 4+2/3.

Wed 19 May 2021 1400 UK
Scott Hudson (University of South Wales)
An introduction to relational complexity Slides (pdf)

The relational complexity of a finite group acting on a finite set is a number that can be calculated for the action. In this talk relational complexity will be defined, illustrated with examples, its origins in model theory discussed and a related concept called the height of an action looked at. An overview of my PhD project on this topic will be given as well as seeing other research carried out in this area.

Wed 5 May 2021 1400 UK
Marién Abreu (Università degli Studi della Basilicata, Potenza, Italy)
Extending perfect matchings to Hamiltonian cycles in line graphs Slides (pdf)

A graph admitting a perfect matching has the Perfect-Matching-Hamiltonian property (for short the PMH-property) if each of its perfect matchings can be extended to a Hamiltonian cycle. In this talk we will present some sufficient conditions for a graph \(G\) which guarantee that its line graph \(L(G)\) has the PMH-property. In particular, we prove that this happens when \(G\) is (i) a Hamiltonian graph with maximum degree at most 3, (ii) a complete graph, or (iii) an arbitrarily traceable graph. Further related questions and open problems will be stated.

Joint work with John Baptist Gauci, Domenico Labbate, Giuseppe Mazzuoccolo and Jean Paul Zerafa.

Wed 7 Apr 2021 1400 UK
Miquel Ángel Fiol (Universitat Politècnica de Catalunya, Barcelona)
Local spectra and symmetric powers of walk-regular graphs Slides (pdf)

The \(u\)-local spectrum of a graph \(G\), introduced by Garriga, Yebra, and the speaker, consists of the local eigenvalues and mutiplicities of a vertex \(u\). The local spectrum gives similar information as the (standard) spectrum when \(G\) is `seen' from the vertex \(u\). From the local spectra we can define their corresponding local characteristic functions, which can be seen as a factorization of the characteristic polynomial of \(G\).

When \(G\) is walk-regular, that is, the number of closed \(\ell\)-walks rooted at a vertex \(u\) only depends on \(\ell\ge 0\), every vertex has the same local spectrum, and all the vertex-deleted subgraphs are cospectral. The symmetric \(k\)-power of a graph \(G\) (also knwn as its \(k\)-token graph) has as vertices the \(k\)-subsets of vertices from \(G\), and two vertices are adjacent when their symmetric difference is a pair of adjacent vertices in \(G\).

In this talk, we discuss some properties of the local spectra, focusing on the case of walk-regular graphs and their symmetric powers. For instance, some of the results are used to derive lower and upper bounds for the spectral radius of the token graphs, which in some cases become exact values.

Wed 31 Mar 2021 1400 UK
Rob Lewis (Open University)
Extremal circulant graphs and where to find them Slides (pdf)

The goal of this talk is to present an efficient method for finding families of extremal circulant graphs of any given degree and infinite classes of diameters. This is a sub-problem of the general degree-diameter problem, which is to find graphs with the largest possible number of vertices for a given maximum degree and diameter.

The method relies on an established relationship between finite Abelian groups with \(f\) generators and the free Abelian group \(\mathbb{Z}^f\) on \(f\) generators, and how this relates to a corresponding Abelian Cayley graph with \(f\) generators. The existence of an Abelian Cayley graph with given parameters is associated with the existence of a lattice covering of \(\mathbb{Z}^f\) by Lee spheres of corresponding radius. The lattice is defined by a corresponding matrix of lattice generating vectors. It has been discovered that all extremal and largest-known Abelian Cayley graph families share a property called quasimaximality and are associated with lattice generator matrices of a specific canonical form. It is conjectured that all extremal Abelian Cayley graph families are quasimaximal and are generated by such a canonical lattice generator matrix. The search for such graph families may therefore be restricted to this subset of matrices.

My aim is to ensure that this talk is accessible to mathematicians with no knowledge of graph theory.

Wed 17 Mar 2021 1400 UK
Bridget Webb (Open University)
Fraïssé limits of Steiner triple systems

A mathematical structure is homogeneous if every isomorphism between two of its substructures can be extended to an automorphism of the whole. Fraïssé's theorem says that if a countably infinite class of finite structures obeys certain properties, and so is an amalgamation class, then there is a homogeneous countably infinite structure, its Fraïssé limit, whose finitely generated substructures are precisely the elements of the amalgamation class. For example, the Fraïssé limit of the class of all graphs is the well-known Rado graph.

In this talk we will look at homogeneous Steiner triple systems, including some recent work with Daniel Horsley (Monash) where we construct uncountably many homogeneous Steiner triple systems as Fraïssé limits of amalgamation classes of finite Steiner triple systems avoiding specified subsystems. These systems are in some ways analogous to the Hensen graphs, however, unlike the case for graphs, it is unknown whether it is possible to completely classify all homogeneous Steiner triple systems. We will consider future avenues of research that may help shed light on this difficult problem.

Wed 3 Mar 2021 1400 UK
Robert Jajcay (Comenius University, Bratislava)
Extremal edge-girth-regular graphs Slides (pdf)

Edge-girth-regular graphs retain the local symmetry properties of highly symmetric (edge-transitive) graphs without necessarily admitting a large group of automorphisms. Moreover, many of the extremal graphs with prescribed degree and girth (the so-called cages) or graphs with prescribed degree and diameter belong to the class of edge-girth-regular graphs, and thus, edge-girth-regular graphs constitute a bridge between Algebraic and Extremal Graph Theory.

An edge-girth-regular \(\mathrm{egr}(v,k,g,\lambda)\)-graph is a \(k\)-regular graph of order \(v\) and girth \(g\) in which every edge is contained in \(\lambda\) distinct \(g\)-cycles. Infinitely many \(\mathrm{egr}(v,k,g,\lambda)\)-graphs are known to exist for sufficiently large parameters \((k,g,\lambda)\), and in line with the well-known Cage Problem we attempt to determine the smallest graphs among all edge-girth-regular graphs for given parameters \((k,g,\lambda)\).

To achieve this, we derive lower bounds in terms of the parameters \(k\), \(g\) and \(\lambda\). We also determine the orders of the smallest \(\mathrm{egr}(v,k,g,\lambda)\)-graphs for some specific parameter triples \((k,g,\lambda)\), and address the problem of the smallest possible orders of bipartite edge-girth-regular graphs.

Presented results come from joint work with A. Zavrtanik Drglin, S. Filipovski, and T. Raiman.

Wed 17 Feb 2021 1400 UK
Josef Lauri (University of Malta)
Schur-rings as a valuable resource in the algebraic graph theorist’s toolkit: an example with graphical regular representations Slides (pdf)

The first part of this talk will be expository as I describe some basic properties of Schur-rings which are a special case of coherent configurations and association schemes, and also the notion of graphical regular representations (GRR) of groups. Then I shall show how even a basic use of Schur rings can give results in algebraic graph theory, such as: If \(p\) is a prime number greater than \(5\) and \(3r-2s\equiv t\pmod p\) then \(\mathrm{Cay}(D_p, \{ab^r, ab^s, ab^t\})\) is a cubic GRR of \(D_p\).

I shall illustrate such results with examples and discuss extensions which we are working on.

Joint work with Jonathan Ebejer, University of Malta.

Wed 3 Feb 2021 1400 UK
Jozef Širáň (Open University)
Classification of regular maps of genus 2 Slides (pdf)

A regular map is a graph embedding on a closed surface, with the property that the automorphism group of the embedding is transitive on flags (i.e., on mutually incident vertex-edge-face triples). In the talk I will outline a way in which a classification of regular maps on a surface of genus 2 can be derived `with bare hands'.

Wed 20 Jan 2021 1400 UK
Cristina Dalfó (Universitat de Lleida, Catalonia)
Spectra and eigenspaces from regular partitions of Cayley (di)graphs of permutation groups Slides (pdf)

We present a method to obtain regular (or equitable) partitions of Cayley (di)graphs (that is, graphs, digraphs, or mixed graphs) of permutation groups on \(n\) letters. We prove that every partition of the number \(n\) gives rise to a regular partition of the Cayley graph. By using representation theory, we also obtain the complete spectra and the eigenspaces of the corresponding quotient (di)graphs. More precisely, we provide a method to find all the eigenvalues and eigenvectors of such (di)graphs, based on their irreducible representations. As examples, we apply this method to the pancake graphs \(P(n)\). As a byproduct, the existence of perfect codes in \(P(n)\) allows us to give a lower bound for the multiplicity of its eigenvalue -1.

Joint work with Miquel Ángel Fiol, Universitat Politècnica de Catalunya, Barcelona.

Wed 16 Dec 2020 1400 UK
David Bevan (Strathclyde University)
Limits of permutations and other discrete objects Slides (pdf)

I will present four (related) notions of convergence introduced recently for sequences of permutations, and some specific results, including the independence of permutation limits at infinitely many scales. The relationship between permutation limits and the analytic limits of other combinatorial objects such as graphs (graphons and graphings) and Latin squares (latinons) will be explored.

Wed 02 Dec 2020 1400 UK
Robert Brignall (Open University)
Labeled well-quasi-order for permutation classes Slides (pdf)
Wed 18 Nov 2020 1400 UK
Nika Salia (Rényi Institute, Budapest)
Survey of Recent Generalisations of Erdős—Gallai Theorems for Berge Hypergraphs Slides (pdf)

A problem, first considered by Erdős and Gallai in 1959, was to determine the Turán number of paths and families of long cycles. In particular Erdős and Gallai determined the maximum number of edges in a graph without a path (not necessarily induced) of length \(k\), \(ex(n,P_k)\leq \frac{(k - 1)n}{2}\) for every \(n \geq k \geq 1\) and the maximum number of edges in a graph without a cycle of length at least \(k\), \(ex(n,C_{\geq k}) \leq \frac{(k - 1)(n - 1)}{2}\) for any \(n \geq k \geq 3\).

Recently numerous mathematicians started investigating similar problems for \(r\)-uniform hypergraphs. They determined the maximum number of hyperedges in an \(r\)-uniform hypergraphs without Berge paths/cycles. A Berge-path of length \(k\) in a hypergraph is a sequence \(v_1,e_1,v_2,e_2,\dots,v_{k},e_k,v_{k+1}\) of distinct vertices and hyperedges with \(v_{i+1}\in e_i,e_{i+1}\) for all \(i\in[k]\).

In this talk we will try to survey those results as well as give you some ideas for possible further research.