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

Metadata Field | Value | Language |
---|---|---|

dc.contributor.advisor | Hoffman, Dean | |

dc.contributor.author | Hollis, Daniel | |

dc.date.accessioned | 2017-04-21T13:37:03Z | |

dc.date.available | 2017-04-21T13:37:03Z | |

dc.date.issued | 2017-04-21 | |

dc.identifier.uri | http://hdl.handle.net/10415/5665 | |

dc.description.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. | en_US |

dc.subject | Mathematics and Statistics | en_US |

dc.title | Disjoint G-Designs and the Intersection Problem for Some Seven Edge Graphs | en_US |

dc.type | PhD Dissertation | en_US |

dc.embargo.status | NOT_EMBARGOED | en_US |

dc.contributor.committee | Johnson, Peter | |

dc.contributor.committee | McDonald, Jessica | |

dc.contributor.committee | Rodger, Chris |