A lower bound on the crossing number of uniform hypergraphs
In this paper, we consider the embedding of a complete d d -uniform geometric hypergraph with n n vertices in general position in Rd R d , where each hyperedge is represented as a (d?1) ( d ? 1 ) -simplex, and a pair of hyperedges is defined to cross if they are vertex-disjoint and contain a common point in the relative interiors of the simplices corresponding to them. As a corollary of the Van KampenFlores Theorem, it can be seen that such a hypergraph contains ? ( 2 d d ) n 2 d crossing pairs of hyperedges. Using Gale Transform and Ham Sandwich Theorem, we improve this lower bound to ? ( 2 d log d d ) n 2 d .
geometric hypergraph gale transform ham sandwich theorem crossing simplices