Almost-linear Zarankiewicz bounds in $1$-semi-equational theories

Abstract

We study multipartite hypergraphs definable in $1$-semi-equational theories and prove almost-linear Zarankiewicz bounds in every fixed arity $r\ge 2$. If $T$ is a $1$-semi-equational theory, then, for every formula $\phi$ and fixed $t,r\ge 2$, there is a constant $c$ such that each $K_{t,\dots ,t}$-free $r$-partite hypergraph defined by $\phi$ on $n$ vertices has $O_{T,\phi ,t,r}\left(n^{r-1}(1+\log (1+n){)}^c\right)$ edges. Put ${\alpha }_k=\min \{k-1,2\}$. In the bipartite case, a Boolean combination of $m$ $(k,1)$-semi-equations has $O_{k,t,m}\left(n(1+\log (1+n){)}^{(m-1){\alpha }_k}\right)$ edges whenever it is $K_{t,t}$-free. In particular, a relation defined by one $(k,1)$-semi-equation or its negation has a linear bound. The proofs combine incidence estimates for indexed set systems with low-crossing orderings of finite $k$-wise laminar families. Consequently, no $1$-semi-equational theory locally trace-defines an infinite domain.

arXiv comment17 pages