Premium
Morris's pigeonhole principle and the Helly theorem for unions of convex sets
Author(s) -
Eckhoff Jürgen,
Nischke KlausPeter
Publication year - 2009
Publication title -
bulletin of the london mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 2.396
H-Index - 48
eISSN - 1469-2120
pISSN - 0024-6093
DOI - 10.1112/blms/bdp024
Subject(s) - pigeonhole principle , disjoint sets , mathematics , conjecture , regular polygon , combinatorics , extension (predicate logic) , discrete mathematics , computer science , geometry , programming language
In 1973, H. C. Morris devised a combinatorial scheme, a ‘generalized pigeonhole principle’, which he used to prove a conjecture of Grünbaum and Motzkin from 1961. This conjecture proposed, in an abstract setting, a Helly‐type theorem for certain families of disjoint unions of sets. A geometric instance dealing with disjoint unions of convex sets in ℝ d was proved in a special case by Larman in 1968 and in the general case by Amenta in 1996. Also covered by the conjecture is a topological extension of Amenta's theorem obtained by Kalai and Meshulam in 2008. Morris's proof of the generalized pigeonhole principle is extremely involved, and the validity of some of his arguments is open to dispute. In the present paper, the principle is placed on a sound basis and established in a relatively short and transparent manner. This includes a particular case, left open by Morris, which is applied here to families of disjoint unions of boxes in ℝ d .