Main content

A Collection of Results of Simonyi's Conjecture

Show simple item record

dc.contributor.advisor Pereira, Rajesh
dc.contributor.advisor McNicholas, Paul
dc.contributor.author Styner, Dustin
dc.date.accessioned 2012-12-17T19:22:12Z
dc.date.available 2012-12-17T19:22:12Z
dc.date.copyright 2012-12
dc.date.created 2012-12-11
dc.date.issued 2012-12-17
dc.identifier.uri http://hdl.handle.net/10214/4926
dc.description.abstract 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\'{a}bor Simonyi conjectured that if $(\mathscr{A,B})$ forms a recovering pair, then $|\mathscr{A} en_US
dc.description.abstract \mathscr{B}|\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. en_US
dc.language.iso en en_US
dc.rights.uri http://creativecommons.org/licenses/by-nc-nd/2.5/ca/ *
dc.subject Combinatorics en_US
dc.subject Set Theory en_US
dc.subject Extremal Combinatorics en_US
dc.subject Graph Theory en_US
dc.title A Collection of Results of Simonyi's Conjecture en_US
dc.type Thesis en_US
dc.degree.programme Mathematics and Statistics en_US
dc.degree.name Master of Science en_US
dc.degree.department Department of Mathematics and Statistics en_US
dc.rights.license All items in the Atrium are protected by copyright with all rights reserved unless otherwise indicated.


Files in this item

Files Size Format View
Styner_Dustin_201212_MSc.pdf 288.9Kb PDF View/Open

This item appears in the following Collection(s)

Show simple item record

http://creativecommons.org/licenses/by-nc-nd/2.5/ca/ Except where otherwise noted, this item's license is described as http://creativecommons.org/licenses/by-nc-nd/2.5/ca/