Finite combinatorial witnesses in recent model theory

Three recent arXiv papers make an abstract model-theoretic property testable through a finite combinatorial object. In one, bounded VC-dimension gives an explicit homogeneous-set bound for finite graphs and hence quantitative consequences for NIP definable relations. In another, free amalgamation produces generic multipartite theories with sharply separated classification behavior. In the third, matroidal pregeometries reduce a fixed-rank case of stable forking to finitely many forbidden embeddings. 1 2 3

The methods are not interchangeable. Their common feature is more precise: each paper chooses a finite object that still remembers the model-theoretic behavior relevant to the theorem.

For a finite graph, the VC-dimension of its neighborhood system measures how many finite adjacency patterns can be realized on a set of vertices. Laskowski's characterization connects finite VC-dimension of definable families with NIP, so a graph theorem under a VC-dimension bound can be read as a finitary consequence for NIP relations. The bridge is important, but the new theorem itself is combinatorial rather than a new characterization of NIP. 1

Sun, Wang, and Zeng prove in Theorem 1.2 that there is an absolute constant h such that every graph G with VC-dimension at most d contains a clique or a stable set of size at least

|G|^(hd)^(-d).

Equivalently, the Erdős–Hajnal exponent is at least (hd)^(-d). This improves the earlier lower bound 2^(-2^(O(d))) to (hd)^(-d). The paper also records consequences for hypergraph Ramsey bounds, NIP graphs, semi-algebraic graphs, and several algebraic representations. 1

The proof has a useful model-theoretic shape even before the NIP application. The authors build a nearly pure blockade, record the relations between its blocks in a pattern graph, and show that a vertex mixed on many blocks forces a drop in the relevant external VC-dimension. The induction therefore moves from dimension r to r - 1; its recurrence has the form s_r <= C r s_(r-1), giving s_r <= (Cr)^r. The finite graph is not merely an example of a tame relation. Its trace patterns are the induction parameter that makes the quantitative estimate possible. 1

Fujita studies graphs whose vertices carry one of n colors, with edges allowed only between different colors. The finite class has free amalgamation: when two finite colored graphs are joined over a common subgraph, no new cross-edges are forced. Its Fraïssé limit gives the generic n-partite graph. This construction supplies a controlled environment in which extension properties can be translated into classification-theoretic dividing lines. 2

The unrestricted generic theory is complete, simple, and has IP, according to Theorem 1.1. The same finite construction changes substantially when one forbids a complete multipartite graph K_mbar. For n > 2, Theorem 1.2 says that the corresponding model companion is complete, has TP2, SOP3, and NSOP4, and has forking independence equal to dividing independence. 2

The finite forbidden pattern matters through the extension axioms: it changes which configurations can be realized in the limit. Here the same broad graph template supports a simple theory with IP in one case and a theory with TP2 and SOP3 in another. The construction makes those differences visible without reducing them to a slogan about graph complexity.

Mutchnik starts from a geometric translation of stable forking. In a finite-rank supersimple theory, algebraic closure on an SU-rank-1 partial type gives a pregeometry, hence a matroid. Instability of the forking relation over a base can then be expressed by the embedding of certain pregeometries into that matroid. Before this paper, the relevant family of obstructions was known to exist but could be infinite. 3

Theorem 1 gives the finite reduction. For each finite rank n, there is a finite set G_n of infinite pregeometries, depending only on n, such that for every finite-rank supersimple theory, forking is stable over a base between types of rank n exactly when no member of G_n embeds into the pregeometry of an SU-rank-1 partial type over a finite set. 3

This does not settle the stable forking conjecture. It changes the form of the problem. At a fixed rank, one no longer has to quantify over an uncontrolled collection of possible geometric failures; the paper supplies a finite obstruction family. The rank-3 case remains the lowest-rank setting where stability of the forking relation over a base is open, while the new theorem gives the same finite-obstruction framework in rank 3 and above. 3

The papers assign different jobs to their finite objects. VC traces provide quantitative control: they limit how quickly a finite graph can avoid homogeneous structure. Free amalgamation provides construction: it builds theories whose extension axioms expose the boundary between simplicity, IP, TP2, and SOP3. Matroid embeddings provide obstruction: they turn instability of forking into a finite list of geometric patterns to exclude.

This gives the papers a concrete common lesson. A finite bound alone need not recover a classification property, and a generic construction need not yield a converse theorem. The translation works when the chosen object preserves the right structure: neighborhood traces preserve NIP tameness, amalgamation preserves realizability patterns, and pregeometries preserve the independence geometry behind forking. These papers show three ways to make that preservation precise, without claiming a general finite-combinatorial characterization of model-theoretic classification.