A theorem on independence

✍ Scribed by Daniel Q. Naiman; Henry P. Wynn

• Publisher: Elsevier Science
• Year: 1993
• Tongue: English
• Weight: 161 KB
• Volume: 120
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(93)90589-l

✦ Synopsis

Suppose we are given a family of sets W= {S(j), jgJ}, where S(j)= n;=, Hi( j), and suppose each collection of sets H,(j,), . . . . H,(j,+,) has a lower bound under the partial ordering defined by inclusion, then the maximal size of an independent subcollection of 'Z is k. For example, for a fixed collection of half-spaces H, , , Hk in W', we define V to be the collection of all sets of the form where xi, i = 1, _. , k are points in [Wd. Then the maximal size of an independent collection of such sets us k. This leads to a proof of the bound of 2d due to Renyi et al. (1951) for the maximum size of an independent family of rectangles in [W" with sides parallel to the coordinate axes, and to a bound of d + 1 for the maximum size of an independent family of simplices in [W" with sides parallel to given hyperplanes H, , , H,, 1.