Combinatorial generalizations of Jung's theorem (Q1953063): Difference between revisions

The famous theorem of Jung states that any set with diameter 1 in \(\mathbb {R}^d\) can be covered by a ball of radius \(\mathrm{R}_d = \sqrt{\frac{d}{2(d + 1)}}\). In this paper, using a well-known combinatorial variant of the Helly theorem, due to \textit{M. Katchalski} and \textit{A. Liu} [Proc. Am. Math. Soc. 75, 284--288 (1979; Zbl 0418.52013)], the author proves the following fractional version of Jung's theorem: For every \(d\geq 1\) and every \(\alpha \in (0, 1]\) there exists a \(\beta = \beta(d, \alpha) > 0\) with the following property: If \(\mathcal{V}\) is an \(n\)-point set in \(\mathbb {R}^d\) such that \(\|x - y\| \leq 1\) for at least \(\alpha C_n^2\) pairs \(\{x, y\}\) of distinct points from \(\mathcal{V}\), then there exists a ball of radius \(\mathrm{R}_d\) which covers \(\beta n\) points of \(\mathcal{V}\). Moreover \(\beta \rightarrow 1\) when \(\alpha \rightarrow 1\). Two nonempty subsets \(\mathcal{V}_1\) and \(\mathcal{V}_2\) of \(\mathbb {R}^d\) are said to be close if for any \(x\in \mathcal{V}_1\) and \(y\in \mathcal{V}_2\), \(\|x - y\| \leq 1\). The following colorful version of Jung's theorem is the second main result of the paper: If \(\mathcal{V}_1\), \(\mathcal{V}_2, \dots, \mathcal{V}_n\) are pairwise close sets in \(\mathbb{R}^d\), then one of them can be covered by a ball of radius \(\mathrm{R}\), where \[ \mathrm{R} = \frac{1}{\sqrt{2}} \text{ if }\; n \leq d, \] \[ \mathrm{R}_d = \sqrt{\frac{d}{2(d + 1)}} \text{ if }\; n > d. \]