• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • No language data
  • Tagged with
  • 1
  • 1
  • 1
  • 1
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

Exploring Agreeability in Tree Societies

Fletcher, Sarah 01 May 2009 (has links)
Let S be a collection of convex sets in Rd with the property that any subcollection of d − 1 sets has a nonempty intersection. Helly’s Theorem states that ∩s∈S S is nonempty. In a forthcoming paper, Berg et al. (Forthcoming) 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 S of convex sets on the space. A society is (k, m)-agreeable if every m-element subset of S has a k-element subset with a nonempty intersection. The agreement number of a society is the size of the largest subset of S with a nonempty intersection. In my work I focus on the case where X is a tree and the convex sets in 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 1 |S | and 3 that the agreement number of (k, k + 1)-agreeable tree societies is at least |S|−1.

Page generated in 0.0734 seconds