Disjoint G-Designs and the Intersection Problem for Some Seven Edge Graphs

Abstract

A $G$-Design of order $n$ is a decomposition of the edges of $K_n$ (the complete graph on $n$ vertices) into subgraphs of $K_n$ isomorphic to $G$, called blocks, in which each edge of $K_n$ appears in exactly one block. If $\mathcal{B}_{1}$ and $\mathcal{B}_{2}$ are arbitrary block sets corresponding to two $G$-designs of order $n$, one might ask under what circumstances can a $G$-design $\mathcal{B}_{2}'$ of order $n$ be found such that $\mathcal{B}_{2}$ and $\mathcal{B}_{2}'$ are isomorphic and $\mathcal{B}_{1}$ and $\mathcal{B}_{2}'$ are disjoint. Luc Teirlinck found that if $\mathcal{B}_{1}$ and $\mathcal{B}_{2}$ are $K_{3}$-designs of order $n$, then such a design $\mathcal{B}_{2}'$ can be found for all $n\geq{7}$. In the first part of this dissertation, a similar result is shown for all graphs $G$ with the exception of four small graphs (i.e. some graphs with less than $5$ vertices and $3$ edges). That is, if $\mathcal{B}_{1}$ and $\mathcal{B}_{2}$ is a pair of arbitrary $G$-designs of order $n$, then there is a $G$-design $\mathcal{B}_{2}'$ such that $\mathcal{B}_{2}$ and $\mathcal{B}_{2}'$ are isomorphic and $\mathcal{B}_{1}$ and $\mathcal{B}_{2}'$ are disjoint provided $n$ is sufficiently large.

The remainder of the dissertation focuses on the intersection problem for some selected graphs $G$. The intersection problem is concerned with determining the positive integer pairs $n$,$k$ for which there are $G$-designs $\mathcal{B}_{1}$ and $\mathcal{B}_{2}$ of order $n$ such that $|\mathcal{B}_{1} \cap \mathcal{B}_{2}|=k$. In a landmark result, C.C. Lindner and A. Rosa solved the intersection problem for Steiner Triple Systems (which are $K_{3}$-designs). Since then the intersection problem has been solved for various combinatorial designs among which are cycle systems where the cycles have length less than $10$, star designs, and various other simple connected graphs with no more than $6$ edges. The results presented here solve the intersection problem for $7$ bipartite graphs each of which has exactly $7$ vertices and $7$ edges.