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$. More precisely, if $T$ is a $1$-semi-equational theory, then, for every formula $\phi$ and every $t\ge 2$, and every $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}(n^{r-1}(1+\log (1+n){)}^c)$ edges. In the bipartite case, a Boolean combination of $m$ $(k,1)$-semi-equations has $O_{k,t,m}(n(1+\log (1+n){)}^{(m-1)(k-1)})$ 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 are based on incidence estimates for $k$-wise laminar indexed set systems.

13 pages