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 its nd vertices represented as points in general position in R d and each hyperedge drawn as the 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 vertex 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 Colored Tverberg theorem with restricted dimensions, we observe that such an embedding of a complete balanced d-partite d-uniform hypergraph with nd vertices contains X o8=3THORNd=2 on=2THORNd oon 1THORN=2THORNd crossing pairs of hyperedges for n 3 and sufficiently large d. Using Gale transform and Ham-Sandwich theorem, we improve this lower bound to X 2d on=2THORNd oon 1THORN=2THORNd for n 3 and sufficiently large d.