Over the last thirty years $k$-cycle systems have received an increasing amount of attention. In spite of this, the obvious necessary conditions for their existence were proven to be also sufficient quite recently. This important result is due to Alspach and Gavlas in the odd case and to \v Saina in the even case.

In this talk we give a survey on very recent results about $k$-cycle systems admitting a cyclic automorphism group acting sharply transitively on the vertices $k$-cycle systems or fixing one vertex and acting sharply transitively on the others $1$-rotational $k$-cycle systems.

We illustrate, in particular, a result according to which for $k$ odd and any admissible $v<3k$ there exists a $k$-cycle system of order $v$ that is either cyclic or $1$-rotational. This, in view of a well known result by Hoffman, Lindner and Rodger, may also be viewed as an alternative proof of the theorem of Alspach and Gavlas mentioned above.

Bibliography

B. Alspach and H. Gavlas, Cycle decompositions of $K_n$ and $K_n-I$, J. Combin. Theory Ser. B, 81 (2001), 77-99.

M. Buratti, 1-rotational $k$-systems of order $v<3k$; an alternative proof of the existence of odd cycle systems, J. Combin. Des., to appear.

D.G. Hoffman, C.C. Lindner and C.A. Rodger, On the construction of odd cycle systems, J. Graph Theory, 13 (1989), 417-426.

M. \v Sajna, Cycle decompositions III: Complete graphs and fixed length cycles}, J. Combin. Des., 10 (2002), 27-78.

A Class-Uniformly Resolvable Design (CURD) is a resolvable pairwise balanced design, with multiple block sizes, in which each of the esolution classes has the same number of blocks of each size. These designs are related to many well known classes of designs.

In this talk we investigate the necessary conditions for the existence of Class-Uniformly Resolvable Designs with block sizes two and three. A CURD on $v$ points has $r$ resolution classes and each class contains $p_2$ blocks of size 2 and $p_3$ blocks of size 3. We will see how these necessary conditions give rise to some unexpected extremal bounds on $v$ for given values of either $p_2$, or $p_3$.

A Class-Uniformly Resolvable Design with block sizes two and three can be characterised by the four (interelated) parameters $(v, r, p_2, p_3)$. A classification of which parameter sets are permissable has proved elusive, we will show how a standard frame construction leads to a complete characterisation of admissable parameter sets.

In this talk I will discuss two different problems that I have been interested in lately. The first is a problem in graph theory. A fire breaks out at a node at time 0. At each time period a firefighter (or several firefighters) can be placed at a node of the graph that it protects for all subsequent time periods. All unprotected nodes that are adjacent to burning nodes catch on fire at each time period. We discuss several questions concerning firefighting on the rectangular grid graph.

The second topic concerns the enumeration of balanced tournament designs (BTDs) of order 10. These are arrangements of the 45 pairs of elements from a 10 set into the cells of a 5 x 9 array in such a way that each symbol occurs exactly once in each column and at most twice in each row. In 1988 it was determined that there are exactly 47 nonisomorphic BTDs on 8 points. We have found that there are precisely 30,220,557 nonisomorphic BTDs on 10 points. We will give a short discussion of the techniques used to determine this value.

The (Hamming) distance between two permutations on the same symbol set is the number of positions in which they differ. A permutation code (or permutation array) with length `n' and minimum distance `d' is a collection of permutations on a symbol set of size `n' such that the distance between any two distinct members of this collection is at least `d'. Finding large permutation codes is of some interest for powerline communication.

In this talk, I will mention a variety of old and new constructions of permutation codes. In particular, a recursive construction of permutation codes using resolvable designs (or packings) will be presented. The performance of maximum clique searching to this problem will also be discussed.

A $\lambda$-fold kite system is a pair $(X, K)$, where K is a collection of edge disjoint kites which partitions the edge set of $ \lambda$$K_n $ with vertex set X. A $\lambda$-fold $4$-cycle system is a pair $(X, C)$, where C is a collection of edge disjoint $4$-cycles which partitions the edge set of $\lambda$$K_n$ with vertex set X. If $(X,B)$ is a $3$-fold block design, $(X,K)$ a $2$-fold kite system, and $(X,C)$ a $2$-fold $4$-cycle system of order n, then $ |B| =n(n-1)/4=|K|=|C|$. We can ask: for which n does there exist a 3-fold block design $(X,B)$ with the property that a kite [$4$-cycle] can be selected from each block in B so that the resulting collection of kites K [$4$-cycles C] is a $2$-fold kite system $(X,K)$ [$4$-cycle system $ (X,C)$] of order n? As with Steiner triple systems, the $2$-fold kite system [4-cycle system ] is said to be nested in the $3$-fold block design $(X,B)$. In general we will say that the $ \lambda_1$-fold kite system $(X,K)$ is nested in the $\lambda_2$-fold block design $(X,B)$ provided a kite can be selected from each of B so that the resulting collection of kites is K. We have the same definition for the nesting of a $\lambda_1$-fold $4$-cycle system $(X,C)$. Now if the $\lambda_1$-fold kite system $(X,K)$ [$\lambda_1$-fold $4$-cycle system $(X,C)$] can be nested in the $\lambda_2$-fold block design $(X,B)$, then $\lambda_2n(n-1)/12=|B|=|K|=|C|= \lambda_1n(n-1)/8$ implies $\lambda_1= 2k$ and $\lambda_2= 3k$. Hence the general problem of " the nesting for kites and $4$-cycles". We give a complete solution of nesting problem for $ 2k$-fold kite [$4$-cycle] systems.

D.R. Stinson, The spectrum of nested Steiner triple systems, Graphs and Combinatorics, 1985, 189-191.

Given a polygon P, the visibility graph of P is the graph whose vertices are the vertices of P with two vertices connected by an edge if they are visible in P, that is, if the line segment between them lies inside P. This problem touches many areas and related problems that are "difficult" in the computational sense. This talk will provide a basic introduction the problem of recognizing/characterizing visibility graphs and further describe our current research in a special, fundamental, case of the problem, staircase polygons, specifically realizing a staircase polygon from its visibility graph via group theoretic operations in the Weak Bruhat Order.

The typical graph-decomposition problem asks if the edges of the complete graph on n vertices can be partitioned into copies of a given graph G. What if we don't specify G, but rather just specify the number b of copies of G in the decomposition? (For example, if b = 2, we're asking for a self-complementary graph on n vertices.) We give a simple solution to this problem, and also the corresponding problem for indices other than one.

Let S be a finite set of nonzero points in d-dimensional space. Then S is a simplex if it is minimal such that 0 is in the convex hull of S. A hypergraph is d-embeddable if there exists a mapping from its vertex set into d-dimensional space such that every hyperedge is a simplex. In this talk we describe what is known about which hypergraphs are d-embeddable for d = 1, 2.

A rank 3 combinatorial geometry (simple matroid) consists of a set of points and a family of distinguished subsets of points called lines that satisfy two properties: any two distinct points belong to exactly one line; and any line has at least two distinct points. A geometry is said to be representable over a finite field GF(q), where q is a power of a prime, if there is a rank preserving map from the elements of the geometry to a matrix with entries from GF(q). We show how to use automated matroid generation to study the representability problem for rank 3 geometries. We verify that up to 9 elements all except four rank 3 geometries are representable and the bound on the order of the field is 11.

Suppose we have a necklace with 2n beads of k different colors, 2ai beads of color i. The necklace bisection problem is to find the smallest number of strings into which a necklace can be cut so that it is then possible to divide the strings into two groups with equal number of beads of every color in each group. Although an exponential in k algorithm for making these cuts is known, the existence of an algorithm polynomial in or independent of k is a long-standing open problem and the subject of my presentation.

It this talk, I will describe how to construct CCRRSs, complete coupling round robin schedules, for $n$ teams each consisting of two pairs. The motivation for these schedules is a problem in scheduling bridge tournaments. For $n$ odd, we show that a CCRRS can be constructed using a house with special properties. For $n$ even, a CCRRS is equivalent to a Howell design, $H(2n-2,2n)$, with a special property called Property P. We use a combination of direct and recursive constructions to construct $H(2n-2,2n)$ with Property P. In order to apply our main recursive construction, we need group divisible designs with both odd block and odd group size. One of our main results is the existence of these GDDs. This is joint work with Alan Ling and Gennian Ge.

An m-cycle system of order n is a pair (X,C), where C is a collection of edge disjoint m-cycles which partitions the edge set of K_n with vertex set X. Given an m-cycle system we can define a groupoid (X,o) as follows: (i) x o x = x for all x in X, and (ii) if x =/ y, x o y = z and y o x = w if and only if the cycle (....,w,x,y,z,....) belongs to C. It is well-known that the groupoid (X,o) is a quasigroup if and only if the m-cycle system (X, C) is 2-perfect. (2-perfect means that each pair of vertices are connected by a path of length 2 in exactly one m-cycle of C.) This is an elementary survey of results on constructing quasigroups from 2-perfect m-cycle systems.

In this talk, we present a result on resolvable packings with block size 4. Particular attention will be given on the direct constructions aspect of this problem. As a result of direct and recursive constructions, it is shown that there are at most 18 possible exceptions for resolvable packings with block size four.

Covering arrays are a type of design with many applications. Like most interesting designs they can be difficult to build. In this talk I will give a construction for strength 2 covering arrays based on an algebraic method of Chateauneuf, Colbourn and Kreher. This construction uses a subarray of a covering array and a group action on that subarray. With this construction we can improve the best known upper bounds on the size of many covering arrays 2-CA(n,k,g) with k between g and 2g.

This talk presents last new vertex colourings of Steiner systems S(t,k,v), for t = 2, k = 3 or 4, and for t = 3, k = 4, respect different block colour patterns. New concepts such as upper chromatic number, uncolourability, chromatic spectrum, will be shown.

Covering arrays are generalizations of orthogonal arrays useful for testing systems such as software, networks and circuits. Each parameter of the system corresponds to a row of the array and each test to be performed on the system correspond to a column; the covering array property requires that every possible pair of values for any pair of parameters is covered by some test. A covering array is said to be mixed if each row may take values from different alphabet sizes. In this talk, we present results and constructions for mixed covering arrays.

We discuss some properties and an application of yet another class of graphs whose smallest member is the Petersen graph. These graphs, which we call extended Petersen graphs, arise naturally in the context of a construction of Steiner systems S(2,4,v) with maximal arcs but seem to be interesting on their own.

Packing arrays are the natural generalizations of orthogonal arrays, or transversal designs, to packing criteria. We will discuss their definition, construction and bounds on their size. Additionally we will discuss their applications to disk arrays and their relationship to other families of designs including CURDS, packing designs and finite projective planes.

A $t$-fold $(N-k)$-blocking set in the projective space $PG(N,q)$ of dimension $N$ over the finite field of order $q$ is a set of points intersecting every $k$-dimensional subspace in at least $t$ points. A $t$-fold $(N-k)$-blocking set is called minimal when none of its proper subsets is still a $t$-fold $(N-k)$-blocking set.

We present new characterization results on minimal $t$-fold $(N-k)$-blocking sets in $PG(N,q)$, $N \geq 3$, $q=p^h$, $p$ prime, $h \geq 1$. The most important part in obtaining these characterization results is the fact that, presently, for $t$-fold $(N-k)$-blocking sets, of not too large cardinality, a so-called $t$ mod $p$ result is known. This result gives crucial information on the intersection sizes of these blocking sets with the subspaces of $PG(N,q)$, leading to the characterization results.

In this talk I will introduce the notion of the ultimate independence ratio of a graph and present an open problem (UIR of odd wheels). I will also mention a few results relevant to this problem.

A triple array A is an array with r rows and c columns, based on a set V, having the following properties:

(P1) no element is repeated in any row or column;

(P2) any member of V occurs k times in the array, for some constant k;

(P3) any two distinct rows have the same number of common elements;

(P4) any two distinct columns have the same number of common elements.

(P5) any row and any column have the same number of common elements.

We shall discuss triple arrays. In particular, we prove various constraints on the parameters, and report on the existence of these arrays.

The Open University presents the half-credit (30 point) course MT365 Graphs, Networks and Design annually to over seven hundred students. This is a problems-based course, presented in a down-to-earth manner, and is intended for a wide audience. The course evolved from separate plans in the Pure Mathematics Department and the Design Group of the Technology Department to produce combinatorics-based courses. The resulting joint venture continues with an inter-departmental team up keeping and presenting the course.

Open University students are adults, mostly in full-time employment, who are studying part-time. They live around the UK and elsewhere. Their backgrounds and experience are diverse?some students studying mathematics courses have no formal mathematics education prior to embarking with the Open University, while others may have had considerable experience.

The course MT365 is intended for highly motivated students who do not necessarily have a strong mathematical background. The course is popular with mathematicians, technologists, scientists and computer scientists alike. The emphasis is on solving problems and applying algorithms, rather than understanding proofs; it is very much a "doing" course. The development of combinatorics as a subject is integrated with the modelling of practical situations.

In my talk I will discuss this course in more detail; how it was developed, the topics covered, the method of presentation and the ideas behind it.