Abstract
Bárány, Katchalski and Pach (Proc Am Math Soc 86(1):109–114, 1982) (see also Bárány et al., Am Math Mon 91(6):362–365, 1984) proved the following quantitative form of Helly’s theorem. If the intersection of a family of convex sets in \(\mathbb {R}^d\) is of volume one, then the intersection of some subfamily of at most 2d members is of volume at most some constant v(d). In Bárány et al. (Am Math Mon 91(6):362–365, 1984), the bound \(v(d)\le d^{2d^2}\) was proved and \(v(d)\le d^{cd}\) was conjectured. We confirm it.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction and Preliminaries
Theorem 1.1
Let \(\mathcal {F}\) be a family of convex sets in \({\mathbb {R}}^{d}\) such that the volume of its intersection is \({\text {vol}}\left( \cap \mathcal {F}\right) >0\). Then there is a subfamily \(\mathcal {G}\) of \(\mathcal {F}\) with \(\left| \mathcal {G}\right| \le 2d\) and \({\text {vol}}\left( \cap \mathcal {G}\right) \le e^{d+1}d^{2d+\frac{1}{2}} {\text {vol}}\left( \cap \mathcal {F}\right) \).
We recall the note from [2] (see also [3]) that the number 2d is optimal, as shown by the 2d half-spaces supporting the facets of the cube.
The order of magnitude \(d^{cd}\) in the Theorem (and in the conjecture in [2]) is sharp as shown in Sect. 3.
Recently, other quantitative Helly type results have been obtained by De Loera et al. [5].
We introduce notations and tools that we will use in the proof. We denote the closed unit ball centered at the origin o in the d-dimensional Euclidean space \({\mathbb {R}}^{d}\) by \(\mathbf {B}\). For the scalar product of \(u,v\in {\mathbb {R}}^{d}\), we use \(\left\langle u,v\right\rangle \), and the length of u is \(|u|=\sqrt{\left\langle u,u\right\rangle }\). The tensor product \(u\otimes u\) is the rank one linear operator that maps any \(x\in {\mathbb {R}}^{d}\) to the vector \((u\otimes u)x=\left\langle u,x\right\rangle u\in {\mathbb {R}}^{d}\). For a set \(A\subset {\mathbb {R}}^{d}\), we denote its polar by \(A^{*}=\{y\in {\mathbb {R}}^{d}:\left\langle x,y\right\rangle \le 1 \text{ for } \text{ all } x\in A\}\). The volume of a set is denoted by \({\text {vol}}\left( \cdot \right) \).
Definition 1.2
We say that a set of vectors \(w_1,\ldots ,w_m\in {\mathbb {R}}^{d}\) with weights \(c_1,\ldots ,c_m>0\) form a John’s decomposition of the identity, if
where I is the identity operator on \({\mathbb {R}}^{d}\).
A convex body is a compact convex set in \({\mathbb {R}}^{d}\) with non-empty interior. We recall John’s theorem [8] (see also [1]).
Lemma 1.3
(John’s theorem) For any convex body K in \({\mathbb {R}}^{d}\), there is a unique ellipsoid of maximal volume in K. Furthermore, this ellipsoid is \(\mathbf {B}\) if, and only if, there are points \(w_1,\ldots ,w_m\in {\text {bd}}{\mathbf {B}}\cap {\text {bd}}{K}\) (called contact points) and corresponding weights \(c_1,\ldots ,c_m>0\) that form a John’s decomposition of the identity.
It is not difficult to see that if \(w_1,\ldots ,w_m\in {\text {bd}}{\mathbf {B}}\) and corresponding weights \(c_1,\ldots ,c_m>0\) form a John’s decomposition of the identity, then \(\{w_1,\ldots ,w_m\}^*\subset d\mathbf {B}\), cf. [1] or [7, Thm. 5.1]. By polarity, we also obtain that \(\frac{1}{d}\mathbf {B}\subset {\text {conv}}(\{w_1,\ldots ,w_m\})\).
One can verify that if \(\Delta \) is a regular simplex in \({\mathbb {R}}^{d}\) such that the ball \(\mathbf {B}\) is the largest volume ellipsoid in \(\Delta \), then
We will use the following form of the Dvoretzky–Rogers lemma [6].
Lemma 1.4
(Dvoretzky–Rogers lemma) Assume that \(w_1,\ldots ,w_m\in {\text {bd}}{\mathbf {B}}\) and \(c_1,\ldots ,c_m>0\) form a John’s decomposition of the identity. Then there is an orthonormal basis \(z_1,\ldots ,z_d\) of \({\mathbb {R}}^{d}\), and a subset \(\{v_1,\ldots ,v_d\}\) of \(\{w_1,\ldots ,w_m\}\) such that
This lemma is usually stated in the setting of John’s theorem, that is, when the vectors are contact points of a convex body K with its maximal volume ellipsoid, which is \(\mathbf {B}\). And often, it is assumed in the statement that K is symmetric about the origin, see for example [4]. Since we make no such assumption (in fact, we make no reference to K in the statement of Lemma 1.4), we give a proof in Sect. 4.
2 Proof of Theorem 1.1
Without loss of generality, we may assume that \(\mathcal {F}\) consists of closed half-spaces, and also that \({\text {vol}}\left( \cap \mathcal {F}\right) <\infty \), that is, \(\cap \mathcal {F}\) is a convex body in \({\mathbb {R}}^{d}\). As shown in [3], by continuity, we may also assume that \(\mathcal {F}\) is a finite family, that is \(P=\cap \mathcal {F}\) is a d-dimensional polyhedron.
The problem is clearly affine invariant, so we may assume that \(\mathbf {B}\subset P\) is the ellipsoid of maximal volume in P.
By Lemma 1.3, there are contact points \(w_1,\ldots ,w_m\in {\text {bd}}{\mathbf {B}}\cap {\text {bd}}{P}\) (and weights \(c_1,\ldots ,c_m>0\)) that form a John’s decomposition of the identity. We denote their convex hull by \(Q={\text {conv}}\{w_1.\ldots ,w_m\}\). Lemma 1.4 yields that there is an orthonormal basis \(z_1,\ldots ,z_d\) of \({\mathbb {R}}^{d}\), and a subset \(\{v_1,\ldots ,v_d\}\) of the contact points \(\{w_1,\ldots ,w_m\}\) such that (3) holds.
Let \(S_1={\text {conv}}\{o,v_1,v_2,\ldots ,v_d\}\) be the simplex spanned by these contact points, and let \(E_1\) be the largest volume ellipsoid contained in \(S_1\). We denote the center of \(E_1\) by u. Let \(\ell \) be the ray emanating from the origin in the direction of the vector \(-u\). Clearly, the origin is in the interior of Q. In fact, by the remark following Lemma 1.3, \(\frac{1}{d}\mathbf {B}\subset Q\). Let w be the point of intersection of the ray \(\ell \) with \({\text {bd}}Q\). Then \(|w|\ge 1/d\). Let \(S_2\) denote the simplex \(S_2={\text {conv}}\{w,v_1,v_2,\ldots ,v_d\}\). See Fig. 1.
We apply a contraction with center w and ratio \(\lambda =\frac{|w|}{|w-u|}\) on \(E_1\) to obtain the ellipsoid \(E_2\). Clearly, \(E_2\) is centered at the origin and is contained in \(S_2\). Furthermore,
Since w is on \({\text {bd}}Q\), by Caratheodory’s theorem, w is in the convex hull of some set of at most d vertices of Q. By re-indexing the vertices, we may assume that \(w\in {\text {conv}}\{w_1,\ldots ,w_k\}\) with \(k\le d\). Now,
Let \(X=\{w_1,\ldots ,w_k, v_1,\ldots ,v_d\}\) be the set of these unit vectors, and let \(\mathcal {G}\) denote the family of those half-spaces which support \(\mathbf {B}\) at the points of X. Clearly, \(|\mathcal {G}|\le 2d\). Since the points of X are contact points of P and \(\mathbf {B}\), we have that \(\mathcal {G}\subseteq \mathcal {F}\). By (5),
By (3),
Since \(\mathbf {B}\subset \cap \mathcal {F}\), by (6) and (4), (2), (7) we have
where \(\Delta \) is as defined above (2). This completes the proof of Theorem 1.1.
Remark 2.1
In the proof, in place of the Dvoretzky–Rogers lemma, we could select the d vectors \(v_1,\ldots ,v_d\) from the contact points randomly: picking \(w_i\) with probability \(c_i/d\) for \(i=1,\ldots ,m\), and repeating this picking independently d times. Pivovarov proved (cf. [9, Lem. 3]) that the expected volume of the random simplex \(S_1\) obtained this way is the same as the right hand side in (7).
3 A Simple Lower Bound for v(d)
We outline a simple proof that one cannot hope a better bound in Theorem 1.1 than \(d^{d/2}\) in place of \(d^{2d+1/2}\). Indeed, consider the Euclidean ball \(\mathbf {B}\), and a family \(\mathcal {F}\) of (very many) supporting closed half space of \(\mathbf {B}\) whose intersection is very close to \(\mathbf {B}\). Suppose that \(\mathcal {G}\) is a subfamily of \(\mathcal {F}\) of 2d members. Denote by \(\sigma \) the Haar probability measure on the sphere \(R\mathbb {S}^{d-1}\), where \(R=(d/(2\ln d))^{\frac{1}{2}}\). Let \(H\in \mathcal {G}\) be one of the half spaces. Then
It follows that
for any \(\varepsilon >0\) if d is large enough.
4 Proof of Lemma 1.4
We follow the proof in [4].
Claim 4.1
Assume that \(w_1,\ldots ,w_m\in {\text {bd}}{\mathbf {B}}\) and \(c_1,\ldots ,c_m>0\) form a John’s decomposition of the identity. Then for any linear map \(T:{\mathbb {R}}^{d}\rightarrow {\mathbb {R}}^{d}\) there is an \(\ell \in \{1,\ldots ,m\}\) such that
where \({\text {tr}}T\) denotes the trace of T.
For matrices \(A,B\in \mathbb {R}^{d\times d}\) we use \(\left\langle A,B\right\rangle ={\text {tr}}\left( AB^T\right) \) to denote their Frobenius product.
To prove the claim, we observe that
Since \(\sum _{i=1}^m c_i=d\), the right hand side is a weighted average of the values \(\left\langle Tw_i,w_i\right\rangle \). Clearly, some value is at least the average, yielding Claim 4.1.
We define \(z_i\) and \(v_i\) inductively. First, let \(z_1=v_1=w_1\). Assume that, for some \(k<d\), we have found \(z_i\) and \(v_i\) for all \(i=1,\ldots ,k\). Let \(F={\text {span}}\{z_1,\ldots ,z_k\}\), and let T be the orthogonal projection onto the orthogonal complement \(F^{\perp }\) of F. Clearly, \({\text {tr}}T=\dim F^{\perp }=d-k\). By Claim 4.1, for some \(\ell \in \{1,\ldots ,m\}\) we have
Let \(v_{k+1}=w_\ell \) and \(z_{k+1}=\frac{Tw_\ell }{|Tw_\ell |}\). Clearly, \(v_{k+1}\in {\text {span}}\{z_1,\ldots ,z_{k+1}\}\). Moreover,
finishing the proof of Lemma 1.4.
Note that in this proof, we did not use the fact that, in a John’s decomposition of the identity, the vectors are balanced, that is \(\sum _{i=1}^m c_iw_i=o\).
References
Ball, K.: An elementary introduction to modern convex geometry. Flavors of Geometry, pp. 1–58. Cambridge University Press, Cambridge (1997)
Bárány, I., Katchalski, M., Pach, J.: Quantitative Helly-type theorems. Proc. Am. Math. Soc. 86(1), 109–114 (1982)
Bárány, I., Katchalski, M., Pach, J.: Helly’s theorem with volumes. Am. Math. Mon. 91(6), 362–365 (1984)
Brazitikos, S., Giannopoulos, A., Valettas, P., Vritsiou, B.-H.: Geometry of Isotropic Convex Bodies, Mathematical Surveys and Monographs, vol. 196. American Mathematical Society, Providence, RI (2014)
De Loera, J.A., La Haye, R.N., Rolnick, D., Soberón, P.: Quantitative Tverberg, Helly, & Carathéodory Theorems. http://arxiv.org/abs/1503.06116 [math] (March 2015)
Dvoretzky, A., Rogers, C.A.: Absolute and unconditional convergence in normed linear spaces. Proc. Natl Acad. Sci. USA 36, 192–197 (1950)
Gordon, Y., Litvak, A.E., Meyer, M., Pajor, A.: John’s decomposition in the general case and applications. J. Differ. Geom. 68(1), 99–119 (2004)
John, F.: Extremum problems with inequalities as subsidiary conditions. Studies and Essays Presented to R. Courant on his 60th Birthday, pp. 187–204, 8 Jan 1948
Pivovarov, P.: On determinants and the volume of random polytopes in isotropic convex bodies. Geom. Dedicata 149, 45–58 (2010)
Acknowledgments
I am grateful for János Pach for the many conversations that we had on the subject and for the inspiring atmosphere that he creates in his DCG group at EPFL. I also thank the referee for helping to make the presentation more clear. The support of the János Bolyai Research Scholarship of the Hungarian Academy of Sciences, and the Hung. Nat. Sci. Found. (OTKA) Grant PD104744 is acknowledged.
Author information
Authors and Affiliations
Corresponding author
Additional information
Editor in Charge: János Pach
Rights and permissions
About this article
Cite this article
Naszódi, M. Proof of a Conjecture of Bárány, Katchalski and Pach. Discrete Comput Geom 55, 243–248 (2016). https://doi.org/10.1007/s00454-015-9753-3
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-015-9753-3
Keywords
- Helly’s theorem
- Quantitative Helly theorem
- Intersection of convex sets
- Dvoretzky–Rogers lemma
- John’s ellipsoid
- Volume