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.
It is well known that the asymptotic behaviour of the number of objects in a combinatorial class can be determined from the singularities on the circle of convergence of its generating function. In this talk we extend the scope of analytic combinatorics to classes whose objects have irrational sizes by establishing an analogous result when it is no longer required that the size of an object must be an integer.
The generating function for such a class is a power series that admits irrational exponents (which we call a Ribenboim series). A transformation then yields a generalised Dirichlet series from which the asymptotics of the coefficients can be extracted by singularity analysis using an appropriate Tauberian theorem. In practice, the asymptotics can often be determined directly from the original generating function. The technique will be illustrated with a variety of applications, including tilings with tiles of irrational area, lattice walks with irrational step sizes, and trees with vertices of irrational size. We will also explore phase transitions in the asymptotics of families of irrational combinatorial classes.
This is joint work with Julien Condé and Andrew Elvey Price of l’Université de Tours.
A weak \(k\)-resolving set of a graph \(G\) is a set \(S\) of vertices of \(G\) such that the sum of the distance differences from any pair of vertices of \(G\) to all vertices of \(S\) is at least \(k\). The weak \(k\)-metric dimension of \(G\), denoted \(\mathrm{wdim}_k(G)\), is defined as the cardinality of a smallest weak \(k\)-resolving set of \(G\). The largest integer \(k\) such that \(G\) contains a weak \(k\)-resolving set is denoted by \(\kappa(G)\). Several results concerning \(\mathrm{wdim}_k(G)\) and \(\kappa(G)\) shall be discussed in this talk.
The \(k\)-hyperopic cops and robber game is a generalization of the hyperopic cops and robber, analogous to the \(k\)-visibility cops and robber. The game is defined similarly as the usual cops and robber game, but with the robber being omniscient and invisible to the cops that are at distance at most \(k\) away from the robber (i.e. cops are hyperopic or farsighted). The minimum number of cops needed to win the game on a graph is the \(k\)-hyperopic cop number. In this talk we will present some basic properties of the new game, provide a general upper bound and consider the game on trees and outerplanar graphs.
This is joint work with Nicholas Crawford.
Inspired by a chessboard puzzle of Dudeney, the general position problem in graph theory asks for the largest set \(S\) of vertices in a graph such that no three vertices of \(S\) lie on a common shortest path. The number of vertices in such a largest set is called the general position number of the graph. In this talk, we consider a variant of the general position problem, called the monophonic position problem, which is obtained by replacing 'shortest path' with 'induced path'. We explore the monophonic position number on Cartesian and lexicographic products of graphs. It is shown that in Cartesian products, a monophonic position set can take one of only three canonical forms, namely layered, varied, and cliquey. The monophonic position number of an arbitrary Cartesian product is bounded from both below and above. These bounds coincide if neither factor has simplicial vertices. Additionally, we present a formula for the monophonic position number of a lexicographic product that depends only on the clique number and the structure of monophonic sets of the second factor. We discuss some of the key ideas used in the proofs of these results.
This is a joint work with Sandi Klavžar, James Tuite, and Neethu P. K.
A vertex-girth-regular \(\operatorname{vgr}(v,k,g,\lambda)\)-graph is a \(k\)-regular graph of girth \(g\) and order \(v\) in which every vertex belongs to exactly \(\lambda\) cycles of length \(g\). While all vertex-transitive graphs are necessarily vertex-girth-regular, the majority of vertex-girth-regular graphs are not vertex-transitive. Similarly, while many of the smallest \(k\)-regular graphs of girth \(g\), the so-called \((k,g)\)-cages, are vertex-girth-regular, infinitely many vertex-girth-regular graphs of degree \(k\) and girth \(g\) exist for many pairs \(k,g\). Due to these connections, the study of vertex-girth-regular graphs promises insights into the relations between the classes of extremal, highly symmetric, and locally regular graphs of given degree and girth. This paper lays the foundation to such study by investigating the fundamental properties of \(\operatorname{vgr}(v,k,g,\lambda)\)-graphs, specifically the relations necessarily satisfied by the parameters \(v,k,g\) and \(\lambda\) to admit the existence of a corresponding vertex-girth-regular graph, by presenting constructions of infinite families of \(\operatorname{vgr}(v,k,g,\lambda)\)-graphs, and by establishing lower bounds on the number \(v\) of vertices in a \(\operatorname{vgr}(v,k,g,\lambda)\)-graph. It also includes computational results determining the orders of smallest cubic and quartic graphs of small girths.
A poset is well quasi-ordered (wqo) if it contains no infinite descending sequences or infinite antichains; this property is said to distinguish between 'tame' and 'wild' posets. We consider posets where combinatorial structures are related when one is a substructure of the other. Given such a poset, avoidance sets are subsets which are defined by their forbidden substructures. The wqo problem asks if it is decidable, given a finite set of forbidden substructures, whether their avoidance set is wqo. This talk will begin with an overview of the solution for permutations under the consecutive order, as given by McDevitt and Ruškuc, which encodes permutations as paths in certain digraphs. We will explore recent work extending these methods to a variety of combinatorial structures, and then focus on the case of equivalence relations under the consecutive order.
The Wiener index of a vertex coloring of a finite graph is the sum of the pairwise distances between vertices of the same color. Thus, a large Wiener index indicates that, in a sense, the color classes of a vertex coloring are spread out within the graph. We will discuss several notions of what it means for a vertex coloring to have "maximal Wiener index", and we will present characterizations of various kinds of maximizers on cycle and path graphs.
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.
For any simple graphs \(F\), \(G\) and \(H\), we define \(F\to(G,H)\) if, under any red-blue edge coloring of \(F\), there exists either a red copy of \(G\) or a blue copy of \(H\). A graph \(F\) is called a Ramsey graph for \((G,H)\) if \(F\to(G,H)\). Furthermore, if \(F\) satisfies the condition that removing any edge \(e\) results in \(F −e \not\to (G,H)\), then \(F\) is referred to as a Ramsey \((G,H)\)-minimal graph. The set of all Ramsey \((G,H)\)-minimal graphs is denoted by \(\mathcal{R}(G,H)\).
Recent studies on certain classes of graphs belonging to \(\mathcal{R}(C_4,K_{1,n})\) were conducted by Nabila et al, who used paths to construct theta-path graphs, and Assiyatun et al, who utilized trees to construct theta-tree graphs. In this research, we present constructions of Ramsey \((C_4,K_{1,n})\)-minimal graphs based on unicyclic graphs for any \(n \geq 2\).
This talk is based on joint work with Hilda Assiyatun and Edy Tri Baskoro.
Let \(D=(V(D), A(D),w)\) be a weighted digraph, \(X\) and \(Y\) be a partition of \(V(D)\). Then the directed cut (or dicut for short) \((X,Y)\) of \(D\) is the bipartite subgraph of \(D\) induced by the arcs going from \(X\) to \(Y\).
In this talk, we will establish lower bounds for the maximum weight of dicuts in the classes of weighted digraphs and acyclic digraphs, as well as in some of their subclasses. In particular, we show that every weighted acyclic digraph with \(w(D)\geq 1\) admits a dicut with weight at least \(\frac{w(D)}{4}+\Omega(w^{3/5}(D))\).
This talk is based on joint work with Jiangdong Ai, Stefanie Gerke, Gregory Gutin, and Anders Yeo.
A \((v, r \times c)\)-triple array is an \(r \times c\) table with each cell filled with one of \(v\) symbols, such that each symbol occurs the same number of times, there are no repetitions in rows and columns, any two rows have the same number of common symbols, and the same is true (with a different constant) for any two columns, and for any pair of a row and a column.
In the first part of the talk, I will describe a new way to construct triple arrays by combining a resolution of a 2-design and a symmetric design with compatible parameters. We used this construction to produce many new non-extremal triple arrays, i.e. those with \(v > r + c - 1\). Only one example of a non-extremal triple array was known before.
In the remaining time, I will introduce a new concept of near-triple arrays with slightly relaxed intersection conditions compared to triple arrays. These designs exist for a much wider range of parameters, which we verified by enumerating near-triple arrays for small parameter sets. As a byproduct of these enumeration efforts, we classified up to isotopism \((14, 7 \times 8)\), \((15, 6 \times 10)\) and \((20, 5 \times 16)\)-triple arrays for the first time.
This talk is based on joint work with Lars-Daniel Öhman.
Let \(r, b \in \mathbb{N}\) such that \(b\lt r\). Given a \((b + r)\)-regular graph, does there exist a colouring of its edges such that every vertex is incident to exactly \(b\) blue edges and \(r\) red edges, but such that in each closed neighbourhood there are more blue edges than red edges? We term such a graph as a \((b, r)\)-flip graph, due to the local vs. global majority flip they demonstrate. We show that such edge-coloured graphs do exist, namely for when the difference between \(b\) and \(r\) is not too great, as intuition would suggest. In particular, it is shown that a \((b,r)\)-flip graph exists if, and only if, \(3 \leq b \lt r \lt \binom{b+1}{2}\).
In this talk we will establish a number of bounds on the number of vertices \(h(b, r)\) of the smallest \((b,r)\)-flip graph. Somewhat surprisingly we show that such graphs can be very small, illustrating cases where \(h(b, r)\) is \(\Theta(b+r)\). To establish these results, we provide a number of different construction techniques using: edge-coloured graph products, graph packings and Cayley graphs. We conclude with a short survey of known results about the flip-colouring problem with \(k \geq 3\) colour-degrees \((a_1, a_2, \dots, a_k)\), including some surprising results that provide some insight into \(h(a_1, a_2, \dots, a_k)\) (where good bounds are still not known).
This talk is based on joint work with Yair Caro, Josef Lauri, Raphael Yuster, and Christina Zarb.
An orientably-regular map is an embedding of a graph on an orientable surface which demonstrates as much rotational symmetry as possible. The rotary automorphism group is generated by the natural rotations around a face and incident vertex. Examples include the Platonic solids, which can be viewed as graphs on the sphere. If an orientably-regular map lacks reflectional symmetry, then it is said to be chiral.
In this talk we use permutation diagrams to extend the proof of the existence of hyperbolic chiral maps of given vertex valency and face length, thereby proving that such maps exist with simple automorphism group.
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}\).
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.
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.
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.
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.
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.
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.
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.
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.