We prove a generalization of the Elekes–Szabó theorem [G. Elekes and E. Szabó, How to find groups? (and how to use them in Erdos geometry?), Combinatorica 32(5) 537–571 (2012)] for relations definable in strongly minimal structures that are interpretable in distal structures.

We present a systematic study of the regularity phenomena for NIP hypergraphs and connections to the theory of (locally) generically stable measures, providing a model-theoretic hypergraph version of the results from [L. Lov asz, B. Szegedy, "Regularity partitions and the topology of graphons", An irregular mind, Springer Berlin Heidelberg, 2010, 415-446]. Besides, we revise the two extremal cases of regularity for stable and distal hypergraphs, improving and generalizing the results from [A. Chernikov, S. Starchenko, "Regularity lemma for distal structures", J. Eur. Math. Soc. 20 (2018), 2437-2466] and [M. Malliaris, S. Shelah, "Regularity lemmas for stable graphs", Transactions of the American Mathematical Society, 366.3, 2014, 1551-1585]. Finally, we consider a related question of the existence of large (approximately) homogeneous definable subsets of NIP hypergraphs and provide some positive results and counterexamples.

We prove a generalizations of the Elekes-Szab o theorem for relations definable in strongly minimal structures that are interpretable in distal structures.

Abstract We present a systematic study of the regularity phenomena for NIP hypergraphs and connections to the theory of (locally) generically stable measures, providing a model-theoretic hypergraph version of the results of Alon-Fischer-Newman and Lov asz-Szegedy for graphs of bounded VC-dimension. We also consider the two extremal cases of regularity for stable and distal hypergraphs, improving and generalizing the corresponding results for graphs in the literature. Finally, we consider a related question of the existence of large (approximately) homogeneous definable subsets of NIP hypergraphs and provide some positive results and counterexamples, in particular for graphs definable in the p-adics.

We establish a cutting lemma for definable families of sets in distal structures, as well as the optimality of the distal cell decomposition for definable families of sets on the plane in $o$-minimal expansions of fields. Using it, we generalize the results in [J. Fox, J. Pach, A. Sheffer, A. Suk, and J. Zahl. "A semi-algebraic version of Zarankiewicz's problem"] on the semialgebraic planar Zarankiewicz problem to arbitrary $o$-minimal structures, in particular obtaining an $o$-minimal generalization of the Szemer edi-Trotter theorem.

Abstract: A bipartite graph$H = \left (V_1, V_2; E \right )$with$\lvert V_1\rvert + \lvert V_2\rvert = n$issemilinearif$V_i \subseteq \mathbb {R}^{d_i}$for some$d_i$and the edge relationEconsists of the pairs of points$(x_1, x_2) \in V_1 \times V_2$satisfying a fixed Boolean combination ofslinear equalities and inequalities in$d_1 + d_2$variables for somes. We show that for a fixedk, the number of edges in a$K_{k,k}$-free semilinearHis almost linear inn, namely$\lvert E\rvert = O_{s,k,\varepsilon }\left (n^{1+\varepsilon }\right )$for any$\varepsilon> 0$; and more generally,$\lvert E\rvert = O_{s,k,r,\varepsilon }\left (n^{r-1 + \varepsilon }\right )$for a$K_{k, \dotsc ,k}$-free semilinearr-partiter-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 }\left (n^{1+\varepsilon }\right )$incidences. The same bound holds if instead of boxes, one takes polytopes cut out by the translates of an arbitrary fixed finite set of half-spaces. 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 ino-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).