Zarankiewicz's problem for semi-algebraic hypergraphs
Zarankiewicz's problem for semi-algebraic hypergraphs
复制标题
半代数超图的扎兰凯维奇问题
DOI：
10.1016/j.jcta.2018.04.007
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Thao T. Do
中科院分区：
文献类型：
--
作者：
Thao T. Do
Zarankiewicz问题要求在一个图中，不包含一个Ku，u子图，对于一个固定的正整数u，最大可能的边数。最近，Fox，Pach，Sheffer，Sulk和Zahl [12]考虑了半代数图的这个问题，其中顶点是Rd中的点，边由某些半代数关系定义。在本文中，我们将这一思想推广到半代数超图。对k≥ 2，我们给出了不含Ku 1，...，uk的k-一致k-部半代数超图中超边个数的一个上界，其中u1，...，uk为固定正整数.当k= 2时，这个界与Fox等人的界相匹配，当k= 3时，它是O（（m n p）2 d 2 d+ 1+ ε+ m（n p）d d+ 1+ ε+ n（m p）d d+1 + ε+ p（m n）d d+ 1+ ε+ m n+ n p+ p m），其中m，n，p是三部超图各部分的大小，ε是一个任意小的正常数.然后，我们提出的应用程序，这一结果的一个变种的单位面积问题，单位未成年人的问题和交叉超图。
Zarankiewicz's problem asks for the largest possible number of edges in a graph that does not contain a K u, 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 R d 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 K u 1,…, u k for fixed positive integers u 1,…, u k. When k= 2, this bound matches the one of Fox et al. and when k= 3, it is O ((m n p) 2 d 2 d+ 1+ ε+ m (n p) d d+ 1+ ε+ n (m p) d d+ 1+ ε+ p (m n) d d+ 1+ ε+ m n+ n p+ p m), 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.