Zarankiewicz's problem for semilinear hypergraphs

DOI10.1017/FMS.2021.52zbMATH Open1473.05133arXiv2009.02922OpenAlexW3198368056WikidataQ112628822 ScholiaQ112628822MaRDI QIDQ5154785FDOQ5154785

Authors:

Publication date: 5 October 2021

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

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).

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

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

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)

Cites Work

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

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)