Previous work of the author and Wolf, and independently Chernikov and Towsner, showed that $3$-uniform hypergraphs of small slicewise VC-dimension admit homogeneous partitions. The results of Chernikov and Towsner did not produce explicit bounds, while the work of the author and Wolf relied on a strong version of hypergraph regularity, and consequently produced a Wowzer type bound on the size of the partition. This paper gives a new proof of this result, yielding $\epsilon$-homogeneous partitions of size at most $2^{2^{\epsilon ^{-K}}}$, where $K$ is a constant depending on the slicewise VC-dimension. This is the first in a series of papers about growth of regular partitions of $3$-uniform hypergraphs. Our main result is a crucial ingredient in the second and third papers in the series, which investigate the growth of two types of regular partitions in hereditary properties of $3$-uniform hypergraphs, namely the weak type first defined by Chung and Haviland–Thomason, and the stronger type first developed by Gowers, and independently, Frankl and Rödl.

We set up a general context in which one can prove Sauer–Shelah type lemmas. We apply our general results to answer a question of Bhaskar [1] and give a slight improvement to a result of Malliaris and Terry [7]. We also prove a new Sauer–Shelah type lemma in the context of $ \operatorname {\textrm{op}}$-rank, a notion of Guingona and Hill [4].

We consider a group G that does not have the independence property and study the definability of certain subgroups of G, using parameters from a fixed elementary extension G of G. If X is a definable subset of G, its trace on G is called an externally definable subset. If H is a definable subgroup of G, we call its trace on G an external subgroup. We show the following. For any subset A of G and any external subgroup H of G, the centraliser of A, the A-core of H and the iterated centres of H are external subgroups. The normaliser of H and the iterated centralisers of A are externally definable. A soluble subgroup S of derived length ℓ is contained in an S-invariant externally definable soluble subgroup of G of derived length ℓ. The subgroup S is also contained in an externally definable subgroup X ∩ G of G such that X generates a soluble subgroup of G of derived length ℓ. Analogue results are discussed when G is merely a type definable group in a structure that does not have the independence property.