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 1330 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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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).
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.
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.
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).
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.
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.
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.
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.
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.
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.
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.
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.
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.
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'.
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.
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.
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.