Return to search

A Collection of Results of Simonyi's Conjecture

Given two set systems $\mathscr{A}$ and $\mathscr{B}$ over an $n$-element set, we say that $(\mathscr{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 \setminus B = A' \setminus B' \Rightarrow A=A'$
\\
$ \forall A, A' \in \mathscr{A}$ and $ \forall B, B' \in \mathscr {B}$, $B \setminus A = B' \setminus A' \Rightarrow B=B'$
\\
In 1989, G\'bor Simonyi conjectured that if $(\mathscr)$ forms a recovering pair, then $|\mathscr||\mathscr|\leq 2^n$. 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.

Identiferoai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:OGU.10214/4926
Date17 December 2012
CreatorsStyner, Dustin
ContributorsPereira, Rajesh, McNicholas, Paul
Source SetsLibrary and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada
LanguageEnglish
Detected LanguageEnglish
TypeThesis
Rightshttp://creativecommons.org/licenses/by-nc-nd/2.5/ca/

Page generated in 0.0018 seconds