Atlantic Graph Theory Seminar

Speaker: Andrea Burgess, University of New Brunswick

Title: Colourings of combinatorial designs

Abstract: A combinatorial design is a pair $(V,\mathcal{B})$ where $V$ is a nonempty set of points, and $\mathcal{B}$ is a collection of subsets of $\mathcal{B}$, called blocks.  A $c$-colouring of a design $(V,\mathcal{B})$ is a function $f:V \rightarrow C$, where $C$ is a set of $c$ colours, such that each block contains at least two points of different colours.  The design’s chromatic number is the least value of $c$ for which it admits a $c$-colouring.  While colourings of balanced incomplete block designs and cycle systems have been extensively studied, relatively little is known regarding colourings of designs with restricted structural properties, such as resolvability, or colourings of certain other classes of designs, such as group divisible designs.  In this talk, we aim to bridge this gap.

We start by considering colourings of Kirkman triple systems (KTS), which are resolvable Steiner triple systems.  We show that there is a $3$-chromatic KTS$(v)$ if and only if $v \equiv 3$~(mod~$6$), and construct infinite families of $c$-chromatic KTS$(v)$ for every integer $c \geq 4$.

We then extend the study of colourings to group divisible designs (GDDs).  In a GDD, the points are partitioned into groups; no block contains more than one point from any group, but each pair of points not in the same group appears in exactly $\lambda$ blocks.  We consider the existence of uniform GDDs with arbitrary group size and arbitrary chromatic number $c$, and further discuss colourings of GDDs with additional restrictions on the colours appearing in each group.

If time permits, we will mention some results on equitable colourings of group divisible designs and packing designs; in this type of colouring, each colour must appear an equal number of times (or as closely as possible) in each block.

This talk contains joint work with Nicholas Cavenagh, Peter Danziger, Diane Donovan, Tara Kemp, James Lefevre, David Pike and E. \c{S}ule Yaz{\i}c{\i}.

Zoom link:

Meeting ID: 880 1326 1876