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 1400 UK time.

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

Wed 9 Oct 2024 1400 UK

Emma Smith (Royal Holloway)

Distinct Difference Configurations and cardinality bounds in free groups

A *Distinct Difference Configuration* is a subset of a group whose pairwise differences are distinct. The subset is bounded (with diameter at most \(d\)) if these differences all have length at most \(d\). The existence of large bounded Distinct Difference Configurations is of cryptographic interest due to their application to symmetric key distribution in sensor networks. We show that the largest distinct difference configuration in a free group of rank \(n\) of diameter \(d\) has cardinality approximately \((2n-1)^{d/3}\).

Wed 23 Oct 2024 1400 UK

Olivia Reade (Open University)

Wed 6 Nov 2024 1400 UK

Xandru Mifsud (University of Oxford)

Wed 27 Nov 2024 1400 UK

Alexey Gordeev (Umeå University, Sweden)

Wed 4 Dec 2024 1400 UK

Yacong Zhou (Royal Holloway)

Wed 8 Jan 2025 1400 UK

Speaker TBA

Wed 22 Jan 2025 1400 UK

Mark Ellingham (Vanderbilt University)

Maximum genus embeddings of Eulerian graphs and digraphs with specified faces

Embeddings with faces bounded by Euler circuits arise in several situations, such as building DNA models of graphs that can be scanned easily, and finding maximum genus orientable directed embeddings of digraphs. We discuss results on the existence of such embeddings, including situations where some of the faces can be specified in advance. First, graphs or Eulerian digraphs where all vertices have degree congruent to 2 mod 4 have an orientable embedding with two Euler circuit faces, where one of the Euler circuits can be specified in advance. Second, sufficiently dense Eulerian graphs or digraphs have an orientable embedding where a decomposition of the graph or digraph into circuits (closed trails) can be specified in advance as a subset of the faces, and there are at most two other faces. The required density condition is that each vertex in the \(n\)-vertex graph or digraph has at least \((4n+2)/5\) neighbours. This generalizes results of Bonnington et al. on upper embeddings of regular tournaments and of Griggs, McCourt and Širáň on upper embeddings of oriented Steiner triple systems. We discuss some of the ideas used in the proofs of these results and some extensions and related results.

This is joint work with Jo Ellis-Monaghan of the University of Amsterdam.

Wed 12 Feb 2025 1400 UK

Speaker TBA

Wed 26 Feb 2025 1400 UK

Speaker TBA

Wed 12 Mar 2025 1400 UK

Jorik Jooken (KU Leuven, Belgium)

Vertex-girth-regular graphs (title TBC)

Wed 26 Mar 2025 1400 UK

Speaker TBA

Wed 11 Sep 2024 1400 UK

Christina Zarb (University of Malta)

The feasibility of families of graphs characterised by forbidden induced subgraphs
Slides (pdf)

The *Feasibility Problem* is an umbrella for various specific problems in extremal combinatorics. Let \({\cal F}\) be an infinite family of graphs. Then \({\cal F}\) is called *feasible* if for every \(n \geq 1\), \(0 \leq m \leq \binom{n}{2}\), there is a graph \(G \in {\cal F}\) having exactly \(n\) vertices and \(m\) edges. If \({\cal F}\) is not feasible, it is of interest to find the set of all feasible pairs
\[FP({\cal F})= \{ ( n ,m) : \mbox{ there is a graph \(G \in {\cal F}\) having \(n\) vertices and \(m\) edges}\},\]
as well as the complementary set
\[\overline{FP}({\cal F})= \{ ( n, m) : \mbox{ no member of \({\cal F}\) has precisely \(n\) vertices and \(m\) edges}\}.\]

In the paper [1], the feasibility problem for line graphs was considered and the sets \(\overline{FP}({\cal F})\) and \(FP({\cal F})\) when \({\cal F}\) is the family of all line graphs were determined.

Inspired by the fact that line graphs are characterised by the nine forbidden Bieneke graphs [2], we here consider families of graphs which are characterised by a set of forbidden induced subgraphs. We call such families \({\cal H}\)-*free*, where \({\cal H}\) is the set of forbidden induced subgraphs. In particular we consider \({\cal F}(G)\), which is the family of graphs which is induced \(G\)-free, and show that is feasible if and only if \(G\) is not \(K_k\), \(K_k\backslash K_2\), \(\overline{K_k}\), \(\overline{K_k\backslash K_2}\), for \(k \geq 2\).

We then consider the following natural question : Suppose \(G\) and \(H\) are graphs such that \({\cal F}(G)\) and \({\cal F}(H)\) are both feasible families. Is \({\cal F}(G,H)\), the family of all graphs which are simultaneously induced \(G\)-free and induced \(H\)-free, necessarily feasible? We give examples which result in non-feasibility, and examples which result in feasible families, and discuss some conditions which explain these results.

This talk is based on joint work with Yair Caro, Matthew Cassar and Josef Lauri.

[1]
Y. Caro, J. Lauri, and C. Zarb.
The feasibility problem for line graphs.
*Discrete Applied Math.*, 324:167–180, 2023.

[2]
L.W. Beineke.
Characterizations of derived graphs.
*J. of Combin. Theory*, 9(2):129–135, 1970.

Wed 24 Apr 2024 1330 UK

Jonathan Fine

A Pascal-like triangle for Fibonacci numbers
Notes (pdf)

We define a triangle of numbers, whose row sums are Fibonacci numbers. The rows of this triangle are similar to the rows of Pascal's triangle (which sum to the powers of 2). For example:

34 = 1 + 5 + 11 + 11 + 5 + 1

55 = 1 + 5 + 13 + 17 + 13 + 5 + 1

89 = 1 + 7 + 21 + 31 + 21 + 7 + 1

In both the Pascal and Fibonacci triangles the rows are palindromic and increase to the middle, but not too rapidly. In both cases, each row sum is the dimension of a vector space of flags for objects that have homology that satisfies Poincaré duality and hard Lefschetz. This was the speaker's original motivation. Perhaps the additional structure gives new insight into Fibonacci numbers.

Wed 27 Mar 2024 1330 UK

Jude Buot (Ateneo de Manila University, Philippines)

The ham-sandwich theorem and other subdivision problems of colored point sets in the plane

Points in the plane are said to be in *general position* if no three are collinear.
Given any configuration of red and blue points in the plane in general position,
the *ham-sandwich theorem* guarantees the existence of a line (or *ham-sandwich cut*)
that subdivides the plane into two regions each containing the same number of red and blue points.
In this talk, I discuss some results in discrete geometry that make use of the ham-sandwich theorem,
and present other subdivision problems in the plane that extend or generalize this classical result.

Wed 28 Feb 2024 1330 UK

Suhadi Wido Saputro (Institut Teknologi Bandung, Indonesia)

The metric dimension of (edge) comb product graphs
Slides (pdf)

A set of vertices \(W\) *resolves* a graph \(G\) if every vertex is uniquely determined by its coordinate of distance
to the vertices in \(W\). The minimum cardinality of a resolving set of \(G\) is called the *metric dimension* of \(G\).
In this talk, we consider a graph which is obtained by the (edge) comb product between two connected graphs.
Let \(o\) be (an edge) a vertex of \(H\). The (edge) *comb product* between \(G\) and \(H\), denoted by
(\(G\unrhd_o H\)) \(G\rhd_o H\), is a graph obtained by taking one copy of \(G\) and (\(|E(G)|\) copies) \(|V(G)|\) copies of \(H\)
and identifying the \(i\)-th copy of \(H\) at the (edge) vertex \(o\) to the \(i\)-th (edge) vertex of \(G\).
We give an exact value of the metric dimension of \(G\rhd_o H\) where \(H\) is not a path,
or \(H\) is a path where the vertex \(o\) is not a leaf.
Furthermore, we provide sharp general bounds of the metric dimension of \(G\rhd_o P_n\) for \(n\geq 2\)
where the vertex \(o\) is a leaf of \(P_n\).
We also determine an exact value of the metric dimension of \(G\unrhd_o H\)
where \(H\) is a connected graph containing a bridge \(o\).

Joint work with Novi Mardiana, Ira Apni Purwasih, Erma Suwastika and Pritta Etriana Putri.

Wed 14 Feb 2024 1330 UK

Mónica Reyes (Universitat de Lleida, Catalonia)

On token graphs

In graph theory, there are different operations that construct a "large" graph from a "smaller" one.
Then, the question is what properties of the former can be deduced (or, at least, approximated) from the properties of the latter.
One of these operations that recently received some attention in the literature is the construction of token graphs.
The \(k\)-*token graph* \(F_k(G)\) of a graph \(G\) is the graph whose vertices are the \(k\)-subsets of vertices from \(G\),
two of which being adjacent whenever their symmetric difference is a pair of adjacent vertices in \(G\).

In this talk, we'll discuss some interesting facts about token graphs.

Wed 31 Jan 2024 1330 UK

Tymoteusz Chojecki (UMCS, Lublin, Poland)

New results on algebraic constructions of Extremal Graph Theory and implementations of new algorithms of Postquantum Cryptography
Slides (pdf)

We study a family of graphs \(A(n,q)\). This is a family of small world graphs, which are given by some system of equations. Our field of interest is girth and diameter of these graphs. We use these graphs in post-quantum cryptography, implementing symmetric ciphers and public key algorithms. I will show the results we obtained by implementing our algorithms on a computer using Python and Sage.

Joint work with Vasyl Ustimenko.

Wed 13 Dec 2023 1330 UK

Meysam Korivand (Alzahra University, Tehran)

Resolving Sets Breaks Symmetry in Graphs
Slides (pdf)

The talk is an investigation of the connection between the classical graph theory concepts of the metric dimension and the distinguishing number. We recently showed that in connected graphs, every resolving set breaks graph symmetry. Precisely, if \(G\) is a connected graph with a resolving set \(S=\{v_1, v_2, \ldots, v_n \}\), then \(\{\{v_1\}, \{v_2\}, \ldots, \{v_n\}, V(G)\setminus S \}\) is a partition of \(V(G)\) into a distinguishing coloring, and as a consequence \(D(G)\leq {\rm dim}(G)+1\).

Joint work with Prof. N. Soltankhah.

Wed 29 Nov 2023 1330 UK

Alexander Clifton (Institute for Basic Science, Korea)

Saturated Partial Embeddings of Planar Graphs
Slides (pdf)

We study how far one can deviate from optimal behavior when drawing a planar graph on a plane.
For a planar graph \(G\), we say that a plane subgraph \(H \subseteq G\) is a *plane-saturated subgraph*
if adding any edge (possibly with a new vertex) to \(H\) would either violate planarity or make the resulting graph
no longer a subgraph of \(G\). For a planar graph \(G\), we define the *plane-saturation ratio*, \(\mathrm{psr}(G)\),
as the minimum value of \(e(H)/e(G)\) for a plane-saturated subgraph \(H \subseteq G\) and investigate how
small \(\mathrm{psr}(G)\) can be. While there exist planar graphs where \(\mathrm{psr}(G)\) is arbitrarily
close to 0, we show that for all twin-free planar graphs, \(\mathrm{psr}(G) > 1/16\),
and that there exist twin-free planar graphs where \(\mathrm{psr}(G)\) is arbitrarily close to \(1/16\).

Joint work with Nika Salia.

Wed 7 Jun 2023 1400 UK

Geoffrey Exoo (Indiana State University)

On Mixed Graphs, Girth, Diameter and Geodecity
Slides (pdf)

Some recent results on the search for extremal graphs with given degree and girth, diameter or geodecity are presented. For degree and girth, we investigate a promising connection with strongly regular graphs.

Two new methods for obtaining exact answers are discussed and applied to the diameter and geodecity problems.

Wed 12 Apr 2023 1400 UK

Silvia Barbina (University of Camerino)

Steiner triple systems: a model theoretic viewpoint
Slides (pdf)

Steiner triple systems (STS) are well known combinatorial objects for which the literature is extensive. An STS is a set \(S\) together with a collection \(B\) of subsets of \(S\) of size 3 such that any two elements of \(S\) belong to exactly one element of \(B\).

Recently, the infinite counterparts of these structures have proven interesting in the context of model theory, a branch of mathematical logic. We will survey recent results in the area, in particular regarding the countable universal homogeneous STS and free constructions of STSs, and explain their model theoretic significance.

Wed 22 Mar 2023 1500 UK

Vasyl Ustimenko (Royal Holloway)

On some optimisation problems for homogeneous algebraic graphs
Notes (pdf)

Homogeneous algebraic graphs defined over an arbitrary field are classical objects of Algebraic Geometry. This class includes geometries of Chevalley groups \(A_2(F)\), \(B_2(F)\) and \(G_2(F)\) defined over an arbitrary field \(F\). Assume that codimension of homogeneous graph is the ratio of dimension of variety of its vertices and the dimension of neighbourhood of some vertex. We evaluate the minimal codimension \(v(g)\) and \(u(h)\) of an algebraic graph of prescribed girth \(g\) and cycle indicator \(h\). Recall that girth is the size of a minimal cycle in the graph and girth indicator stands for the maximal value of the shortest path through some vertex. We prove that for even \(h\) the inequality \(u(h)\leq(h-2)/2\) holds. We define a class of homogeneous algebraic graphs with even cycle indicator \(h\) and codimension \((h-2)/2\). It contains geometries \(A_2(F)\), \(B_2(F)\) and \(G_2(F)\) and infinitely many other homogeneous algebraic graphs.

Wed 1 Feb 2023 1400 UK

Nóra Frankl (Open University)

Helly numbers of exponential lattices
Slides (pdf)

The *Helly number* of a set S in the plane is the smallest N such that the following is true. If any N members of a finite family of convex sets contains a point of S, then there is a point of S which is contained in all members of the family. An exponential lattice with base x consists of points whose coordinates are positive integer powers of x. We prove lower and upper bounds on Helly numbers of exponential lattices in terms of x, and we determine their values exactly in some cases. We also consider asymmetric exponential lattices, and characterise those that have finite Helly numbers.

Joint work with Gergely Ambrus, Martin Balko, Attila Jung and Márton Naszódi.

Wed 25 Jan 2023 1400 UK

Dan Rust (Open University)

Combinatorics of set-valued substitutions

Symbolic dynamics is a subject that benefits from many areas of mathematics, including topology, ergodic theory, operator theory, number theory and combinatorics. There has been a recent explosion in literature on 'set-valued' or 'random' substitutions, which are like substitutions, but instead of mapping a letter to a single word, it is mapped to an element of a finite set of words according to a non-deterministic generating rule. The language generated by a set-valued substitution can be huge. One way to quantify the size of the language is via the entropy of the system. Another way is to count the number of 'periodic blocks' that the language admits. It's therefore important to develop techniques for counting these quantities and establishing growth rates. In this talk, I'll report on the current state of the art for tackling these problems.

Wed 4 Jan 2023 1400 UK

Tatiana Jajcayová (Comenius University, Bratislava)

Representations of groups and inverse semigroups on (uniform) hypergraphs
Slides (pdf)

In our talk, we will discuss our project of constructing uniform hypergraphs whose full automorphism group is isomorphic to a prescribed finite group \(G\) and acts regularly on the vertices of the hypergraph. This project is a generalization of the classical problem of Graphical Regular Representations and relies on a generalization of Cayley graphs to Cayley hypergraphs.

We will then turn our attention to the more general concept of *partial* automorphisms which we believe better captures local properties of the considered combinatorial structures. In the context of partial automorphisms, we address analogous questions of representing hypergraphs via inverse semigroups.

Tue 6 Dec 2022 1400 UK

Vasyl Ustimenko (RHUL and Institute of telecommunications and global information space, Kyiv, Ukraine)

New results on properties of algebraic constructions of extremal graph theory
Slides/notes (pdf)

For an arbitrary finite field \(\mathbb{F}_q\), \(q>2\) we prove that known \(q\)-regular algebraic bipartite graphs \(A(n, q)\) on \(2q^n\) vertices have girth \(2n\) or \(2n+2\). A similar result is formulated for more general graphs \(A(n, K)\) defined over a general commutative integrity ring \(K\). The impact of these results on Extremal Graph Theory and its applications will be discussed.

This research is partially supported by the Fellowship of British Academy for Researchers at Risk 2022.

Wed 23 Nov 2022 1400 UK

Dan Cocks (Open University)

Minimal hereditary classes of graphs of unbounded tree-width or clique-width
Slides (pdf)

Many decision problems defined on a graph are generally hard, but are easy (i.e. an algorithm exists) when restricted to graphs in certain classes. In particular, these include graphs from classes with bounded tree-width or clique-width.

We seek to characterize those graphs at the boundary where hard problems become easy, that is, to identify "minimal" hereditary graph classes that are obstructions to bounded tree-width or clique-width.

This presentation is based on joint work with Robert Brignall.

Wed 26 Oct 2022 1400 UK

Nacho López (Dept. de Matemàtica, Universitat de Lleida, Catalonia)

Getting closer to a Moore graph
Slides (pdf)

Moore graphs are extremal graphs that appear in the context of the degree/diameter problem. The fact that Moore graphs are very rare suggest the study of graphs that are, in some sense, close to being a Moore graph. This closeness measure has been usually given by the difference between the Moore bound and the order of the corresponding founded graphs. Nevertheless, other approximations can be considered. In this talk we will present some background of the topic and we will discuss about these closeness measures.

Wed 28 Sep 2022 1400 UK

Gabriela Araujo-Pardo (Instituto de Matemáticas, Universidad Nacional Autónoma de México)

Bipartite biregular cages: block designs and generalized polygons

A *bipartite biregular* \((m,n;g)\)-graph \(\Gamma\) is a bipartite graph of even girth \(g\) having the degree set \(\{m,n\}\) and satisfying the additional property that the vertices in the same partite set have the same degree. The \((m,n;g)\)-*bipartite biregular cages*, was introduced in 2019 by Filipovski, Ramos-Rivera, and Jajcay, they are bipartite biregular \((m,n;g)\)-graphs of minimum order. The authors calculate lower bounds on the orders of bipartite biregular \((m,n;g)\)-graphs, and call the graphs that attain these bounds *bipartite biregular Moore cages*.

We improve the lower bounds obtained in the above paper. Furthermore, in parallel with the well-known classical results relating the existence of \(k\)-regular Moore graphs of even girths \(g = 6,8\) and \(12\) to the existence of projective planes, generalized quadrangles, and generalized hexagons, we prove that the existence of an \(S(2,k,v)\)-Steiner system yields the existence of a bipartite biregular \((k,\frac{v-1}{k-1};6)\)-cage, and, vice versa, the existence of a bipartite biregular \((k,n;6)\)-cage whose order is equal to one of our lower bounds yields the existence of an \(S(2,k,1+n(k-1))\)-Steiner system. Moreover, in the special case of Steiner triple systems, we completely solve the problem of determining the orders of \((3,n;6)\)-bipartite biregular cages for all integers \(n\geq 4\).

Considering girths higher than \(6\), we relate the existence of generalized polygons (quadrangles, hexagons and octagons) to the existence of \((n+1,n^2+1;8)\)-, \((n^2+1,n^3+1;8)\)-, \((n,n+2;8)\)-, \((n+1,n^3+1;12)\)- and \((n+1,n^2+1;16)\)-bipartite biregular cages, respectively. Using this connection, we also derive improved upper bounds for the orders of other classes of bipartite biregular cages of girths \(8\), \(12\), and \(14\).

Joint work with Robert Jajcay, Alejandra Ramos, and Tamás Szőnyi.

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.