Publication

Abstract : 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 Rd 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 Ω((8/3)d/2)(n/2)d((n−1)/2)d crossing pairs of hyperedges for n≥3 and sufficiently large d. Using Gale transform and Ham-Sandwich theorem, we improve this lower bound to Ω(2d)(n/2)d((n−1)/2)d for n≥3 and sufficiently large d.