Topic: Combinatorial Design Theory
July 13 - 18, 2003

All lectures will be give in the first floor auditorium.


Frank Bennett
Mount Saint Vincent University

A Survey of Steiner Pentagon Packing and Covering Designs

Let K denote the complete undirected graph on n vertices. A Steiner pentagon system (SPS) of order n is a pair (K, B), where B is a collection of edge-disjoint pentagons which partition K, and such that every pair of distinct vertices of K is joined by a path of length two in exactly one pentagon of B. A Steiner pentagon packing (covering) of order n is a pair (K, B), where B is a collection of pentagons from K such that any two vertices are joined by a path of length one in at most (at least) one pentagon of B, and also by a path of length two in at most (at least) one pentagon of B. If no other such packing (covering) has more (fewer) pentagons, the packing (covering) is said to be maximum (minimum) and the number of pentagons in a maximum packing (a minimum covering) is called the packing number (the covering number), denoted by p(n) (c(n)). We shall present a brief survey of the results relating to the determination of the values of p(n) and c(n) and mention some open problems. For the most part, the main results have been established on the strength of the existence of certain types of holey Steiner pentagon systems (HSPSs), which are of interest in their own right.

Marco Buratti
Universita di Perugia

A survey on cyclic or $1$-rotational $k$-cycle systems

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.


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.

Peter Danziger
Ryerson University

A characterisation of Class-Uniformly Resolvable Designs

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.

Jeff Dinitz
University of Vermont

Firefighting and Enumerating Balanced Tournament Designs

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.

Peter Dukes
Arizona State University

Designs and permutation codes

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.

Heather Gavlas
Illinois State University

Cycles Systems in the Complete Bipartite Graph Minus a One-Factor

Let $K_{n,n}-I$ denote the complete bipartite graph with $n$ vertices in each part from which a 1-factor $I$ has been removed. An $m$-cycle system of $K_ {n,n}-I$ is a collection of $m$-cycles whose edges partition $K_{n,n}-I$. Necessary conditions for the existence of a $m$-cycle system of $K_{n,n}-I$ are that $m \ge 4$ is even, $n \ge 3$ is odd, $m \le 2n$, and $m | n(n-1)$. In this talk, we show these necesssary conditions are sufficient except possibly in the case that $m$ is congruent to $0$ modulo $4$ with $ n < m < 2n$.

Lucia Gionfriddo
Universita degli Studi di Catania

Nesting Kite and 4-cycle systems
(Joint work with Curt Lindner)

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.

Vishal Gupta
Yale University
Advisor: James Abello, DIMACS

Realizing Simple Polygons from Visibility Graphs

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.

Dean Hoffman
Auburn University

A Curiously Different Sort of Graph-Decomposition Problem

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.

Steven Jaslar
Rutgers University
Advisors: Vladimir A. Gurvich and Khaled Elbassioni, RUTCOR,and William Cuckler, Mathematics, Rutgers University

d-embeddablity of Hypergraphs

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.

Jonathan Jedwab
University of Richmond

Designing the IEEE 802.12 transmission code

In 1993 S Crouch and I designed a coding scheme for 100 Mbit/s data transmission over copper telephone cabling. This scheme satisfied physical, economic and social constraints, allowing a tenfold increase in transmission speed whilst maintaining error detection capability. In 1995 the Institute of Electrical and Electronic Engineers (IEEE) approved this coding scheme as part of its 802.12 international standard for data transmission. For many years commercial considerations prevented us from revealing the design principles underlying the code structure. However I now have permission to explain how geometrical insight, combinatorial reasoning, and computer search were combined to satisfy all the imposed constraints simultaneously.

Sandra Kingan
Penn State University, Harrisburg

Representability of rank 3 combinatorial geometries

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.

Victor Kostyuk
Rochester Institute of Technology
Advisor: Michael Capalbo, DIMACS

Colored Necklace Bisection

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.

Esther Lamken

Scheduling CCRR tournaments

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.

Curt Lindner
Auburn University

Constructing Quasigroups from Cycle Systems

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.

Alan Ling
University of Vermont

On resolvable packings with block size four
(Joint work with Gennian Ge. Shen Hao and Clement Lam)

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.

Sasha Logan
Auburn University

Maximal Sets of Hamilton Cycles

A set S of edge-disjoint hamilton cycles in a graph T is said to be maximal if the hamilton cycles in S form a subgraph of T such that T-E(S) has no hamilton cycle. The spectrum of a graph T is the set of integers m such that T contains a maximal set of m edge-disjoint hamilton cycles. This spectrum has previously been determined for all complete graphs, all complete bipartite graphs, and most complete multipartite graphs. In this paper we solve one of the two unsolved cases for complete multipartite graphs, giving two substantially different proofs.

Karen Meagher
University of Ottawa

A Construction for Covering arrays

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.

Lorenzo Milazzo
Universita di Catania

New colourings for Steiner systems with different block colour patterns

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.

Lucia Moura
University of Ottawa

Mixed Covering Arrays
(Joint work with John Stardom, Brett Stevens and Alan Williams)

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.

Alexander Rosa
McMaster University

Extended Petersen graphs
PowerPoint Presentation

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.

Brett Stevens
Carleton University

Packing arrays and related designs

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.

Leo Storme
Ghent University

Blocking sets in projective spaces

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.

Ida Svejdarova
Charles University
Advisor: Jozsef Beck, Mathematics, Rutgers University

Ultimate Independence Ratio of Wheels

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.

Walter Wallis
Southern Illinois University

Triple Arrays

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.

Bridget Webb
The Open University

Teaching Combinatorics to 700 Students per Year

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.

Page last updated July 8, 2003.