← Back to arXiv
arXivLogicarXiv:2608.25464

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

The paper tackles a combinatorics problem about how many connections can exist in certain structured mathematical systems before a particular pattern must appear. Specifically, it studies hypergraphs, which are generalizations of networks where relationships can link more than two objects at a time. The central question is: if you forbid a specific repeated pattern called a complete sub-hypergraph (denoted K_{t,...,t}, meaning t objects on each side all mutually connected), how many total connections or "edges" can the hypergraph have? The answer depends on the algebraic structure defining the hypergraph, and the paper shows that for a class of logical theories called "1-semi-equational theories," the number of edges is nearly as small as it could possibly be, growing almost linearly in the number of vertices rather than much faster.

The class of theories studied here, called 1-semi-equational, describes mathematical structures where relationships between objects can be expressed using equations in a controlled, one-sided way. The main result is that any hypergraph definable in such a theory, once you forbid the repeated pattern, has at most roughly n^(r-1) times a slowly growing logarithmic correction factor in edges, where n is the number of vertices and r is the number of parts in the hypergraph. For ordinary bipartite graphs (r=2), this becomes nearly linear in n. The authors also give more precise bounds depending on how the defining formula is built up from simpler semi-equational pieces, tracking exactly how the logarithmic factor grows with complexity.

The technical engine behind these results is a new tool the authors develop called "k-wise laminar indexed set systems." Laminar families are collections of sets with a clean nesting structure (any two sets are either disjoint or one contains the other), and the paper generalizes this idea to handle multiple interacting families simultaneously. By carefully controlling how these structured set systems can overlap and interact, the authors obtain the incidence estimates needed to count edges. The work fits into a broader program in model theory and combinatorics that tries to explain why definable structures in "tame" logical theories behave much more regularly than arbitrary combinatorial objects, and it extends previously known results from graphs to higher-arity hypergraphs in a new family of theories.

Read original →