Sarah Fletcher

Harvey Mudd College Mathematics 2009

mugshot
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$.