Rectilinear Crossings in Complete Balanced d-Partite d-Uniform Hypergraphs

Abstract

In this paper, we study the embedding of a complete balanced $d$-partite $d$-uniform hypergraph with all its $nd$ vertices represented as points in general position in ${\mathbb{R}}^d$ and each hyperedge drawn as a convex hull of $d$ corresponding vertices. We assume that the set of vertices is partitioned into $d$ disjoint sets, each of size $n$, such that each of the vertices in a hyperedge is from a different set. Two hyperedges are said to be crossing if they are vertex disjoint and contain a common point in their relative interiors. Using the Generalized Colored Tverberg Theorem, we observe that such an embedding of a complete balanced $d$-partite $d$-uniform hypergraph with $nd$ vertices contains $\Omega \left((8/3{)}^{d/2}\right){\left(n/2\right)}^d{\left((n-1)/2\right)}^d$ crossing pairs of hyperedges for sufficiently large $n$ and $d$. Using the Gale Transform and the Ham-Sandwich Theorem, we improve this lower bound to $\Omega \left(2^d\right){\left(n/2\right)}^d{\left((n-1)/2\right)}^d$ for sufficiently large $n$ and $d$.