Zarankiewicz's problem for semi-algebraic hypergraphs

摘要

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