\documentstyle[12pt]{amsart} \headheight=6.15pt \textheight=574pt \textwidth=432pt \oddsidemargin=18.88pt \evensidemargin=18.88pt \topmargin=14.21pt \title{A Tverberg-type result on multicolored simplices} \author{J\'anos Pach} \thanks{Supported by NSF grant CCR-94-24398, PSC-CUNY Research Award 663472 and OTKA-4269. This paper was written while the author was visiting MSRI Berkeley, as part of the Convex Geometry Program. Research at MSRI is supported in part by NSF grant DMS-9022140.} \address{\hskip-\parindent J\'anos Pach\\ City College, CUNY and\\ Courant Institute, NYU\\ 251 Mercer Street\\ New York, NY 10012} \email{pach\@cims6.nyu.edu} \date{} \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{definition}[theorem]{Definition} \newtheorem{prop}[theorem]{Proposition} \newtheorem{conjecture}[theorem]{Conjecture} \def\bs{\bigskip}\def\ms{\medskip}\def\noi{\noindent} \def\bc{\begin{center}}\def\ce{\begin{center}}\def\ec{\end{center}} \def\bd{\begin{eqnarray*}}\def\ed{\end{eqnarray*}} \def\ds{\displaystyle} \def\eps{\varepsilon}\def\ffi{\varphi} \def\qed{\ifhmode\unskip\nobreak\fi\quad\ifmmode\Box\else$\Box$\fi} \begin{document} \begin{abstract} Let $P_1, P_2,\ldots, P_{d+1}$ be pairwise disjoint $n$-element point sets in general position in $d$-space. It is shown that there exist a point $O$ and suitable subsets $Q_i\subseteq P_i \; (i=1, 2, \ldots, d+1)$ such that $|Q_i|\geq c_d|P_i|$, and every $d$-dimensional simplex with exactly one vertex in each $Q_i$ contains $O$ in its interior. Here $c_d$ is a positive constant depending only on $d$. \end{abstract} \maketitle \section{Introduction} Let $P_1, P_2,\ldots, P_{d+1}$ be pairwise disjoint $n$-element point sets in general position in Euclidean $d$-space $\Re ^d$. If two points belong to the same $P_i$, then we say that they are of the same {\it color}. A $d$-dimensional simplex is called {\it multicolored}, if it has exactly one vertex in each $P_i\; (i=1, 2, \ldots, d+1)$. Answering a question of B\'ar\'any, F\"uredi, and Lov\'asz [BFL90], Vre\'cica and {\v Z}ivaljevi\'c [ZV92], proved the following Tverberg-type result. For every $k$, there exists an integer $n(k,d)$ such that if $n\geq n(k,d)$, then one can always find $k$ multicolored vertex disjoint simplices with an interior point in common. (For some special cases, see [BL92], [JS91], [VZ94].) This theorem can be used to derive a nontrivial upper bound on the number of different ways one can cut a finite point set into two (roughly) equal halves by a hyperplane. The aim of this note is to strengthen the above result by showing that there exist ``large'' subsets of the sets $P_i$ such that {\it all} multicolored simplices induced by them have an interior point in common. \medskip \medskip \medskip {\bf Theorem.} {\it There exists $c_d > 0$ with the property that for any disjoint $n$-element point sets $P_1, P_2,\ldots, P_{d+1}\subset\Re ^d$ in general position, one can find a point $O$ and suitable subsets $Q_i\subseteq P_i,\; |Q_i|\geq c_d |P_i|\; (i=1, 2, \ldots, d+1)$ such that every $d$-dimensional simplex with exactly one vertex in each $Q_i$ contains $O$ in its interior.} \medskip The proof is based on the $k=d+1$ special case of the Vre\'cica-\v Zivaljevi\'c theorem (see Theorem 2.1). It uses three auxiliary results, each of them interesting on its own right. The first is Kalai's fractional Helly theorem [K84], which sharpens and generalizes some earlier results of Katchalski and Liu [KL79] (see Theorem 2.2). The second is a variation of Szemer\'edi's regularity lemma for hypergraphs [S78] (Theorem 2.3), and the third is a corollary of Radon's theorem [R21], discovered and applied by Goodman and Pollack [GPW96] (Theorem 2.4). In the next section, we state the above mentioned results and also include a short proof of Theorem 2.3, because in its present form it cannot be found in the literature. Our argument is an adaptation of the approach of Koml\'os and S\'os [KS96]. For some similar results, see [C91],[FR92],[KS95]. The proof of the Theorem is given in Section 3. It shows that the statement is true for a constant $c_d>0$ whose value is triple-exponentially decreasing in $d$. \section{Auxiliary results} \begin{theorem}\label{1} {\rm [ZV92]} Let $A_1, A_2,\ldots, A_{d+1}$ be disjoint $4d$-element sets in general position in $d$-space. Then one can find $d+1$ vertex disjoint simplices with a common interior point such that each of them has exactly one vertex in every $A_i,\; 1\leq i\leq d+1$. \end{theorem} A family of sets is called {\em intersecting} if they have an element in common. \begin{theorem}\label{2} {\rm [K84]} For any $\alpha > 0$, there exists $\beta = \beta(\alpha,d) > 0$ satisfying the following condition. Any family of $N$ convex sets in $d$-space, which contains at least $\alpha {N\choose {d+1}}$ intersecting $(d+1)$-tuples, has an intersecting subfamily with at least $\beta N$ members. \end{theorem} In fact, if $N$ is sufficiently large, then Theorem 2.2 is true for any $\beta < 1 - (1-\alpha)^{1/(d+1)}$. In particular, it holds for $\beta = \alpha/(d+1)$. Let $\cal H$ be a $(d+1)$-partite hypergraph whose vertex set is the union of $d+1$ pairwise disjoint $n$-element sets, $P_1, P_2,\ldots, P_{d+1}$, and whose edges are $(d+1)$-tuples containing precisely one element from each $P_i$. For any subsets $S_i\subseteq P_i\; (1\leq i\leq d+1)$, let $e(S_1, \ldots, S_{d+1})$ denote the number of edges of $\cal H$ induced by $S_1\cup\ldots\cup S_{d+1}$. In this notation, the total number of edges of $\cal H$ is equal to $e(P_1, \ldots, P_{d+1})$. It is not hard to see that for any sets $S_i$ and for any integers $t_i\leq |S_i|,\; 1\leq i\leq d+1$, \begin{equation}\label{average} \frac{e(S_1, \ldots, S_{d+1})}{|S_1|\ldots |S_{d+1}|} =\sum\frac{e(T_1, \ldots, T_{d+1})}{|T_1|\ldots |T_{d+1}|} /{{|S_1|}\choose {t_1}}\ldots {{|S_{d+1}|}\choose {t_{d+1}}}, \end{equation} \noindent where the sum is taken over all $t_i$-element subsets $T_i\subseteq S_i,\; 1\leq i\leq d+1$. \begin{theorem}\label{3} Let $\cal H$ be a $(d+1)$-partite hypergraph on the vertex set $P_1\cup\ldots\cup P_{d+1},\; |P_i| = n\; (1\leq i \leq d+1)$, and assume that $\cal H$ has at least $\beta n^{d+1}$ edges for some $\beta > 0$. Let $0<\eps <1/2$. Then there exist subsets $S_i\subseteq P_i$ of equal size $|S_i|=s\geq \beta ^{1/\eps ^{2d}}n\; (1\leq i\leq d+1)$ such that \noindent (i) $e(S_1, \ldots, S_{d+1}) \geq\beta s^{d+1},$ \noindent (ii) $e(Q_1, \ldots, Q_{d+1})>0$ for any $Q_i\subseteq S_i$ with $|Q_i|\geq\eps s\; (1\leq i\leq d+1)$. \end{theorem} \noindent {\bf Proof:} Let $S_i\subseteq P_i\; (1\leq i \leq d+1)$ be sets of equal size such that $$\frac{e(S_1,\ldots, S_{d+1})}{|S_1|^{d+1-\eps ^{2d}}}$$ is {\em maximum}, and denote $|S_1|=\ldots =|S_{d+1}|$ by $s$. For this choice of $S_i$, condition (i) in the theorem is obviously satisfied, because $$\frac{e(S_1,\ldots, S_{d+1})}{|S_1|^{d+1-\eps ^{2d}}} \geq\frac{e(P_1,\ldots, P_{d+1})}{n^{d+1-\eps ^{2d}}} =\frac{\beta}{n^{-\eps ^{2d}}}\geq \frac{\beta}{s^{-\eps ^{2d}}}.$$ Taking into account the trivial relation $$\frac{e(S_1,\ldots, S_{d+1})}{|S_1|^{d+1-\eps ^{2d}}} \leq s^{\eps ^{2d}},$$ the above inequalities also yield that $s\geq\beta ^{1/\eps ^{2d}}n$. It remains to verify (ii). To simplify the notation, assume that $\eps s$ is an integer, and let $Q_i$ be any $\eps s$-element subset of $S_i\; (1\leq i\leq d+1).$ Then \begin{eqnarray*} \lefteqn{e(Q_1,\ldots, Q_{d+1}) = e(S_1,\ldots, S_{d+1})} \\ & & - e(S_1-Q_1, S_2, S_3, ..., S_{d+1})\\ & & - e(Q_1, S_2-Q_2, S_3, ..., S_{d+1})\\ & & - e(Q_1, Q_2, S_3-Q_3, ..., S_{d+1})\\ & & \ldots\\ & & - e(Q_1, Q_2, Q_3, ..., S_{d+1}-Q_{d+1}). \end{eqnarray*} In view of (1), it follows from the maximal choice of $S_i$ that \begin{eqnarray*} \lefteqn{e(S_1-Q_1, S_2, ..., S_{d+1})}\\ & & = (1-\eps)s^{d+1}\frac{e(S_1-Q_1, S_2, ..., S_{d+1})} {|S_1-Q_1| |S_2| ... |S_{d+1}|}\\ & & = (1-\eps)s^{d+1}\sum_{{T_i\subseteq S_i, |T_i|= (1-\eps)s\atop 2\leq i\leq d+1}} \frac{e(S_1-Q_1, T_2, ..., T_{d+1})}{[(1-\eps)s]^{d+1}} /{s\choose\eps s}^d\\ & & \leq(1-\eps)s^{d+1}\frac{e(S_1, S_2, ..., S_{d+1})} {s^{d+1-\eps ^{2d}}}[(1-\eps)s]^{-\eps ^{2d}}\\ & & = e(S_1, ..., S_{d+1})(1-\eps)^{1-\eps ^{2d}}. \end{eqnarray*} \noindent Similarly, for any $i,\; 2\leq i\leq d+1$, we have \begin{eqnarray*} \lefteqn{e(Q_1, ..., Q_{i-1}, S_i-Q_i, S_{i+1}, ..., S_{d+1})}\\ & & \leq e(S_1, ..., S_{d+1})\eps ^{i-1-\eps ^{2d}}(1-\eps). \end{eqnarray*} Summing up these inequalities, we obtain \begin{eqnarray*} \lefteqn{e(Q_1,\ldots, Q_{d+1})\geq e(S_1,\ldots, S_{d+1}) (1-(1-\eps)^{1-\eps ^{2d}}-\sum_{i=2}^{d+1} \eps ^{i-1-\eps ^{2d}}(1-\eps))}\\ & & \geq e(S_1,\ldots, S_{d+1})(1-(1-\eps)^{1-\eps ^{2d}}- \eps ^{1-\eps ^{2d}}+\eps ^{d+1-\eps ^{2d}}) > 0, \end{eqnarray*} \noindent as required. \qed A $(d+1)$-tuple of convex sets in $d$-space is called {\em separated} if any $j$ of them can be strictly separated from the remaining $d+1-j$ by a hyperplane, $1\leq j\leq d$. An arbitrary family of at least $d+1$ convex sets in $d$-space is {\em separated} if every $(d+1)$-tuple of it is separated. \begin{theorem}\label{4} {\rm [GPW96]} A family of convex sets in $d$-space is separated if and only if no $d+1$ of its members can be intersected by a hyperplane. \end{theorem} Let $n\geq d+1$. Two sequences of points in $d$-space, $(p_1,\ldots, p_n)$ and $(q_1,\ldots, q_n)$, are said to have the same {\em order type} if for any integers $1\leq i_1 <\ldots \frac{1}{(5d)^{d^2}}{N\choose {d+1}}.$$ Hence, we can apply Theorem 2.2 with $\alpha = 1/(5d)^{d^2}$. We obtain that there is a point $O$ contained in the interior of at least $\beta N = \beta (1/(5d)^{d^2},d)n^{d+1}$ multicolored simplices. Let $\cal H$ denote the $(d+1)$-partite hypergraph on the vertex set $P_1\cup\ldots\cup P_{d+1}$, whose edge set consists of all multicolored $(d+1)$-tuples that induce a simplex containing $O$ in its interior. Set $\eps = 1/2^{d2^d},$ and apply Theorem 2.3 to the hypergraph $\cal H$ to find $S_i\subseteq P_i,\; 1\leq i\leq d+1,$ meeting the requirements. By throwing out some points from each $S_i$, but retaining a positive proportion of them, we can achieve that the convex hulls of the sets $S_i$ are separated. Indeed, assume e.g. that there is no hyperplane strictly separating $S_1\cup\ldots\cup S_j$ from $S_{j+1}\cup\ldots\cup S_{d+1}$. By the {\em ham-sandwich theorem} [B33], one can find a hyperplane $h$ which simultaneously bisects $S_1,\ldots, S_d$ into as equal parts as possible. Assume without loss of generality that at least half of the elements of $S_{d+1}$ are ``above'' $h$. Then throw away all elements of $S_1\cup\ldots\cup S_j$ that are above $h$ and all elements of $S_{j+1}\cup\ldots\cup S_{d+1}$ that are below $h$. We can repeat this procedure as long as we find a non-separated $(d+1)$-tuple. In each step, we reduce the size of every set by a factor of at most 2. Notice that in the same manner we can also achieve that e.g. the $(d+1)$-tuple \(\{\{O\}, \mbox{ conv$(S_1),\ldots,$ conv$(S_d)$}\}\) becomes separated. In this case, $h$ will always pass through the point $O$, therefore $O$ will never be deleted. After at most $(d+2)2^d$ steps we end up with $Q_i\subseteq S_i,\; |Q_i|>\eps s\; (1\leq i\leq d+1)$ such that \(\{\{O\}, \mbox{ conv$(S_1),\ldots,$conv$(S_{d+1})$}\}\) is a separated family. It follows from the remark after Theorem 2.4 that there are only two possibilities: either every multicolored simplex induced by $Q_1\cup\ldots\cup Q_{d+1}$ contains $O$ in its interior, or none of them does. However, this latter option is ruled out by part (ii) of Theorem 2.3. This completes proof. \qed \medskip Instead of applying Theorem 2.2, we could have started the proof by referring to the following result of Alon, B\'ar\'any, F\"uredi, and Kleitman [ABFK92], which is also based on Theorem 2.1. For any $\beta>0$ there is a $\beta^{'}_{d} > 0$ such that any family of $\beta n^{d+1}$ simplices induced by $n$ points in $d$-space has at least $\beta^{'}_{d}n^{d+1}$ members with non-empty intersection. Our proof easily yields the following. \begin{theorem} For any $\beta>0$ there is a $\beta^{''}_{d}> 0$ with the property that given any family of $\beta n^{d+1}$ simplices induced by an $n$-element set $P\subset\Re ^d$, one can find a point $O$ and suitable subsets $Q_i\subseteq P_i,\; |Q_i|\geq\beta^{''}_{d}|P_i|\; (i=1, 2, \ldots, d+1)$ such that every $d$-dimensional simplex with exactly one vertex in each $Q_i$ contains $O$. \end{theorem} {\bf Acknowledgement.} I am grateful to Imre B\'ar\'any, G\'eza T\'oth, and Pavel Valtr for their valuable suggestions. \begin{thebibliography}{DSS} \bibitem[ABFK92]{ABFK92} {N. Alon, I. B\'ar\'any, Z. F\"uredi, and D. Kleitman,} {Point selections and weak $\eps$-nets for convex hulls} {\it Combin. Probab. Comput.} {\bf 1}, 189--200. \bibitem[BFL90]{BFL90} {I. B\'ar\'any, Z. F\"uredi, and L. Lov\'asz,} {On the number of halving planes,} {\it Combinatorica} {\bf 10}, 175--183. \bibitem[BL92]{BL92} {I. B\'ar\'any and D. Larman,} {A colored version of Tverberg's theorem,} {\it J. London Math. Soc. (2)} {\bf 45}, 314--320. \bibitem[B33]{B33} {K. Borsuk,} {Drei S\"atze \"uber die $n$-dimensionale euklidische sph\"are,} {\it Fundamenta Math.} {\bf 20}, 177--190. \bibitem[C91]{C91} {F. R. K. Chung,} {Regularity lemmas for hypergraphs and quasi-randomness,} {\it Random Structures and Algorithms} {\bf 2}, 241--252. \bibitem[FR92]{FR92} {P. Frankl and V. R\"odl,} {The uniformity lemma for hypergraphs,} {\it Graphs and Combinatorics} {\bf 8}, 309--312. \bibitem[GPW93]{GPW93} {J. E. Goodman, R. Pollack, and R. Wenger,} {Geometric transversal theory, in:} {\it New Trends in Discrete and Computational Geometry (J. Pach, ed.), Springer-Verlag, Berlin}, 163--198. \bibitem[GPW96]{GPW96} {J. E. Goodman, R. Pollack, and R. Wenger,} {Bounding the number of geometric permutations induced by k-transversals,} {\it J. Combin. Theory, Ser. A,} to appear. \bibitem[JS91]{JS91} {J. Jaromczyk and G. \'Swiatek,} {The optimal constant for the colored version of Tverberg's theorem,} {\it manuscript}. \bibitem[K84]{K84} {G. Kalai,} {Intersection patterns of convex sets,} {\it Israel J. Math.} {\bf 48}, 161--174. \bibitem[KL79]{KL79} {M. Katchalski and A. Liu,} {A problem of geometry in $\Re ^d$,} {\it Proc. Amer. Math. Soc.} {\bf 75}, 284--288. \bibitem[KS95]{KS95} {J. Koml\'os and M. Simonovits,} {Szemer\'edi's regularity lemma and its applications, to appear in:} {\it Paul Erd\H os is Eighty, Proc. Colloq. Math. Soc. J. Bolyai.} \bibitem[KS96]{KS96} {J. Koml\'os and V. T. S\'os,} {Regular subgraphs of graphs,} {manuscript.} \bibitem[R21]{R21} {J. Radon,} {Mengen konvexer K\"orper, die einen gemeinsamen Punkt enthalten,} {\it Math. Ann.} {\bf 83}, 113--115. \bibitem[S78]{S78} {E. Szemer\'edi,} {Regular partitions of graphs, in:} {\it Probl\`emes combinatoires et th\'eorie des graphes, Colloq. Internat. CNRS} {\bf 260}, {CNRS, Paris}, 399--401. \bibitem[T66]{T66} {H. Tverberg,} {A generalization of Radon's theorem,} {\it J. London Math. Soc.} {\bf 41}, 123--128. \bibitem[VZ94]{VZ94} {S. T. Vre\'cica and R. T. \v Zivaljevi\'c,} {New cases of the colored Tverberg theorem, in:} {\it Jerusalem Combinatorics '93, Contemp. Math.} {\bf 178}, {Amer. Math. Soc., Providence}, 325--334. \bibitem[ZV92]{ZV92} {R. T. \v Zivaljevi\'c and S. T. Vre\'cica,} {The colored Tverberg's problem and complexes of injective functions,} {\it J. Combin. Theory Ser. A} {\bf 61}, 309--318. \end{thebibliography} \end{document}