The authors prove a qualitative version of the regularity lemma for bipartite graphs which are definable, eventually with parameters, in a saturated model and whose edge relation is stable.
Given a bipartite graph \((V,W,R)\) that is definable in a saturated model \(M\) whose edge relation \(R\) is stable in the sense of Shelah, and two Keisler measures (finitely additive probability measures on the definable, with parameters, subsets of \(V\) and \(W\), respectively) \(\mu_V\) and \(\nu_W\), the authors prove that whenever \(\varepsilon>0\) is given, \(V\) and \(W\) can be partitioned in finitely many pieces \(V_i\) and \(W_i\), \(i\leq m\), such that:

–

each \(V_i\) and \(W_i\) is definable as a finite Boolean combinations of sets of the form \(\{x\mid R(x,w)\}\) and \(\{y\mid R(v,y)\}\), for \(v\in V\) and \(w\in W\) and either

–

there are \(A_i,B_i\) with \(A_i\subseteq V_i\), \(B_i\subseteq W_i\), \(\mu_V(V_i\setminus A_i)\leq\varepsilon\mu_V(V_i)\) and \(\nu_W(W_i\setminus B_i)\leq\varepsilon\nu_W(W_i)\) such that \(A_i\times W_j, V_i\times B_j\subseteq R\) for all \(i,j\) or

–

there are \(A_i,B_i\) as above such that \(A_i\times W_j, V_i\times B_j\subseteq (V\times W)\setminus R\) for all \(i,j\).

The proof makes a strong use of forcing. A key tool used in the proof is that, if \(\Delta\) is the collection of all formulas obtained as Boolean combination of formulas of the form \(R(x,a)\), for \(a\in W\), and \(V\), \(W\), \(R\) and \(M\) are as above, then every complete \(\Delta\)-type over \(M\) has a unique nonforking extension to a global complete \(\Delta\)-type.
As a consequence, the regularity lemma for finite stable graphs (where the Keisler measure is given by the counting measure) obtained by the first author and S. Shelah [Trans. Am. Math. Soc. 366, No. 3, 1551–1585 (2014; Zbl 1283.05234)], is recovered in its qualitative version.