A k-ary semi-algebraic relation E on R^d is a subset of R^{kd}, the set of k-tuples of points in R^d,
which is determined by a finite number of polynomial equations and inequalities in kd real variables. Given point sets P_1,...,P_k \subset R^d and a k-ary semi-algebraic relation E on R^d, let H = (P_1,...,P_k,E) be the underlying k-partite k-uniform hypergraph with parts P_1,..,P_k. Fox, Gromov, Lafforgue, Naor, and Pach showed that if H is dense and if k,d and the complexity of E are fixed, then there are linear size subsets P'_i\subset P_i, 1\leq i \leq k, such that P'_1,...,P'_k induces a complete k-partite k-uniform hypergraph.
The goal of this talk is to improve this density-type result by finding much larger subsets P'_1,...,P'_k that induces a complete k-partite k-uniform hypergraph when k and d are large. As a consequence, our results imply several new bounds for classical problems in discrete geometry relating to same-type transversals, homogeneous selections from hyperplanes, and a Tverberg-type result. This is joint work with Jacob Fox and Janos Pach.
Copyright. All Rights Reserved.