Speaker: Alan C.H. Ling University of Vermont
Time and Place: 18 Nov. 2005, 12:00
noon, HP4351, Herzberg building,
Carleton University
Title: The existence of resolvable graph designs
Abstract:
Let v >= k and m be positive integers. A block design BD(v,k,m) is a collection A of k-subsets
of a v-set X in which every unordered pair of elements from X is contained in exactly m elements of A.
More generally, for a fixed simple graph G, a graph design GD(v,G,m) is a collection A of graphs isomorphic
to G with vertices in X such that every unordered pair of elements from X is an edge of exactly m elements
of A. A famous result of Wilson says that for a fixed G and m, there exists a GD(v,G,m) for all sufficiently large
v satisfying certain necessary conditions. A block (graph) design as above is said to be resolvable if A can be
partitioned into partitions of (graphs whose vertex sets partition) X. Lu has shown asymptotic existence of resolvable
BD(v,k,m), yet for over twenty years the analogous problem for resolvable GD(v,k,m) has remained open. In this
paper, we settle asymptotic existence of resolvable graph designs.