Maximum Rectilinear Crossing Number of Uniform Hypergraphs

Abstract

We improve the lower bound on the $d$-dimensional rectilinear crossing number of the complete $d$-uniform hypergraph having $2d$ vertices to $\Omega \left(\frac{(4\sqrt{2}/3^{3/4}{)}^d}{d}\right)$ from $\Omega (2^d\sqrt{d})$. We also establish that the $3$-dimensional rectilinear crossing number of a complete $3$-uniform hypergraph having $n\ge 9$ vertices is at least $\frac{43}{42}\left(\genfrac{}{}{0ex}{}{n}{6}\right)$. We prove that the maximum number of crossing pairs of hyperedges in a $4$-dimensional rectilinear drawing of the complete $4$-uniform hypergraph having $n$ vertices is $13\left(\genfrac{}{}{0ex}{}{n}{8}\right)$. We also prove that among all $4$-dimensional rectilinear drawings of a complete $4$-uniform hypergraph having $n$ vertices, the number of crossing pairs of hyperedges is maximized if all its vertices are placed at the vertices of a $4$-dimensional neighborly polytope. Our result proves the conjecture by Anshu et al. [Anshu, Gangopadhyay, Shannigrahi, and Vusirikala, 2017] for $d=4$. We prove that the maximum $d$-dimensional rectilinear crossing number of a complete $d$-partite $d$-uniform balanced hypergraph is $(2^{d-1}-1){\left(\genfrac{}{}{0ex}{}{n}{2}\right)}^d$. We then prove that finding the maximum $d$-dimensional rectilinear crossing number of an arbitrary $d$-uniform hypergraph is NP-hard. We give a randomized scheme to create a $d$-dimensional rectilinear drawing of a $d$-uniform hypergraph $H$ such that, in expectation the total number of crossing pairs of hyperedges is a constant fraction of the maximum $d$-dimensional rectilinear crossing number of $H$.

Accepted for publication in Graphs and Combinatorics