2026/07/18 by Hongyi Gou, Mihir Mittal, Chieu-Minh Tran +1
#math.LO #math.CO
We establish absolute and relative almost-linear Zarankiewicz bounds for semilinear relations in valued vector spaces. For every fixed arity and description complexity, a Kt,…,t-free semilinear r-partite hypergraph has at most O (nr-1(log n)c) edges, where c depends only on the arity and the number of valuative literals. In the bipartite case a separate arbitrary-trace argument gives the explicit bound O(n(log n)2s) for description complexity (ρ,s). We also prove a relative extension theorem: intersecting any relation with a hereditary almost-linear profile by s affine moving-radius comparisons increases the logarithmic exponent by at most 2s. For the additive affine-valuative structures on \mathbb Qp and \mathbb Cp, quantifier elimination converts these semilinear results into bounds for all definable relations. Finally, over every valued field with infinite value group, we construct K2,2-free semilinear point--box graphs of description complexity (1,4) with Ω(nlog n/loglog n) edges.