Sarah Fletcher
Harvey Mudd College Mathematics 2009
| Final Thesis: | Exploring Agreeability in Tree Societies |
|---|---|
| Thesis Proposal: | Agreeability on Various Classes of Graphs |
| Thesis Advisor: | Prof. Francis E. Su |
| Second Reader: | Prof. Kimberly Tucker |
Exploring Agreeability in Tree Societies
Let $\mathcal{S}$ be a collection of convex sets in $\mathbb{R}^d$ with the property that any subcollection of $d-1$ sets has a nonempty intersection. Helly's Theorem states that $\cap_{s\in\mathcal{S}} \mathcal{S}$ is nonempty. In a forthcoming paper, \cite{berg} interpret the one-dimensional version of Helly's Theorem in the context of voting in a society. They look at the effect that different intersection properties have on the proportion of a society that must agree on some point or issue. In general, we define a society as some underlying space $X$ and a collection $\mathcal{S}$ of convex sets on the space. A society is $(k,m)$-agreeable if every $m$-element subset of $\mathcal{S}$ has a $k$-element subset with a nonempty intersection. The agreement number of a society is the size of the largest subset of $\mathcal{S}$ with a nonempty intersection.
In my work I focus on the case where $X$ is a tree and the convex sets in $\mathcal{S}$ are subtrees. I have developed a reduction method that makes these tree societies more tractable. In particular, I have used this method to show that the agreement number of $(2,m)$-agreeable tree societies is at least $\frac{1}{3}|\mathcal{S}|$ and that the agreement number of $(k,k+1)$-agreeable tree societies is at least $|S|-1$.