Zarankiewicz's problem for semi-algebraic hypergraphs

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:158

Article

Do, Thao T.¹ 

[1] MIT, Dept Math, Cambridge, MA 02139 USA

关键词: Zarankiewicz's problem;    Semi-algebraic hypergraphs;    Polynomial partitioning;    Incidence geometry;    Unit minor problem;    Unit area problem;    Intersection hypergraphs;   

DOI  :  10.1016/j.jcta.2018.04.007

来源: Elsevier

【 摘 要 】

Zarankiewicz's problem asks for the largest possible number of edges in a graph that does not contain a K-u,K-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 K-u1,K- (.) (.) (.) (,) (uk) 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((mnp)(2d/2d+1+epsilon )+ n(mp)(d/d+1+epsilon )+ p(mn)(d/d+1+epsilon )+ mn + np + pm), where m, n, p are, the sizes of the parts of the tripartite hypergraph and e 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. (C) 2018 Elsevier Inc. All rights reserved.

【 授权许可】

Free