A resolving set for a graph Γ is a subset of vertices with the property that the list of distances from a vertex to the chosen set uniquely identifies that vertex. The metric dimension of Γ is the smallest size of a resolving set.

We will give construction methods for resolving sets in Johnson, Kneser and Grassmann graphs, which all reside in association schemes. In particular, we can use incidence matrices of set systems to obtain resolving sets for the Johnson graph J(n,k), and show how some interesting combinatorial objects can be applied to this problem, such as projective planes and Hadamard matrices.

This is joint work with Karen Meagher and a long list of Spaniards.

Covering designs are a generalisation of t-designs, where the requirement that any t-subset of points be contained in exactly λ blocks is replaced with the weaker requirement that they be contained in at least λ blocks. Covering arrays generalise orthogonal arrays in a similar manner.

In this talk, we show that Peter Cameron's definition of "generalised t-designs" can be modified to provide a common generalisation of covering designs and covering arrays, as well as giving some methods of constructing these new designs. In particular, we focus on the case t = 2, where there is a strong relationship with graph theory, in the form of clique coverings. If time permits, we will also look at a similar notion of "generalised packing designs".

This is joint work with the members of the Discrete Math Research Group at the University of Regina, and also with A. C. Burgess.

A k-uniform hypergraph is like a graph, but where the "edges" are k-sets, rather than pairs, of vertices. There are various ways in which one can define a Hamilton cycle in a hypergraph. Just as with graphs, for each notion of Hamilton cycle, one can ask for a Hamiltonian decomposition of a hypergraph, i.e. a partition of the edge set into Hamilton cycles.

We will focus on one particular notion of Hamilton cycle, and on the complete k-uniform hypergraph, discussing a conjecture which is very natural and easy to state but incredibly hard to solve, but which has been verified in some (very) special cases. This talk includes joint work with B. Stevens, as well as results due to M. Meszka and A. Rosa, and due to J. R. Johnson.

The metric dimension of a graph is a well-studied parameter, which has a number of (real world) applications. It is also interesting from the point of view of the automorphism group of the graph, and (in certain interesting special cases) is equivalent to a previously-known parameter of a permutation group in general.

From this, we are able to translate results from the group theory literature into results about metric dimension. This talk will try to explain how.

The spanning tree packing number of a graph G, denoted σ(G), is the largest number of edge-disjoint spanning trees in G. An obvious upper bound on σ(G) is the edge-connectivity of G. We consider those graphs for which these two parameters are equal, and obtain a constructive description of them. We can also ask an equivalent question for matroids, and will conclude by mentioning this.

This is joint work with Brett Stevens (Carleton) and Mike Newman (Ottawa).

The base size of a permutation group, and the metric dimension of a graph, are both well-known parameters. We discuss these and some other parameters of groups and graphs, show how they are related, and describe how some results previously-unknown in one context can be obtained from the other.

We consider the possible use of permutation groups as error-correcting codes, and give a decoding algorithm which associates a combinatorial object called an uncovering-by-bases (or UBB) with each group. We then state a conjecture, the "single-orbit conjecture", about UBBs which was motivated by reducing the complexity of the decoding algorithm, but is also an interesting conjecture about permutation groups in their own right. Finally, we give a proof of the conjecture in some interesting special cases.

Some results are joint work with Peter Cameron (London).

A covering design is a generalisation of a block design: it is a set of blocks of size k chosen from {1,...,n} where each t-set must be contained in at least one block. An uncovering is closely related: we want a set of blocks which avoid any t-set at least once.

We consider the situation when the blocks of our uncovering have some structure, such as being the basis for a vector space, a base for a permutation group, or a spanning tree for a graph.

We will give the definitions of graph decompositions, factors and factorisations of graphs. We then go to show how a particular kind of graph decomposition (a Hamiltonian decomposition) of the complete graph can be used to construct uncoverings-by-bases for the symmetric group in its action on 2-subsets.

There will be lots of pictures!

Finite geometric groups, that is, finite permutation groups which act transitively on their ordered bases, were classified by Maund in her 1988 D.Phil. thesis. However, this (actually quite useful) classification was lost in the mists of time, seemingly forever. However, thanks to a strange twist of fate (and the government's security services), its secrets can now be revealed. This talk will attempt to do so.

We move away from the traditional setting for error-correcting codes, namely vector spaces over finite fields, and replace these with permutation groups. We draw upon sharply k-transitive groups and the general linear and affine general linear groups (among others) for examples, and describe a decoding algorithm which uses the complements of the blocks of a covering design.

Traditionally, coding theory makes use of linear codes, which are vector spaces over finite fields. We replace these with permutation groups, and show that certain group-theoretic properties (e.g. minimum degree, bases) have some meaning in this setting. We shall draw upon sharply k-transitive groups as well as the general linear and affine general linear groups for examples.

The structure of finite fields is very restricted: it was known to Galois. I will give an explanation of why a finite field has to have prime power order, why for a given prime power a unique finite field exists, and why the multiplicative group of a finite field is cyclic.

Traditionally, the theory of error-correcting codes assumes that errors are the change of one symbol to another. We consider the case where the error is a random permutation of the digits, presenting a decoding method for binary codes and explaining why this doesn't generalise nicely to larger alphabets.

(The abstract for this has gone missing. It was a review of the contents of my MMath project.)

Back to Robert Bailey's homepage

Page last updated 1st May 2011.