Given two set systems and over an -element set, we say that forms a recovering pair if the following conditions hold: \ $ \forall A, A' \in \mathscr{A}$ and $ \forall B, B' \in \mathscr{B}$, \ $ \forall A, A' \in \mathscr{A}$ and $ \forall B, B' \in \mathscr {B}$, \ In 1989, G'{a}bor Simonyi conjectured that if forms a recovering pair, then . 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 up to 8. Many of these special cases also verify the conjecture for certain recovering pairs when . 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