A Collection of Results of Simonyi's Conjecture

Date

2012-12-17

Authors

Styner, Dustin

Journal Title

Journal ISSN

Volume Title

Publisher

University of Guelph

Abstract

Given two set systems A and B over an n-element set, we say that (A,B) forms a recovering pair if the following conditions hold: \ $ \forall A, A' \in \mathscr{A}$ and $ \forall B, B' \in \mathscr{B}$, A∖B=A′∖B′⇒A=A′ \ $ \forall A, A' \in \mathscr{A}$ and $ \forall B, B' \in \mathscr {B}$, B∖A=B′∖A′⇒B=B′ \ In 1989, G'{a}bor Simonyi conjectured that if (A,B) forms a recovering pair, then |AB|≤2n. This conjecture is the focus of this thesis. This thesis contains a collection of proofs of special cases that together form a complete proof that the conjecture holds for all values of n up to 8. Many of these special cases also verify the conjecture for certain recovering pairs when n>8. We also present a result describing the nature of the set of numbers over which the conjecture in fact holds. Lastly, we present a new problem in graph theory, and discuss a few cases of this problem.

Description

Keywords

Combinatorics, Set Theory, Extremal Combinatorics, Graph Theory

Citation