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

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 $\mathrm{\Omega }((8\mathrm{/}3{)}^{d\mathrm{/}2}){\left(n\mathrm{/}2\right)}^d{((n-1)\mathrm{/}2)}^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 $\mathrm{\Omega }\left(2^d\right){\left(n\mathrm{/}2\right)}^d{((n-1)\mathrm{/}2)}^d$ for sufficiently large $n$ and $d$.