Zarankiewicz's problem for semi-algebraic hypergraphs

DOI10.1016/J.JCTA.2018.04.007zbMATH Open1391.05187arXiv1705.01979OpenAlexW2963063257MaRDI QIDQ721064FDOQ721064

Authors: Thao Do 

Publication date: 18 July 2018

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Abstract: 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 considered this problem for semi-algebraic graphs, where vertices are points in $mathbb{R}^d$ and edges are defined by some semi-algebraic relations. In this paper, we extend this idea to semi-algebraic hypergraphs. For each $kgeq2$, we find an upper bound on the number of hyperedges in a $k$-uniform $k$-partite semi-algebraic hypergraph without $K_{u_1,dots,u_k}$ for fixed positive integers $u_1,dots,u_k$. When $k=2$, this bound matches the one of Fox et.al. and when $k=3$, it is ${\displaystyle }$Oleft((mnp)^{frac{2d}{2d+1}+varepsilon}+m(np)^{frac{d}{d+1}+varepsilon}+n(mp)^{frac{d}{d+1}+varepsilon}+p(mn)^{frac{d}{d+1}+varepsilon}+mn+np+pm ight),${\displaystyle }$ where $m,n,p$ are the sizes of the parts of the tripartite hypergraph and $varepsilon$ 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.

Full work available at URL: https://arxiv.org/abs/1705.01979

Recommendations

• Zarankiewicz's problem for semilinear hypergraphs
• On the Zarankiewicz problem for intersection hypergraphs
• On the Zarankiewicz problem for intersection hypergraphs
• A semi-algebraic version of Zarankiewicz's problem
• Ramsey numbers of semi-algebraic and semi-linear hypergraphs
• Ramsey-Turán numbers for semi-algebraic graphs
• Density and regularity theorems for semi-algebraic hypergraphs
• An extension of the Erdős-Ginzburg-Ziv theorem to hypergraphs
• The Schur-Erdős problem for semi-algebraic colorings
• Ramsey properties of algebraic graphs and hypergraphs

zbMATH Keywords

incidence geometrypolynomial partitioningintersection hypergraphssemi-algebraic hypergraphsunit area problemunit minor problemZarankiewicz's problem

Mathematics Subject Classification ID

Hypergraphs (05C65)

Cites Work

• Title not available (Why is that?)
• On extremal problems of graphs and generalized graphs
• On the Erdős distinct distances problem in the plane
• Title not available (Why is that?)
• On the Betti Numbers of Real Varieties
• A semi-algebraic version of Zarankiewicz's problem
• A separator theorem for string graphs and its applications
• On the Number of Incidences Between Points and Curves
• Applications of a new separator theorem for string graphs
• Extremal problems in discrete geometry
• Separator theorems and Turán-type results for planar intersection graphs
• On totally positive matrices and geometric incidences
• An incidence theorem in higher dimensions
• Ramsey-type results for semi-algebraic relations
• On the number of cells defined by a family of polynomials on a variety
• Large Complete Bipartite Subgraphs In Incidence Graphs Of Points And Hyperplanes
• Some extremal problems in geometry
• Lower bounds for incidences with hypersurfaces
• A polynomial regularity lemma for semialgebraic hypergraphs and its applications in geometry and property testing
• On the Zarankiewicz problem for intersection hypergraphs
• On the Number of Tetrahedra with Minimum, Unit, and Distinct Volumes in Three-Space
• Density and regularity theorems for semi-algebraic hypergraphs
• The number of unit-area triangles in the plane: theme and variation

Cited In (10)

• Geometric and o-minimal Littlewood-Offord problems
• On the Zarankiewicz problem for intersection hypergraphs
• On the Zarankiewicz problem for intersection hypergraphs
• Density and regularity theorems for semi-algebraic hypergraphs
• Continuous Tur\'an numbers
• Representation complexities of semialgebraic graphs
• The Zarankiewicz problem in 3-partite graphs
• Zarankiewicz's problem for semilinear hypergraphs
• Nondegenerate spheres in four dimensions
• A semi-algebraic version of Zarankiewicz's problem

This page was built for publication: Zarankiewicz's problem for semi-algebraic hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q721064)