Videos

Density-Type Theorems for Semi-Algebraic Hypergraphs

Presenter
November 14, 2014
Keywords:
  • Hypergraphs
MSC:
  • 05C65
Abstract
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'_isubset P_i, 1leq 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.