On the Rectilinear Crossing Number of Complete Uniform Hypergraphs

Abstract

In this paper, we consider a generalized version of the rectilinear crossing number problem of drawing complete graphs on a plane. The minimum number of crossing pairs of hyperedges in the $d$-dimensional rectilinear drawing of a $d$-uniform hypergraph is known as the $d$-dimensional rectilinear crossing number of the hypergraph. The currently best-known lower bound on the $d$-dimensional rectilinear crossing number of a complete $d$-uniform hypergraph with $n$ vertices in general position in ${\mathbb{R}}^d$ is $\Omega (\frac{2^d}{\sqrt{d}}\log d)\left(\genfrac{}{}{0ex}{}{n}{2d}\right)$. In this paper, we improve this lower bound to $\Omega (2^d)\left(\genfrac{}{}{0ex}{}{n}{2d}\right)$. We also consider the special case when all the vertices of a $d$-uniform hypergraph are placed on the $d$-dimensional moment curve. For such complete $d$-uniform hypergraphs with $n$ vertices, we show that the number of pairwise crossing hyperedges is $\Theta (\frac{4^d}{\sqrt{d}})\left(\genfrac{}{}{0ex}{}{n}{2d}\right)$.

References in corpus (1)

• A Lower Bound on the Crossing Number of Uniform Hypergraphs

Cited by in corpus (2)

• $k$-Sets and Rectilinear Crossings in Complete Uniform Hypergraphs
• Rectilinear Crossings in Complete Balanced d-Partite d-Uniform Hypergraphs