$k$-Sets and Rectilinear Crossings in Complete Uniform Hypergraphs

Abstract

In this paper, we study the $d$-dimensional rectilinear drawings of the complete $d$-uniform hypergraph $K_{2d}^d$. Anshu et al. [Computational Geometry: Theory and Applications, 2017] used Gale transform and Ham-Sandwich theorem to prove that there exist $\Omega \left(2^d\right)$ crossing pairs of hyperedges in such a drawing of $K_{2d}^d$. We improve this lower bound by showing that there exist $\Omega \left(2^d\sqrt{d}\right)$ crossing pairs of hyperedges in a $d$-dimensional rectilinear drawing of $K_{2d}^d$. We also prove the following results. 1. There are $\Omega \left(2^d{d}^{3/2}\right)$ crossing pairs of hyperedges in a $d$-dimensional rectilinear drawing of $K_{2d}^d$ when its $2d$ vertices are either not in convex position in ${\mathbb{R}}^d$ or form the vertices of a $d$-dimensional convex polytope that is $t$-neighborly but not $(t+1)$-neighborly for some constant $t\ge 1$ independent of $d$. 2. There are $\Omega \left(2^d{d}^{5/2}\right)$ crossing pairs of hyperedges in a $d$-dimensional rectilinear drawing of $K_{2d}^d$ when its $2d$ vertices form the vertices of a $d$-dimensional convex polytope that is $(\lfloor d/2\rfloor -t^{\prime })$-neighborly for some constant $t^{\prime }\ge 0$ independent of $d$.

11 pages without reference