On (2,3)-agreeable box societies

Abrahams, Michael; Lippincott, Meg; Zell, Thierry

doi:10.2140/involve.2010.3.93

Download this article
	For screen
	For printing

Recent Issues

The Journal

About the journal

Ethics and policies

Peer-review process

Submission guidelines

ISSN 1944-4184 (online)

ISSN 1944-4176 (print)

Author index

To appear

Other MSP journals

On $(2,3)$-agreeable box societies

Michael Abrahams, Meg Lippincott and Thierry Zell

Vol. 3 (2010), No. 1, 93–108

DOI: 10.2140/involve.2010.3.93

Abstract

The notion of a $(k, m)$ -agreeable society was introduced by Berg, Norine, Su, Thomas and Wollan: a family of convex subsets of $ℝ^{d}$ is called $(k, m)$ -agreeable if any subfamily of size $m$ contains at least one nonempty $k$ -fold intersection. In that paper, the $(k, m)$ -agreeability of a convex family was shown to imply the existence of a subfamily of size $β n$ with a nonempty intersection, where $n$ is the size of the original family and $β \in [0, 1]$ is an explicit constant depending only on $k$ , $m$ and $d$ . The quantity $β (k, m, d)$ is called the minimal agreement proportion for a $(k, m)$ -agreeable family in $ℝ^{d}$ .

If we assume only that the sets are convex, simple examples show that $β = 0$ for $(k, m)$ -agreeable families in $ℝ^{d}$ where $k < d$ . In this paper, we introduce new techniques to find positive lower bounds when restricting our attention to families of $d$ -boxes, that is, cuboids with sides parallel to the coordinates hyperplanes. We derive explicit formulas for the first nontrivial case: $(2, 3)$ -agreeable families of $d$ -boxes with $d \geq 2$ .

Keywords

boxicity, arrangements of boxes, agreement proportion, voting, Helly's theorem

Mathematical Subject Classification 2000

Primary: 52C45

Secondary: 91B12

Milestones

Received: 25 August 2009

Revised: 27 January 2010

Accepted: 9 February 2010

Published: 20 April 2010

Communicated by Arthur T. Benjamin

Authors

Michael Abrahams
Vassar College Poughkeepsie, NY 12604 United States

Meg Lippincott
Vassar College Poughkeepsie, NY 12604 United States

Thierry Zell
The Donald and Helen Schort School of Mathematics and Computing Sciences Lenoir-Rhyne University Hickory NC 28603 United States
http://mat.lr.edu/faculty/zell

Vol. 3, No. 1, 2010