Standard

A lower bound on the crossing number of uniform hypergraphs. / Anshu, Anurag; Shannigrahi, Saswata.

In: Discrete Applied Mathematics, Vol. 209, 20.08.2016, p. 11-15.

Research output: Contribution to journal › Article › peer-review

Harvard

Anshu, A & Shannigrahi, S 2016, 'A lower bound on the crossing number of uniform hypergraphs', Discrete Applied Mathematics, vol. 209, pp. 11-15. https://doi.org/10.1016/j.dam.2015.10.009

APA

Anshu, A., & Shannigrahi, S. (2016). A lower bound on the crossing number of uniform hypergraphs. Discrete Applied Mathematics, 209, 11-15. https://doi.org/10.1016/j.dam.2015.10.009

Vancouver

Anshu A, Shannigrahi S. A lower bound on the crossing number of uniform hypergraphs. Discrete Applied Mathematics. 2016 Aug 20;209:11-15. https://doi.org/10.1016/j.dam.2015.10.009

Author

Anshu, Anurag ; Shannigrahi, Saswata. / A lower bound on the crossing number of uniform hypergraphs. In: Discrete Applied Mathematics. 2016 ; Vol. 209. pp. 11-15.

BibTeX

@article{301cb8869ee048f7840e1401647fa142,
title = "A lower bound on the crossing number of uniform hypergraphs",
abstract = "In this paper, we consider the embedding of a complete d-uniform geometric hypergraph with n vertices in general position in Rd, where each hyperedge is represented as a (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 = "Crossing simplices, Gale transform, Geometric hypergraph, Ham Sandwich theorem",
author = "Anurag Anshu and Saswata Shannigrahi",
year = "2016",
month = aug,
day = "20",
doi = "10.1016/j.dam.2015.10.009",
language = "English",
volume = "209",
pages = "11--15",
journal = "Discrete Applied Mathematics",
issn = "0166-218X",
publisher = "Elsevier",

}

RIS

TY - JOUR

T1 - A lower bound on the crossing number of uniform hypergraphs

AU - Anshu, Anurag

AU - Shannigrahi, Saswata

PY - 2016/8/20

Y1 - 2016/8/20

N2 - In this paper, we consider the embedding of a complete d-uniform geometric hypergraph with n vertices in general position in Rd, where each hyperedge is represented as a (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.

AB - In this paper, we consider the embedding of a complete d-uniform geometric hypergraph with n vertices in general position in Rd, where each hyperedge is represented as a (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.

KW - Crossing simplices

KW - Gale transform

KW - Geometric hypergraph

KW - Ham Sandwich theorem

UR - http://www.scopus.com/inward/record.url?scp=84953235737&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2015.10.009

DO - 10.1016/j.dam.2015.10.009

M3 - Article

AN - SCOPUS:84953235737

VL - 209

SP - 11

EP - 15

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

ER -

ID: 49849078