Standard

k-Sets and rectilinear crossings in complete uniform hypergraphs. / Gangopadhyay, Rahul; Shannigrahi, Saswata.

In: Computational Geometry: Theory and Applications, Vol. 86, 101578, 01.2020.

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

Harvard

Gangopadhyay, R & Shannigrahi, S 2020, 'k-Sets and rectilinear crossings in complete uniform hypergraphs', Computational Geometry: Theory and Applications, vol. 86, 101578. https://doi.org/10.1016/j.comgeo.2019.101578

APA

Gangopadhyay, R., & Shannigrahi, S. (2020). k-Sets and rectilinear crossings in complete uniform hypergraphs. Computational Geometry: Theory and Applications, 86, [101578]. https://doi.org/10.1016/j.comgeo.2019.101578

Vancouver

Gangopadhyay R, Shannigrahi S. k-Sets and rectilinear crossings in complete uniform hypergraphs. Computational Geometry: Theory and Applications. 2020 Jan;86. 101578. https://doi.org/10.1016/j.comgeo.2019.101578

Author

Gangopadhyay, Rahul ; Shannigrahi, Saswata. / k-Sets and rectilinear crossings in complete uniform hypergraphs. In: Computational Geometry: Theory and Applications. 2020 ; Vol. 86.

BibTeX

@article{e3956537cd124291a29abd9aa20e27a3,
title = "k-Sets and rectilinear crossings in complete uniform hypergraphs",
abstract = "In this paper, we study the d-dimensional rectilinear drawings of the complete d-uniform hypergraph K2d d. Anshu et al. (2017) [3] used Gale transform and Ham-Sandwich theorem to prove that there exist Ω(2d) crossing pairs of hyperedges in such a drawing of K2d d. We improve this lower bound by showing that there exist Ω(2dd) crossing pairs of hyperedges in a d-dimensional rectilinear drawing of K2d d. We also prove the following results. 1. There are Ω(2dd3/2) crossing pairs of hyperedges in a d-dimensional rectilinear drawing of K2d d when its 2d vertices are either not in convex position in Rd or form the vertices of a d-dimensional convex polytope that is t-neighborly but not (t+1)-neighborly for some constant t≥1 independent of d. 2. There are Ω(2dd5/2) crossing pairs of hyperedges in a d-dimensional rectilinear drawing of K2d d when its 2d vertices form the vertices of a d-dimensional convex polytope that is (⌊d/2⌋−t′)-neighborly for some constant t′≥0 independent of d.",
keywords = "Affine Gale diagram, Balanced line, Gale transform, k-Set, Rectilinear crossing number, NUMBER",
author = "Rahul Gangopadhyay and Saswata Shannigrahi",
year = "2020",
month = jan,
doi = "10.1016/j.comgeo.2019.101578",
language = "English",
volume = "86",
journal = "Computational Geometry: Theory and Applications",
issn = "0925-7721",
publisher = "Elsevier",

}

RIS

TY - JOUR

T1 - k-Sets and rectilinear crossings in complete uniform hypergraphs

AU - Gangopadhyay, Rahul

AU - Shannigrahi, Saswata

PY - 2020/1

Y1 - 2020/1

N2 - In this paper, we study the d-dimensional rectilinear drawings of the complete d-uniform hypergraph K2d d. Anshu et al. (2017) [3] used Gale transform and Ham-Sandwich theorem to prove that there exist Ω(2d) crossing pairs of hyperedges in such a drawing of K2d d. We improve this lower bound by showing that there exist Ω(2dd) crossing pairs of hyperedges in a d-dimensional rectilinear drawing of K2d d. We also prove the following results. 1. There are Ω(2dd3/2) crossing pairs of hyperedges in a d-dimensional rectilinear drawing of K2d d when its 2d vertices are either not in convex position in Rd or form the vertices of a d-dimensional convex polytope that is t-neighborly but not (t+1)-neighborly for some constant t≥1 independent of d. 2. There are Ω(2dd5/2) crossing pairs of hyperedges in a d-dimensional rectilinear drawing of K2d d when its 2d vertices form the vertices of a d-dimensional convex polytope that is (⌊d/2⌋−t′)-neighborly for some constant t′≥0 independent of d.

AB - In this paper, we study the d-dimensional rectilinear drawings of the complete d-uniform hypergraph K2d d. Anshu et al. (2017) [3] used Gale transform and Ham-Sandwich theorem to prove that there exist Ω(2d) crossing pairs of hyperedges in such a drawing of K2d d. We improve this lower bound by showing that there exist Ω(2dd) crossing pairs of hyperedges in a d-dimensional rectilinear drawing of K2d d. We also prove the following results. 1. There are Ω(2dd3/2) crossing pairs of hyperedges in a d-dimensional rectilinear drawing of K2d d when its 2d vertices are either not in convex position in Rd or form the vertices of a d-dimensional convex polytope that is t-neighborly but not (t+1)-neighborly for some constant t≥1 independent of d. 2. There are Ω(2dd5/2) crossing pairs of hyperedges in a d-dimensional rectilinear drawing of K2d d when its 2d vertices form the vertices of a d-dimensional convex polytope that is (⌊d/2⌋−t′)-neighborly for some constant t′≥0 independent of d.

KW - Affine Gale diagram

KW - Balanced line

KW - Gale transform

KW - k-Set

KW - Rectilinear crossing number

KW - NUMBER

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

UR - https://www.mendeley.com/catalogue/d77626c5-f58f-3220-ae10-f9b3a8454450/

U2 - 10.1016/j.comgeo.2019.101578

DO - 10.1016/j.comgeo.2019.101578

M3 - Article

AN - SCOPUS:85073745709

VL - 86

JO - Computational Geometry: Theory and Applications

JF - Computational Geometry: Theory and Applications

SN - 0925-7721

M1 - 101578

ER -

ID: 49848807