Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
418452 | Discrete Applied Mathematics | 2016 | 5 Pages |
Abstract
In this paper, we consider the embedding of a complete dd-uniform geometric hypergraph with nn vertices in general position in RdRd, 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 Kampen–Flores Theorem, it can be seen that such a hypergraph contains Ω(2dd)n2d crossing pairs of hyperedges. Using Gale Transform and Ham Sandwich Theorem, we improve this lower bound to Ω(2dlogdd)n2d.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Anurag Anshu, Saswata Shannigrahi,