کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
418452 | 681673 | 2016 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A lower bound on the crossing number of uniform hypergraphs
ترجمه فارسی عنوان
اتصال پایین تر در تعداد انقطاع ابرگرافهای یکنواخت
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
نمودار بالای هندسی؛ قضیه ساندویچ ژامبون ؛ تبدیل گیل
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 209, 20 August 2016, Pages 11–15
Journal: Discrete Applied Mathematics - Volume 209, 20 August 2016, Pages 11–15
نویسندگان
Anurag Anshu, Saswata Shannigrahi,