کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
8903739 | 1632914 | 2018 | 22 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Zarankiewicz's problem for semi-algebraic hypergraphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Zarankiewicz's problem asks for the largest possible number of edges in a graph that does not contain a Ku,u subgraph for a fixed positive integer u. Recently, Fox, Pach, Sheffer, Sulk and Zahl [12] considered this problem for semi-algebraic graphs, where vertices are points in Rd and edges are defined by some semi-algebraic relations. In this paper, we extend this idea to semi-algebraic hypergraphs. For each kâ¥2, we find an upper bound on the number of hyperedges in a k-uniform k-partite semi-algebraic hypergraph without Ku1,â¦,uk for fixed positive integers u1,â¦,uk. When k=2, this bound matches the one of Fox et al. and when k=3, it isO((mnp)2d2d+1+ε+m(np)dd+1+ε+n(mp)dd+1+ε+p(mn)dd+1+ε+mn+np+pm), where m,n,p are the sizes of the parts of the tripartite hypergraph and ε is an arbitrarily small positive constant. We then present applications of this result to a variant of the unit area problem, the unit minor problem and intersection hypergraphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series A - Volume 158, August 2018, Pages 621-642
Journal: Journal of Combinatorial Theory, Series A - Volume 158, August 2018, Pages 621-642
نویسندگان
Thao T. Do,