Disjoint simplices and geometric hypergraphs. (English) Zbl 0734.05064

Combinatorial mathematics, Proc. 3rd Int. Conf., New York/ NY (USA) 1985, Ann. N. Y. Acad. Sci. 555, 1-3 (1989).
[For the entire collection see Zbl 0699.00014.]
Let A be a set of 2n points in general position in the Euclidean plane \(R^ 2\), and suppose n of the points are colored red and the remaining n are colored blue. A celebrated Putnam problem asserts that there are n pairwise disjoint straight line segments matching the red points to the blue points. To show this, consider the set of all n! possible matchings and choose one, M, that minimizes the sum of lengths l(M) of its line segments. It is easy to show that these line segments cannot intersect. Indeed, if the two segments \(v_ 1,b_ 1\) and \(v_ 2,b_ 2\) intersect, where \(v_ 1,v_ 2\) are two red points and \(b_ 1,b_ 2\) are two blue points, the matching \(M'\) obtained from M by replacing \(v_ 1b_ 1\) and \(v_ 2b_ 2\) by \(v_ 1b_ 2\) and \(v_ 2b_ 1\) satisfies \(l(M')<l(M)\), contracting the choice of M. Our first result in this paper is a generalization of this result to higher dimensions.
Theorem 1: Let A be a set of \(d\cdot n\) points in general position in \(R^ d\), and let \(A=A_ 1\cup A_ 2\cup..>\cup A_ d\) be a partition of A into d pairwise disjoint sets, each consisting of n points. Then there are n pairwise disjoint (d-1)-dimensional simplices, each containing precisely one vertex from each \(A_ i\), \(1\leq i\leq d.\)
We prove this theorem in the next section. The proof is short but uses a non-elementary tool: the well-known Borsuk-Ulam theorem.
Combining Theorem 1 with an old result of Erdős from extremal graph theory we obtain a corollary dealing with geometric hypergraphs. A geometric d-hypergraph is a pair \(G=(V,E)\), where V is a set of points called vertices, in general position in \(R^ d\), and E is a set of (closed) (d-1)-dimensional simplices called edges, whose vertices are points of V. If \(d=2\), G is called a geometric graph. It is well known that every geometric graph with n vertices and \(n+1\) edges contains two disjoint edges, two nonintersecting edges, and this result is the best possible. The number of edges that guarantees l pairwise disjoint edges is not known for \(l>2\).


05C65 Hypergraphs
05C35 Extremal problems in graph theory


Zbl 0699.00014