Zarankiewicz's problem for semilinear hypergraphs

DOI10.1017/FMS.2021.52MaRDI QIDQ5154785zbMATH OpenOpenAlexWikidataFDO

Authors

Publication date 5 October 2021

Published in Forum of Mathematics, Sigma (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

o-minimalitylocal modularityZarankiewicz's problemincidence combinatoricssemilinear hypergraphs

Mathematics Subject Classification ID

Classification theory, stability, and related concepts in model theory (03C45) Enumeration in graph theory (05C30) Hypergraphs (05C65) Erd?s problems and related topics of discrete geometry (52C10) Model theory of ordered structures; o-minimality (03C64) Ramsey theory (05D10) Combinatorial complexity of geometric structures (52C45)

Abstract: A bipartite graph $H=left(V_1,V_2;Eight)$ with $|V_1|+|V_2|=n$ is semilinear if $V_{i}subseteqmathbb{R}^{d_i}$ for some $d_i$ and the edge relation $E$ consists of the pairs of points $(x_1,x_2)in{V}_{1}imes{V}_2$ satisfying a fixed Boolean combination of $s$ linear equalities and inequalities in $d_1+d_2$ variables for some $s$. We show that for a fixed $k$, the number of edges in a $K_{k,k}$-free semilinear $H$ is almost linear in $n$, namely $|E|=O_{s,k,varepsilon}(n^{1+varepsilon})$ for any $varepsilon>0$; and more generally, $|E|=O_{s,k,r,varepsilon}(n^{r-1+varepsilon})$ for a $K_{k,ldots,k}$-free semilinear $r$-partite $r$-uniform hypergraph. As an application, we obtain the following incidence bound: given $n_1$ points and $n_2$ open boxes with axis parallel sides in $mathbb{R}^d$ such that their incidence graph is $K_{k,k}$-free, there can be at most $O_{k,varepsilon}(n^{1+varepsilon})$ incidences. The same bound holds if instead of boxes one takes polytopes cut out by the translates of an arbitrary fixed finite set of halfspaces. We also obtain matching upper and (superlinear) lower bounds in the case of dyadic boxes on the plane, and point out some connections to the model-theoretic trichotomy in $o$-minimal structures (showing that the failure of an almost linear bound for some definable graph allows one to recover the field operations from that graph in a definable manner).

Recommendations

• A semi-algebraic version of Zarankiewicz's problem
• Zarankiewicz's problem for semi-algebraic hypergraphs
• On the Zarankiewicz problem for intersection hypergraphs
• On the Zarankiewicz problem for intersection hypergraphs
• Representation complexities of semialgebraic graphs

Cites work

• scientific article; zbMATH DE number 1160037 (Why is no real title available?)
• scientific article; zbMATH DE number 2145236 (Why is no real title available?)
• scientific article; zbMATH DE number 3893918 (Why is no real title available?)
• A semi-algebraic version of Zarankiewicz's problem
• A trichotomy theorem for o-minimal structures
• Additive reducts of real closed fields
• An o-minimal Szemerédi-Trotter theorem
• Cutting lemma and Zarankiewicz's problem in distal structures
• Extremal problems in discrete geometry
• Model Theory
• Model-theoretic Elekes–Szabó in the strongly minimal case
• On a problem of K. Zarankiewicz
• On extremal problems of graphs and generalized graphs
• On the Zarankiewicz problem for intersection hypergraphs
• On the chromatic number of regular graphs of matrix algebras
• Regularity lemma for distal structures
• Separation dimension of bounded degree graphs
• Separator theorems and Turán-type results for planar intersection graphs
• Trivial Stable Structures with Non-Trivial Reducts
• Turán-type results for intersection graphs of boxes
• Weakly one-based geometric theories
• Zarankiewicz's problem for semi-algebraic hypergraphs

Cited in

(11)

• Functionality of box intersection graphs
• On the Zarankiewicz problem for intersection hypergraphs
• On the Zarankiewicz problem for intersection hypergraphs
• Zarankiewicz's problem for semi-algebraic hypergraphs
• Turán-type results for intersection graphs of boxes
• Ramsey numbers of semi-algebraic and semi-linear hypergraphs
• Ramsey properties of semilinear graphs
• Representation complexities of semialgebraic graphs
• Coloring lines and Delaunay graphs with respect to boxes
• A semi-algebraic version of Zarankiewicz's problem
• Mini-workshop: Topological and differential expansions of o-minimal structures. Abstracts from the mini-workshop held November 27 -- December 3, 2022

This page was built for publication: Zarankiewicz's problem for semilinear hypergraphs

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