
Given an element \(h\in \prod _{\alpha \in \mathrm {ess}(f)}g_1(\alpha )\) , the element \(\bar{r}_h\)  is well-defined because the representation of \(\bar{r}_h\)  given in the definition is defined for each \(\alpha \in B_\beta \)  and \(B_\beta \in \subseteq .\item The prototypical example of the sort of \) hess(f)g1()\( that we wish to consider are the \) h\( defined by Equation~(\ref {hbeta}) in Lemma~\ref {eta}. Our main use of this definition will be to take \)\( elements of \) Gf\( and treat a given set of their representations as if they were \) h\(.\item The condition that there exists a \)\( such that \) B\( is not only to guarantee that we can say that the length of \) rh\( is finite according to \)\(, but also because we will wish to use \) rh\( as a parameter in the formula \) (x;rh)\(.\item The condition that there is such a \)\( becomes trivial in the case that \) =\( for all \) ,\( (in this case we say that \) p(x)\( is a \)\(-type). This case is what occurs for the types we consider later (see e.g.\ the definition of \) SOP2\(-types in Definition~\ref {sop2type}). More generally, it was shown by Malliaris in \cite {mmvarphitypes} that the study of Keisler^{\prime }s order can be reduced to the study of whether \)\(-types are realized in regular ultrapowers.\item The choice of \)\( such that \) B\( is unique in the sense that \)\( will also have \) B\( if and only if \) =\(.\)
Lemma 5.3 
Let \(f\)  be a graph-like distribution with conjugate determined by \(g_1,g_2\)  and with graph distribution sequence \((\mathbb {G}_\alpha )_{\alpha <\lambda }\)  and ultragraph \(\mathbb {G}_f=\mathbb {G}_{\mathrm {ess}(f)}^{}\)  where \(=\mathrm {ess}(f)\) . Let \(H\subseteq \mathbb {G}_f\)  induce a complete subgraph of \(\mathbb {G}_f\) . If

\(H^{\prime }\)  is a set of representatives for the elements of \(H\)  where \(H^{\prime }\)  is a subset of \(\prod _{\alpha \in \mathrm {ess}(f)}g_1(\alpha )\) ,

each element of \(H\)  has exactly one representative in \(H^{\prime }\) , and

for each \(h\in H^{\prime }\)  there exists a \(\beta _h\in \lambda \)  so that
\(B_h:=\lbrace \alpha \in \mathrm {ess}(f):\varphi _{h(\alpha )}(\bar{x};\bar{y})=\varphi _{\beta _h}(\bar{x};\bar{y})\rbrace \in \) 

then the collection of formulas
\(q(\bar{x})=\lbrace \varphi _{\beta _h}(\bar{x},\bar{r}_h):h\in H^{\prime }\rbrace \) 
is a type in \(\widehat{\mathcal {M}}\) .

By the characterization of a type in an ultraproduct, it will be enough to show that \(\llbracket \Delta \rrbracket _{q(\bar{x})}^ for every finite \) H'\(. For each \) P(H')\( define \) B=h Bh\(. Following definitions,\)\(\llbracket \Delta \rrbracket _{q(\bar{x})}^\Big \lbrace \alpha \in B_\Delta :\mathcal {M}_\alpha \vDash \exists x,\bigwedge _{h\in \Delta }\varphi _h(x,\bar{r}_{h(\alpha )}(\alpha ))\Big \rbrace =:\llbracket \Delta \rrbracket ^{B_\Delta }_{q(\bar{x})}\)\(where \) rh\( is the parameter induced by \) h\(. For all \) B\( define \) ():={h():h}\(. If \) ||2\(, define\begin{equation}K_\Delta :=\lbrace \alpha \in B_\Delta :[\Delta (\alpha )]^2\subseteq g_2(\alpha )\rbrace .\end{equation}\) The set \(K_\Delta \)  is the set of indices \(\alpha \)  for which \(\Delta (\alpha )\)  induces a complete subgraph of \(\mathbb {G}_\alpha \) . Let \(=\mathrm {ess}(f)\) . Then, because \(\Delta \)  induces a finite complete subgraph of \(H\)  after modding out by \(\) , we have that
\(\mathbb {G}_f\vDash \bigwedge _{\lbrace h_1,h_2\rbrace \in [\Delta ]^2} \left(h_1/\mathrel {E} h_2/\right)\vee \left(h_1/=h_2/\right),\) 
so, by Łoś theorem we have that
\(\mathbb {G}_\alpha \vDash \bigwedge _{\lbrace h_1,h_2\rbrace \in [\Delta (\alpha )]^2} \left(h_1(\alpha )\mathrel {E} h_2(\alpha )\right)\vee \left(h_1(\alpha )=h_2(\alpha )\right)\) 
for \(\) -many \(\alpha \) , and hence \(-many \)\( by Corollary~\ref {Drestriction}(1). Because \) B, we have that \(K_\Delta \)  is an element of \(. By Lemma~\ref {gldistconj}(2), we have that\)\(K_\Delta \subseteq \llbracket \Delta \rrbracket ^{B_\Delta }_{q(\bar{x})}\subseteq \llbracket \Delta \rrbracket _{q(\bar{x})}^and so \) q(x).
The case of \(|\Delta |=1\)  follows from \(\Delta (\alpha )\subseteq g_1(\alpha )\) , which implies \(\llbracket \Delta \rrbracket _{q(\bar{x})}^\lambda \) .
Remarks 5.4    

The converse to the above lemma is not true in general. There may be types of the same form as \(q(\bar{x})\)  (that is, types with representations \((h_\beta )_{\beta <\lambda }\)  for the parameters coming from \(\prod _{\alpha <\lambda }\lbrace r_\beta (\alpha ):\beta <\lambda \rbrace \)  and with \(\beta _h\) 's) but such that \(\lbrace h_\beta /\beta <\lambda \rbrace \)  does not induce a complete subgraph of \(\mathbb {G}_f\) . This can be thought of as saying that \(f\)  carries enough information to recognize that \(p(\bar{x})\)  is a type, but generally does not carry enough information to recognize that all types with similar representations for their parameters are types. There is a converse of this sort when \(i_f[\mathbb {G}_f]\)  is an induced subgraph of \(\mathbb {G}_L\)  (the argument is similar to the proof of Corollary REF ). See Section 6 for the definitions of \(i_f\)  and \(\mathbb {G}_L\) .

The type \(q(\bar{x})\)  does not depend on the choice of the representatives in \(H^{\prime }\) . If there are two representatives \(h,h^{\prime }\)  for the same element of \(\mathbb {G}_f\)  they must be equal at \(-many indices, the representations for \) rh\( and \) rh'\( must agree at \) -many indices, and hence \(\bar{r}_h\)  and \(\bar{r}_{h^{\prime }}\)  are equal. A similar argument shows that \(\beta _h=\beta _{h^{\prime }}\)  in this case.


We wish to study the connection between induced complete subgraphs of \(\mathbb {G}_{\mathrm {ess}(f)}^{}=\mathbb {G}_f\)  and the types of the form given in Equation (REF ). In order to gain an idea of where this analysis will go, recall that complete subgraphs of \(\mathbb {G}_\alpha \)  indicate subsets of \(p(\bar{x})\)  that, when viewed in the \(\alpha \) -th index structure, are satisfiable (Lemma REF (1)). A major reason why we are able to make this conclusion is that each \(g_1(\alpha )\)  is finite. If \(g_1(\alpha )\)  were not finite we would still be able to say that an infinite complete subgraph corresponds to a finitely satisfiable set of formula in the \(\alpha \) -th index structure (i.e. corresponds to a type) but there is no reason to assume that such a type is realized. Take, for example, the type \(\lbrace 0<x<1/n:n\in \mathbb {N}^+\rbrace \)  in the dense linear ordering \(\mathbb {Q}\) . The satisfiability graph for this type is complete, but there is no realization of the type in \(\mathbb {Q}\) . Since the type \(p(\bar{x})\)  corresponds to the (infinite!) image of \(\eta _f\) , why should we expect that we will get any information from \(\mathbb {G}_f\)  other than the observation that \(p(\bar{x})\)  is a type?
If we treat \(\mathbb {G}_f\)  as an arbitrary graph and forget that it comes from an ultraproduct of finite graphs then we cannot extract any more information about whether \(p(\bar{x})\)  is realized. However, if we do remember this extra information, we then find that Łoś theorem tells us that \(\mathbb {G}_f\)  has many of the features of a finite graph so long as we restrict ourselves to looking at internal parts of the structure. We continue by exploring this interaction of apparent finiteness of internal subsets and the types defined in the previous lemma, after taking care of a few technical details allowing us to pinpoint particular distributions for the types described in Lemma REF .
Lemma 5.5 
Let \(f\)  be a graph-like distribution with conjugate \((g_n)_{n\in \omega }\)  and \(H\)  a \(\lambda \) -sized complete subgraph of \(\mathbb {G}_f\)  with transversal \(H^{\prime }\) . Let \(=\mathrm {ess}(f)\) . If \((h_\beta )_{\beta \in \lambda }\)  is an enumeration of \(H^{\prime }\)  and for each \(\beta \in \lambda \)  there exists an \(\beta _h\in \lambda \)  so that
\(B_\beta :=\lbrace \alpha \in \mathrm {ess}(f):\varphi _{h_\beta (\alpha )}(\bar{x};\bar{y})=\varphi _{\beta _h}(\bar{x};\bar{y})\rbrace \in ,\) 
then there is a graph-like distribution \(f_{H^{\prime }}\colon \mathcal {P}_\omega (\lambda )\rightarrow  for the type \)\(q(\bar{x})=\lbrace \varphi _{\beta _h}(\bar{x},\bar{r}_{h_\beta }):\beta <\lambda \rbrace \)\( where, if \) (n)n\( is the conjugate of \) fH'\(, then \) 1,2\( are defined for all \)\( by{\begin{@align*}{1}{-1}\ell _1(\alpha )&:=g_1(\alpha )\cap \lbrace \beta \in \lambda :\alpha \in B_\beta \rbrace \text{ and }\\\ell _2(\alpha )&:=[\ell _1(\alpha )]^2\cap \lbrace \lbrace \beta ,\gamma \rbrace \in [\lambda ]^2:\lbrace h_\beta (\alpha ),h_\gamma (\alpha )\rbrace \in g_1(\alpha )\cup g_2(\alpha )\rbrace .\end{@align*}}\)
The function \(\ell _1\)  produces a finite subset of \(\lambda \)  for any input \(\alpha <\lambda \)  as \(\ell _1(\alpha )\subseteq g_1(\alpha )\) . The image of \(\ell _2\)  consists of finite sets as \(\ell _2(\alpha )\subseteq [\ell _1(\alpha )]^2\)  and \(\ell _1(\alpha )\)  is finite.
We will proceed by checking that the functions \(\ell _1,\ell _2\)  satisfy conditions \((1)\) –\((4)\)  of Lemma REF .
\((1)\) : Suppose that \(\beta \in \ell _1(\alpha )\subseteq g_1(\alpha )\) . Then \(\alpha \in \mathrm {ess}(f)\)  by Lemma REF (2). We thus have
\(\mathcal {M}_\alpha \vDash \exists \bar{x},\,\varphi _{\beta _h}(\bar{x},\bar{r}_{h_\beta (\alpha )}(\alpha ))\) 
because \(h_\beta (\alpha )\in g_1(\alpha )\)  by definition and because we can apply Lemma REF (1) to \(g_1\) .
\((2)\) : Suppose that \(\Delta \in [\lambda ]^n\)  for \(n\ge 2\) , \(\alpha <\lambda \) , and \([\Delta ]^2\subseteq \ell _2(\alpha )\) . Then \([\Delta ]^2\subseteq [g_1(\alpha )]^2\)  as \(\ell _2(\alpha )\subseteq [\ell _1(\alpha )]^2\subseteq [g_1(\alpha )]^2\) , so \(\alpha \in \mathrm {ess}(f)\) . Moreover, for each \(\lbrace \beta ,\gamma \rbrace \in [\Delta ]^2\) , we must have \(\lbrace h_\beta (\alpha ),h_\gamma (\alpha )\rbrace \in g_2(\alpha )\) . This means that
\(\big \lbrace \lbrace h_\beta (\alpha ),h_\gamma (\alpha )\rbrace :\lbrace \beta ,\gamma \rbrace \in [\Delta ]^2\big \rbrace \subseteq [g_2(\alpha )]^2.\) 
Now applying Lemma REF (2) to \(\Delta ^{\prime }=\lbrace h_\beta (\alpha ):\beta \in \Delta \rbrace \)  and \(g_2\) , we get that
\(\mathcal {M}_\alpha \vDash \exists \bar{x},\bigwedge _{\beta \in \Delta }\varphi _{\beta _h}(\bar{x},\bar{r}_{h_\beta (\alpha )}(\alpha ))\) 
as desired. In the case that \(\lbrace h_\beta (\alpha ),h_\gamma (\alpha )\rbrace \in g_1(\alpha )\)  we know that \(h_\beta (\alpha )=h_\gamma (\alpha )\)  and then the desired result is the statement proved in \((1)\)  above.
\((3)\) : We have for any \(\alpha <\lambda \)  that
\(\ell _2(\alpha )\subseteq [\ell _1(\alpha )]^2\) 
by the definition of \(\ell _2\) .
\((4)\) : Pick \(\Delta \in [\lambda ]^2\) . In order to show that
\(A:=\lbrace \alpha \in \lambda :\Delta \in \ell _2(\alpha )\rbrace \in \) 
it will be enough to check that
\(C&:=\big \lbrace \alpha \in \lambda :\Delta \in \lbrace \lbrace \beta ,\gamma \rbrace \in [\lambda ]^2:\lbrace h_\beta (\alpha ),h_\gamma (\alpha )\rbrace \in g_2(\alpha )\rbrace \big \rbrace \in { and }\\D&:=\big \lbrace \alpha \in \lambda :\Delta \in [\ell _1(\alpha )]^2\big \rbrace \in {align*}as A= C\cap D. DefineD^{\prime }= \lbrace \alpha \in \lambda :\Delta \in g_2(\alpha )\rbrace \text{ and }B_\Delta =\bigcap _{\beta \in \Delta }B_{\beta }and notice that D^{\prime }\cap B_\Delta \subseteq D by the fact that g_2(\alpha )\subseteq [g_1(\alpha )]^2 by Lemma~\ref {gldistconj}(3). By Lemma~\ref {gldistconj}(4) applied to g_2, we have that D^{\prime }\in , so D\in  as well. The set C may be rewritten asC=\big \lbrace \alpha \in \lambda :\Delta =\lbrace \beta ,\gamma \rbrace \text{ and }\lbrace h_\beta (\alpha ),h_\gamma (\alpha )\rbrace \in g_2(\alpha )\big \rbrace .Define the set\Delta ^{\prime }:=\lbrace h_\beta :\beta \in \Delta \rbrace .Then K_{\Delta ^{\prime }}\subseteq C where K_{\Delta ^{\prime }} is defined as in Equation~(\ref {kdelta}). The same argument as in the proof of the previous lemma then shows that K_{\Delta ^{\prime }}\in .\) 
Lemma 5.6 
Let \(f\)  be a graph-like distribution with conjugate \((g_n)_{n\in \omega }\)  and \(H\)  a \(\lambda \) -sized complete subgraph of \(\mathbb {G}_f\)  with transversal \(H^{\prime }\) . Let \(1=\mathrm {ess}(f)\)  and \((h_\beta )_{\beta \in \lambda }\)  be an enumeration of \(H^{\prime }\)  such that for each \(\beta \in \lambda \)  there exists a \(\beta _h\in \lambda \)  so that
\(B_\beta :=\lbrace \alpha \in \mathrm {ess}(f):\varphi _{h_\beta (\alpha )}(\bar{x};\bar{y})=\varphi _{\beta _h}(\bar{x};\bar{y})\rbrace \in 1.\) 
Let \(q(\bar{x})\) , \(f_{H^{\prime }}\) , \(\ell _1\) , and \(\ell _2\)  be defined as in the previous lemma and \(2=\mathrm {ess}(f_{H^{\prime }})\) . Then

Define \(\mathrm {loop}(\mathbb {G}_f)\)  to be the graph obtained by adding a loop to every vertex in \(\mathbb {G}_f\) . The map \(\Psi :\mathrm {loop}(\mathbb {G}_{f_{H^{\prime }}})\rightarrow \mathrm {loop}(\mathbb {G}_f)\)  defined for each \(j/2\in \mathbb {G}_{f_{H^{\prime }}}\)  by
\(\Psi (j/2)=(h_{j(\alpha )}(\alpha ))_{\alpha \in \mathrm {ess}(f)}/1\) 
is a graph homomorphism that also preserves non-edges.

\(\Psi \text{\,}\mathord {\upharpoonright }\text{\,}\eta _{f_{H^{\prime }}}[\lambda ]\)  is an isomorphism between the induced subgraphs of \(\eta _{f_{H^{\prime }}}[\lambda ]\)  and \(H\)  in \(\mathbb {G}_{f_{H^{\prime }}}\)  and \(\mathbb {G}_f\)  respectively.


We note that \(\Psi \)  is well-defined as \(j/2=k/2\)  implies that \(j(\alpha )=k(\alpha )\)  for 2-many \(\alpha \)  in \(\mathrm {ess}(f)\)  and \(h_{j(\alpha )}(\alpha )=h_{k(\alpha )}(\alpha )\)  for at least these \(\alpha \) . Using that \(\mathrm {ess}(f_{H^{\prime }})\subseteq \mathrm {ess}(f)\)  (as \(\ell _1(\alpha )\subseteq g_1(\alpha )\)  for all \(\alpha \in \lambda \)  and then using Lemma REF (2)) we have that \(2=1\text{\,}\mathord {\upharpoonright }\text{\,}\mathrm {ess}(f_{H^{\prime }})\) . Then, by Corollary REF (3), we have that \(h_{j(\alpha )}(\alpha )\)  and \(h_{k(\alpha )}(\alpha )\)  are equal for a set of \(\alpha \)  in 1.
\((1)\) : Suppose that \(j/2\)  and \(k/2\)  are elements of \(\mathbb {G}_{f_{H^{\prime }}}\) . Then \(\Psi (j/)\)  and \(\Psi (k/)\)  are edge related in \(\mathrm {loop}(\mathbb {G}_f)\)  if and only if
\(\lbrace \alpha \in \mathrm {ess}(f):\lbrace h_{j(\alpha )}(\alpha ),h_{k(\alpha )}(\alpha )\rbrace \in g_1(\alpha )\cup g_2(\alpha )\rbrace \in 1.\) 
By the definition of \(\ell _2\) , this is equivalent to \(\lbrace j(\alpha ),k(\alpha )\rbrace \in \ell _2(\alpha )\)  or \(j(\alpha )=k(\alpha )\)  for 2-many \(\alpha \)  in \(\mathrm {ess}(f)\)  (by the definition of \(\mathbb {G}_{f_{H^{\prime }}}\)  we have \(j(\alpha )\) , \(k(\alpha )\in \ell _1(\alpha )\) ), which is equivalent to \(j/2\)  and \(k/2\)  being edge related in \(\mathrm {loop}(\mathbb {G}_{f_{H^{\prime }}})\) . As each step in this argument is an equivalence, we must have that \(\Psi (j/2)\)  is edge related to \(\Psi (k/2)\)  in \(\mathrm {loop}(\mathbb {G}_f)\)  if and only if \(j/2\)  and \(k/2\)  are edge related in \(\mathrm {loop}(\mathbb {G}_{f_{H^{\prime }}})\) .
\((2)\)  Now that we know that \(\Psi \)  is a graph homomorphism that also preserves non-edges, showing that \(\Psi \text{\,}\mathord {\upharpoonright }\text{\,}\eta _{f_{H^{\prime }}}[\lambda ]\)  is an isomorphism amounts to showing that the restriction is bijective. Having that \(j/2=\eta _{f_{H^{\prime }}}(\beta )\)  for some \(\beta \in \lambda \)  is equivalent, by Lemma REF , to having that
\(\lbrace \alpha \in \mathrm {ess}(f):j(\alpha )=\beta \rbrace \in 2.\) 
Then the statement \(k/1=\Psi (j/2)\)  is equivalent to
\(\lbrace \alpha \in \mathrm {ess}(f):k(\alpha )=h_\beta (\alpha )\rbrace \in 1,\) 
which is equivalent by Łoś theorem to \(k/1=h_\beta /1\) . As this argument consists of a series of “if and only if” statements, we have that \(\Psi \)  is bijective when restricted to \(\eta _{f_{H^{\prime }}}[\lambda ]\) .
Convention 5.7 We continue to make the distinction between 1 and 2 as defined above. However, since \(2\subseteq 1\)  and \(A\in 1\)  if and only if \(A\cap \mathrm {ess}(f_{H^{\prime }})\in 2\) , we will treat the statements \(A\in 1\)  and \(A\in 2\)  as if they were equivalent and do not spend time worrying about how to translate between the statements.

In order to get to the result that \(\Psi \)  allows some transfer of information between the types \(p(\bar{x})\)  and \(q(\bar{x})\) , we will first prove that “nice enough” homomorphisms between ultraproducts of graphs using essentially the same ultrafilter preserve internal subsets and complete subsets. The “nice enough” referers to functions that are what non-standard analysts would call “internal functions” that are either homomorphisms or preserve non-edges. The following proof is well-known in non-standard analysis, but we feel that it is worth presenting here.
Lemma 5.8 
Suppose that \(I\)  and \(J\)  are sets with \(J\subseteq I\)  and \((\mathbb {G}_i)_{i\in I}\)  and \((\mathbb {H}_j)_{j\in J}\)  are sequences of graphs. Further suppose that \(I\)  is an ultrafilter on \(I\)  and \(J\)  is an ultrafilter on \(J\)  with \(J\subseteq I\)  and that there is a sequence of functions \((\theta _j)_{j\in J}\)  where \(\theta _j\colon \mathbb {H}_j\rightarrow \mathbb {G}_j\)  for each \(j\in J\) . Define
\(\mathbb {G}:=\prod _{i\in I}\mathbb {G}_i/I\,\text{ and }\,\mathbb {H}:=\prod _{j\in J}\mathbb {H}_j/J.\) 
Then

The function \(\Theta :\mathbb {H}\rightarrow \mathbb {G}\)  defined for all \(p/J\)  in \(\mathbb {H}\)  by
\(\Theta (p/J):=\left[i\mapsto \left\lbrace \begin{array}{ll} \theta _i(p(i));&\text{if }i\in J\\\text{any element of }\mathbb {G}_i;&\text{otherwise} \end{array}\right.\right]\bigg /I\) 
is well-defined and unique,

if \(A\subseteq \mathbb {G}\)  and \(B\subseteq \mathbb {H}\)  are internal then so are \(\Theta [B]\)  and \(\Theta ^{-1}[A]\) ,

if \(\lbrace j\in J:\theta _j\text{ is a graph homomorphism}\rbrace \)  is an element of \(J\)  and \(K\subseteq \mathbb {H}\)  induces a complete subgraph of \(\mathbb {H}\)  then \(\Theta [K]\)  induces a complete subgraph of \(\mathbb {G}\) , and

if \(\lbrace j\in J:\theta _j\text{ preserves non-edges as a map }\mathbb {H}_j\rightarrow \mathrm {loop}(\mathbb {G}_j)\rbrace \)  is an element of \(J\)  and \(K\subseteq \mathbb {G}\)  induces a complete subgraph of \(\mathbb {G}\)  then \(\Theta ^{-1}[K]\)  is a complete subgraph of \(\mathbb {H}\) .


\((1)\) : If \(p/J=p^{\prime }/J\) , then \(p(i)=p^{\prime }(i)\)  for \(j\) -many \(i\in J\) , so \(\theta _i(p(i))=\theta _i(p^{\prime }(i))\)  for \(J\) -many \(i\in J\)  as well. Since \(J\subseteq I\) , this is enough to show well-definedness and uniqueness.
\((2)\) : We start with \(\Theta [B]\) . As \(B\)  is internal, we can write \(B\)  as an ultraproduct of the form
\(\prod _{j\in J}B_j/J\) 
where each \(B_j\subseteq H_j\) . Define for each \(i\in J\)  the set
\(B^{\prime }_i=\lbrace \theta _i(h):h\in B_i\rbrace \) 
and for \(i\in I\setminus J\)  define \(B^{\prime }_i=G_i\) .
We claim that \(\Theta [B]=\prod _{i\in I}B^{\prime }_i/I=:\widehat{B}\) . Suppose that \(p\in \prod _{i\in I}B^{\prime }_i\) . Then
\((\theta _i(p(i)))_{i\in I}/I=\Theta ((p\text{\,}\mathord {\upharpoonright }\text{\,}J)/J).\) 
As every element of \(\mathbb {H}\)  can be written as \(\Theta ((p\text{\,}\mathord {\upharpoonright }\text{\,}J)/J)\)  for some \(p\in \prod _{i\in I}B^{\prime }_i\) , we have that \(\Theta [B]=\widehat{B}\)  and so is internal.
The proof that \(\Theta ^{-1}[A]\)  is internal in \(\mathbb {G}\)  is essentially the same after swapping \(A\)  and \(B\) , \(I\)  and \(J\) , and \(\Theta \)  and \(\Theta ^{-1}\) .
\((3)\) : Suppose that \(k_1,k_2\)  are representatives for distinct elements of \(K\) . Then \(\theta _j(k_1(j))\)  and \(\theta _j(k_2(j))\)  are edge related for \(J\) -many \(j\in J\) . Then the representatives given for \(\Theta (k_1)\)  and \(\Theta (k_2)\)  are edge related for \(I\) -many \(i\in I\) . In particular, \(\Theta \)  is a graph homomorphism.
\((4)\) : As in \((3)\) , \(\Theta \colon \mathbb {H}\rightarrow \mathrm {loop}(\mathbb {G})\)  will inherit the property that non-edges are preserved. Suppose that \(k_1,k_2\)  are distinct elements of \(\Theta ^{-1}[K]\) . Then either there is an edge or a loop between \(\Theta (k_1)\)  and \(\Theta (k_2)\) , so \(k_1\)  and \(k_2\)  must be edge related in \(\mathbb {H}\) .
Theorem 5.9 
Let \(f\)  be a graph-like distribution for the \(\lambda \) -type \(p(\bar{x})\)  with graph distribution sequence \((\mathbb {G}_\alpha )_{\alpha <\lambda }\) , let \(1=\mathrm {ess}(f)\) , and let \(H\subseteq \mathbb {G}_f=\mathbb {G}_{\mathrm {ess}(f)}^{1}\)  induce a complete subgraph with \(|H|=\lambda \) . If \(H^{\prime }=\lbrace h_\beta :\beta <\lambda \rbrace \)  is a transversal of \(H\)  and for each \(\beta \in \lambda \)  there exists a \(\beta _h\in \lambda \)  so that
\(B_{\beta ^{\prime }}:=\lbrace \alpha \in \mathrm {ess}(f):\varphi _{h_\beta (\alpha )}(\bar{x};\bar{y})=\varphi _{\beta _h}(\bar{x};\bar{y})\rbrace \in 1,\) 
then the distribution \(f_{H^{\prime }}\)  for the type
\(q(\bar{x})=\lbrace \varphi _{\beta _h}(\bar{x},\bar{r}_{h_\beta }):\beta <\lambda \rbrace \) 
has a multiplicative refinement if and only if there is an internal \(K\subseteq \mathbb {G}_f\)  that induces a complete subgraph with \(H\subseteq K\) .

(\(\Rightarrow \) ) Suppose that \(k:\mathcal {P}_\omega (\lambda )\rightarrow  is a multiplicative refinement of \) fH'\(. We know from Lemma~\ref {multviaseq} that the distribution graph sequence for \) k\( consists of complete graphs. The ultragraph \) Gk\( is complete as completeness is a first-order property of a graph and hence preserved by ultraproducts. From Lemma~\ref {refviaseq} we know that the \)\(-th graph of the graph distribution sequence for \) k\( is a subgraph of the \)\(-th graph of the graph distribution sequence for \) fH'\(. Using Lemma~\ref {inthomandcomp}(1)--(3) where \) I=ess(fH')\(, \) J=ess(k)\(, \) A=Gk\(, and \) ()J\( where \)\( is the inclusion map from the \)\(-th graph in the distribution graph sequence of \) k\( to the distribution graph sequence of \) fH'\(, we have that the inclusions maps induce a graph homomorphism from \) Gk\( to \) GfH'\( whose image is an internal complete subgraph, \) K'\(. Furthermore, this homomorphism sends \) k[]\( to \) fH'[]\( so \) fH'K'\(. We claim that \) [K']\( is the desired \) KGf\(.\) From the definition of \(\Psi \) , we know that we can use Lemma REF (2) and (3). That is, \(\Psi [K^{\prime }]\)  induces an internal complete subgraph of \(\mathbb {G}_f\) , and, by Lemma REF (2), \(\Psi [K^{\prime }]\)  contains \(H\) .
(\(\Leftarrow \) ) Suppose now that \(H\subseteq K\)  where \(K\)  is an internal subset of \(G_f\)  that induces a complete subgraph of \(\mathbb {G}_f\) . Then, by using Lemma REF , we have that \(\mathbb {G}_K:=\Psi ^{-1}[K]\)  is internal in \(G_{f_{H^{\prime }}}\)  and induces a complete subgraph of \(\mathbb {G}_{f_{H^{\prime }}}\) . We will use the fact that \(\mathbb {G}_K\)  is internal and complete to construct a multiplicative refinement of \(f_{H^{\prime }}\) .
Let \(2=\mathrm {ess}(f_{H^{\prime }})\) .
As \(\mathbb {G}_K\)  is internal in \(\mathbb {G}_{f_{H^{\prime }}}\)  we can express \(\mathbb {G}_K\)  in the form
\(\prod _{\alpha \in \mathrm {ess}(f_{H^{\prime }})}K_\alpha /2\) 
where \(K_\alpha \subseteq \ell _1(\alpha )\)  for all \(\alpha \in \mathrm {ess}(f_{H^{\prime }})\) . For each \(\alpha \in \mathrm {ess}(f_{H^{\prime }})\) , define \(C_\alpha \)  to be \(K_\alpha \)  if \([K_\alpha ]^2\subseteq \ell _2(\alpha )\)  and to be \(\lbrace \min K_\alpha \rbrace \)  otherwise (so that \([C_\alpha ]^2=\emptyset \subseteq \ell _2(\alpha )\)  in this case). Then \(C_\alpha \)  is complete for all \(\alpha \)  in \(\mathrm {ess}(f_{H^{\prime }})\)  and \(C_\alpha =K_\alpha \)  for 2-many \(\alpha \)  (the ultraproduct of the \(K_\alpha \)  is the complete graph \(\mathbb {G}_K\)  so 2-many \(K_\alpha \)  must induce complete subgraphs in \((\ell _1(\alpha ),\ell _2(\alpha ))\)  by Łoś theorem).
We claim that the functions defined for \(\alpha \in \mathrm {ess}(f_{H^{\prime }})\)  by \(s_1(\alpha ):=C_\alpha \)  and \(s_2(\alpha ):=[s_1(\alpha )]^2\)  belong to the conjugate for a multiplicative refinement of \(f_{H^{\prime }}\)  (multiplicative distributions must be graph-like by Lemma REF ). By Lemma REF , \(s_1\)  and \(s_2\)  determine the conjugate of a refinement of \(f_{H^{\prime }}\)  if and only if \((s_1(\alpha ),s_2(\alpha ))\)  is a subgraph of \((\ell _1(\alpha ),\ell _2(\alpha ))\)  for all \(\alpha \)  in \(\mathrm {ess}(f_{H^{\prime }})\)  and \(\eta _{f_{H^{\prime }}}[\lambda ]\subseteq s_1(\mathrm {ess}(f_{H^{\prime }}))^{2}\)  induces a complete subgraph of
\(\prod _{\alpha \in \mathrm {ess}(f_{H^{\prime }})}(s_1(\alpha ),s_2(\alpha ))/2\cong \mathbb {G}_K\) 
(note that this is a rewriting of the condition in Lemma REF (2)). These follow from
\(s_1(\alpha )=C_\alpha \subseteq K_\alpha \subseteq \ell _1(\alpha )\text{ and }s_2(\alpha )\subseteq \ell _2(\alpha )\) 
and the fact that \(C_\alpha =K_\alpha \)  for 2-many \(\alpha \)  in \(\mathrm {ess}(f_{H^{\prime }})\)  so
\(C_{\mathrm {ess}(f)}^{2}&=\mathbb {G}_K\\&\supseteq \Psi ^{-1}[H]\\&= \eta _{f_{H^{\prime }}}[\lambda ]\) 

where the last equality follows from Lemma REF (2).
Further, by Lemma REF , we know that the distribution determined by \(s_1,s_2\)  is multiplicative as \(s_2(\alpha )=[s_1(\alpha )]^2\) , making the graph \((s_1(\alpha ),s_2(\alpha ))\)  complete for each \(\alpha \)  in \(\mathrm {ess}(f_{H^{\prime }})\) .
Thus the distribution determined by \(s_1,s_2\)  is a multiplicative refinement of \(f_{H^{\prime }}\)  and has \(\mathbb {G}_K\)  as its ultragraph.
Corollary 5.10 
A graph-like distribution \(f\)  for \(p(\bar{x})\)  has a multiplicative refinement if and only if the image of \(\eta _f\)  in \(\mathbb {G}_f\)  is a subset of an internal complete subgraph.

Let \(H=\eta _f[\lambda ]\)  and \(H^{\prime }=\lbrace h_\beta :\beta \in \lambda \rbrace \)  where the \(h_\beta \)  are the functions defined in Equation (REF ). Then \(H^{\prime }\)  is a transversal of \(H\)  and
\(B_\beta =\lbrace \alpha \in \mathrm {ess}(f):\varphi _{h_\beta (\alpha )}(\bar{x};\bar{y})=\varphi _\beta (\bar{x},\bar{y})\rbrace \supseteq f(\lbrace \beta \rbrace )\in by the definitions of the \) 
\( and \) g1()\(.We claim that the distribution \) fH'\( and type \) q(x)\( defined in Lemma~\ref {hdist} are equal to \) f\( and \) p(x)\( respectively. The desired result then follows from Theorem~\ref {hmult}. To check that \) fH'=f\(, it will be enough to show that \) 1=g1\( and \) 2=g2\( by Theorem~\ref {uniqglconj}. Having \) g1()\( is equivalent to \) h()=\(, which implies \) B\(. That is,\)\(\ell _1(\alpha )=g_1(\alpha )\cap \lbrace \beta \in \lambda :\alpha \in B_\beta \rbrace =g_1(\alpha ).\)\(Having \) {,}2()\( is equivalent to \) {h(),h()}g2()\( and \) ,1()= g1()\(, so \) h()=\( and \) h()=\( and \) {,}g2()\(. The reverse argument follows the same steps in reverse.\) The type \(q(\bar{x})\)  is
\(\lbrace \varphi _\beta (\bar{x},\bar{r}_{h_\beta }):\beta <\lambda \rbrace .\) 
Since \(h_\beta (\alpha )=\beta \)  for 2-many \(\alpha \)  in \(\mathrm {ess}(f_{H^{\prime }})\) , we have that \(\bar{r}_{h_\beta }=\bar{r}_\beta \) , so \(q(\bar{x})=p(\bar{x})\) .

Graph-like Types
The particular types (\(\mathrm {SOP}_2\) -types and types expressing that cuts in linear orders are filled) that we wish to study are not only special in that there are distributions for the type that are graph-like but that, for certain choices of the representations \(\bar{r}_\beta \in \prod _{\alpha <\lambda }\mathcal {M}_\alpha \) , every distribution for the type can be extended to one that is graph-like. As we will see in Lemma REF , this special property is related to the fact that the Łoś map exhibits graph-like behavior.
Convention 6.1 From now on, we will assume that \(p(\bar{x})\)  is a \((\varphi ,\lambda )\) -type (that is, both a \(\varphi \) -type and a \(\lambda \) -type) unless otherwise stated.

Definition 6.2 
The type \(p(\bar{x})\)  is called a graph-like type if there is a choice of representatives \((\bar{r}_\beta )_{\beta <\lambda }\)  for the parameters of \(p(\bar{x})\)  so that \(L\) , the Łoś map of \(p(\bar{x})\)  with this choice of representatives, satisfies
\(L(\Delta )=\bigcap _{\Phi \in [\Delta ]^2}L(\Phi )\) 
for all finite \(\Delta \subseteq \lambda \)  with \(|\Delta |\ge 2\) .

Proposition 6.3 Every type of the form \(p(\bar{x})=\lbrace \varphi (\bar{x},\bar{a}_\beta ):\beta <\lambda \rbrace \)  of the ultraproduct \(\widehat{\mathcal {M}}=\prod _{\beta <\lambda }\mathcal {M}_\alpha / with a multiplicative distribution (i.e.\ \) p(x)\( is realized in \) M\() is graph-like.\)
If \(f\)  is a multiplicative distribution of \(p(\bar{x})\)  with parameters given by \((\bar{r}_\beta )_{\beta <\lambda }\) , then \(f\)  is graph-like by Lemma REF  and every graph in its distribution graph sequence is complete by Lemma REF . A choice of representatives that witness \(p(\bar{x})\)  being a graph-like type is given by
\(\bar{s}_\beta (\alpha )=\left\lbrace \begin{array}{ll} \bar{r}_{h_\beta (\alpha )}(\alpha );&\alpha \in \mathrm {ess}(f)\\\bar{\gamma }_\alpha ;&\text{otherwise} \end{array}\right.\) 
where the \(h_\beta \)  are the functions in \(\prod _{\alpha \in \mathrm {ess}(f)}\mathcal {M}_\alpha \)  defined in Equation (REF ) and \(\bar{\gamma }_\alpha \)  is a fixed tuple of parameters from \(\mathcal {M}_\alpha \) . The Łoś map under this choice of representatives is
\(L(\Delta )=\mathrm {ess}(f)\cup \big \lbrace \alpha \in \lambda \setminus \lbrace \mathrm {ess}(f)\rbrace :\mathcal {M}_\alpha \vDash \exists \bar{x},\, \varphi (\bar{x};\bar{\gamma }_\alpha )\big \rbrace \) 
for all \(\Delta \in \mathcal {P}_\omega (\lambda )\) , which satisfies the requirement for \(p(\bar{x})\)  to be graph-like because \(L\)  is constant.
In particular, over a \(\lambda \) -good ultrafilter \( \emph {every \)\(-type that is also a \)\(-type is graph-like}. Thus, if being graph-like is not a trivial property, it must depend on the ultrafilter \)  being considered. We are most interested in types that are graph-like independent of the choice of \( as this would appear to reveal something about the underlying structure of the type and the complete theory from which it came.\) To continue the theme of investigating the ways in which the Łoś map acts in ways similar to a distribution and to rephrase Lemma REF , we define the conjugate of the Łoś map.
Definition 6.4 
The Łoś conjugate for the type \(p(\bar{x})\)  is the sequence of functions \(k_n\colon \lambda \rightarrow \mathcal {P}([\lambda ]^n)\)  such that
\(k_n(\alpha )=\lbrace \Delta \in [\lambda ]^n: \alpha \in L(\Delta )\rbrace .\) 

Lemma 6.5 
If \(g_1\)  and \(g_2\)  are functions \(g_i\colon \lambda \rightarrow \mathcal {P}_\omega ([\lambda ]^i)\)  then \(g_1\)  and \(g_2\)  belong to the conjugate of a (unique) monotone graph-like distribution \(f\)  for the \(\lambda \) -type \(p(\bar{x})\)  in \(\widehat{\mathcal {M}}=\prod _{\alpha <\lambda }\mathcal {M}_\alpha / with the representatives \) (r)<\( if and only if the functions satisfy the conditions:\begin{enumerate}\item Let (k_n)_{n\in \omega } be the Łoś conjugate for p(\bar{x}). For all \alpha \in \lambda  we have that g_1(\alpha )\subseteq k_1(\alpha ).\item For all \alpha <\lambda  and all \Delta \in \mathcal {P}_\omega (\lambda ) with n:=|\Delta |\ge 2 and [\Delta ]^2\subseteq g_2(\alpha ) we have that \Delta \in k_n(\alpha ).\item For all \alpha \in \lambda  it is the case that g_2(\alpha )\subseteq [g_1(\alpha )]^2.\item For each \Delta \in [\lambda ]^2 the set \lbrace \alpha \in \lambda :\Delta \in g_2(\alpha )\rbrace  is an element of .\end{enumerate}\)
By comparison with Lemma REF , we see that it will be enough to show that condition (1) of this lemma is equivalent to the combination of condition (1) of Lemma REF , and that condition (2) of this lemma is equivalent to condition (2) in Lemma REF . Both of these follow from the definition of the Łoś map and the Łoś conjugate.
Lemma 6.6 
If \(p(\bar{x})\)  is a graph-like type then every distribution (with representatives witnessing \(p(\bar{x})\)  being graph-like) is a refinement of a graph-like distribution.

Let \(f\)  be a distribution for \(p(\bar{x})\)  and \((g_n)_{n\in \omega }\)  the conjugate of \(f\) . We claim that \(g_1,g_2\)  belong to the conjugate of a graph-like distribution \(f^{\prime }\)  with the property that \(f\subseteq f^{\prime }\) . We proceed by checking the conditions of Lemma REF  and then checking that \(f\)  is a refinement of the unique graph-like distribution having \(g_1\)  and \(g_2\)  in its conjugate.
\((1)\) : This is equivalent to Lemma REF (1) (for \(n=1\) ) by the definitions of the Łoś map and the Łoś conjugate. We know that \(g_1\)  satisfies the referenced condition as it belongs to the conjugate of \(f\) .
\((2)\) : If \(\Delta \in \mathcal {P}_\omega (\lambda )\)  and \(n:=|\Delta |\ge 2\)  then
\([\Delta ]^2\subseteq g_2(\alpha )\Rightarrow [\Delta ]^2\subseteq k_2(\alpha )\Rightarrow \Delta \in k_n(\alpha )\) 
where the last implication follows from \(L\)  being graph-like (see Theorem REF ).
\((3)\) : Follows from Lemma REF (2) applied to \(f\)  with \(n=2\)  and \(m=1\) .
\((4)\) : For \(\Delta \in [\lambda ]^2\) , we have that
\(\lbrace \alpha \in \lambda :\Delta \in g_2(\alpha )\rbrace \in by Lemma~\ref {distconj}(3) applied with \) 
=2\(.\) It remains to show that \(f\subseteq f^{\prime }\) . Let \((\ell _n)_{n\in \omega }\)  be the conjugate of \(f^{\prime }\) . By Lemma REF (2) applied to \(f\) , we get if \(\Delta \in \mathcal {P}_\omega (\lambda )\)  and \(\alpha \in \lambda \)  with \(\Delta \in g_n(\alpha )\)  (equivalently, \(\alpha \in f(\Delta )\) ) for \(n\ge 2\) , then
\([\Delta ]^2\subseteq g_2(\alpha )=\ell _2(\alpha ).\) 
In particular, this implies that \(\Delta \in \ell _n(\alpha )\)  by Equation (REF ) (equivalently, \(\alpha \in f^{\prime }(\Delta )\) ). We thus have that \(f(\Delta )\subseteq f^{\prime }(\Delta )\)  for all \(\Delta \in \mathcal {P}_\omega (\lambda )\)  with \(|\Delta |\ge 2\) . As \(\ell _1=g_1\) , we also have that \(f(\lbrace \beta \rbrace )\subseteq f^{\prime }(\lbrace \beta \rbrace )\)  for all \(\beta \in \lambda \)  by Equation (REF ).
Corollary 6.7 
If \(p(\bar{x})\)  is a graph-like \(\varphi \) -type of cardinality \(\lambda \) , then \(p(\bar{x})\)  is realized whenever \( has multiplicative refinements for all graph-like functions \) P().

One consequence of the Łoś map having graph-like behavior is that \(L\)  behaves almost as if it were a maximal graph-like distribution. In particular, we can construct an ultraproduct of graphs using the Łoś map as a template just as we did with graph-like distributions, and this ultragraph will contain all of the distribution ultragraphs in a compatible way (i.e. all of the embeddings of \(\lambda \)  (representing the type \(p(\bar{x})\) ) in the various ultragraphs (see Lemma REF ) will coincide in the Łoś ultragraph). By using Corollary REF  and Lemma REF , this will allow us to conclude that the graph-like type \(p(\bar{x})\)  is realized precisely in the case that the image of \(\lambda \)  in the Łoś ultragraph is contained within an internal complete subgraph.
Definition 6.8 
If \(p(\bar{x})\)  is graph-like we say that the Łoś ultragraph of \(p(\bar{x})\)  is
\(\mathbb {G}_L:=\prod _{\alpha \in \mathrm {ess}(L)}(k_1(\alpha ),k_2(\alpha ))/\) 
where \(\mathrm {ess}(L)\)  is defined analogously to \(\mathrm {ess}(f)\)  and \(=\mathrm {ess}(L)\) .

Lemma 6.9 
Suppose that \(p(\bar{x})\)  is a graph-like \((\varphi ,\lambda )\) -type and that \(f\)  is a graph-like distribution for \(p(\bar{x})\)  with conjugate \((g_n)_{n\in \omega }\) . Then \(\mathbb {G}_f\)  is an internal (not necessarily induced) subgraph of \(\mathbb {G}_L\) . In particular, the map \(i_f:\mathbb {G}_f\rightarrow \mathbb {G}_L\)  induced by the inclusions \(g_1(\alpha )\rightarrow k_1(\alpha )\)  for each \(\alpha \in \mathrm {ess}(f)\)  is an injective graph homomorphism with internal image.

Let the conjugate of \(f\)  be \((g_n)_{n\in \omega }\) . We have that \(g_1(\alpha )\subseteq k_1(\alpha )\)  and \(g_2(\alpha )\subseteq k_2(\alpha )\)  for all \(\alpha \in \mathrm {ess}(f)\)  as \(f\subseteq L\) . For each \(\alpha \in \mathrm {ess}(f)\) , let \(i_\alpha :g_1(\alpha )\rightarrow k_1(\alpha )\)  be the inclusion map and note that it is a graph homomorphism. For each \(\alpha \in \mathrm {ess}(L)\) , choose an element \(\gamma _\alpha \)  in \(k_1(\alpha )\)  (recall that \(\alpha \in \mathrm {ess}(L)\)  if and only if \(k_1(\alpha )\ne \emptyset \) ). Let \(1=\mathrm {ess}(L)\)  and \(1^{\prime }=\mathrm {ess}(f)\) . Define the map \(i_f:\mathbb {G}_f\rightarrow \mathbb {G}_L\)  given for all \(j/1^{\prime }\in \mathbb {G}_f\)  by the formula
\(i_f(j/1^{\prime })=\left[\alpha \mapsto \left\lbrace \begin{array}{ll} j(\alpha ); &\text{if }\alpha \in \mathrm {ess}(f)\\ \gamma _\alpha ; &\text{otherwise} \end{array}\right.\right]\bigg /1.\) 
As \(1^{\prime }\subseteq 1\) , the function \(i_f\)  is well-defined and injective with internal image (see Lemma REF ).
The value of \(i_f(j/1^{\prime })\)  in the above proof does not depend on the choice of \(\gamma _\alpha \)  as \(\mathrm {ess}(f)\in 1\) .
Lemma 6.10 
Let \(f,f^{\prime }\)  be two graph-like distributions for the graph-like \(\varphi \) -type \(p(\bar{x})\)  using a common sequence of representatives \((\bar{r}_\beta )_{\beta <\lambda }\)  for the parameters of \(p(\bar{x})\) . Recall the definitions of \(\eta _f\)  (Lemma REF ) and \(i_f\)  (Lemma REF ). Then the maps \(i_f\circ \eta _f\)  and \(i_{f^{\prime }}\circ \eta _{f^{\prime }}\)  are equal injective functions from \(\lambda \)  to \(\mathbb {G}_L\) .

Let the conjugates of \(f\)  and \(f^{\prime }\)  be given by \((g_n)_{n\in \omega }\)  and \((g^{\prime }_n)_{n\in \omega }\)  respectively.
Fix some \(\beta \in \lambda \)  and let
\(h_\beta \in \prod _{\alpha \in \mathrm {ess}(f)}g_1(\alpha )\;\text{ and }\;h^{\prime }_\beta \in \prod _{\alpha \in \mathrm {ess}{f^{\prime }}}g^{\prime }_1(\alpha )\) 
be the representatives for \(\eta _f(\beta )\)  and \(\eta _{f^{\prime }}(\beta )\)  given by Equation (REF ) (applied to \(\eta _f,h_\beta \)  and \(\eta _{f^{\prime }},h_\beta ^{\prime }\)  respectively). Define \(1=\mathrm {ess}(f)\)  and \(1^{\prime }=\mathrm {ess}(f^{\prime })\) . Then we have that
\(\lbrace \alpha \in \mathrm {ess}(L):h_\beta (\alpha )=h^{\prime }_\beta (\alpha )\rbrace &\supseteq \lbrace \alpha \in \mathrm {ess}(L):\beta \in g_1(\alpha )\cap g^{\prime }_1(\alpha )\rbrace \\&=f(\lbrace \beta \rbrace )\cap f^{\prime }(\lbrace \beta \rbrace )\\&\in \) 

Applying Łoś theorem to the representatives for \(i_f(h_\beta /1)\)  and \(i_{f^{\prime }}(h^{\prime }_\beta /1^{\prime })\)  given in Equation (REF ) shows that \(i_f(\eta _f(\beta ))=i_{f^{\prime }}(\eta _{f^{\prime }}(\beta ))\) . \(i_f\circ \eta _f\)  is injective because both \(i_f\)  and \(\eta _f\)  are.
Definition 6.11 
If \(p(\bar{x})\)  is a graph-like \(\varphi \) -type, we will denote by \(\eta _L\)  the unique map \(\lambda \rightarrow \mathbb {G}_L\)  that can be written as \(i_f\circ \eta _f\)  for any graph-like distribution \(f\)  of \(p(\bar{x})\) .

Identifying the subgraph induced by \(\eta _L[\lambda ]\)  in \(\mathbb {G}_L\)  allows us to capture much of the information contained within distributions by looking at internal subgraphs of \(\mathbb {G}_L\)  that contain \(\eta _L[\lambda ]\)  as a complete subgraph and that are hyperfinite. We record a proof of this correspondence here but will not use it until the next section.
Definition 6.12 A subset \(A\)  of an ultraproduct \(\prod _{\alpha <\lambda }\mathcal {M}_\alpha / is called \emph {hyperfinite} if it can be expressed as an ultraproduct \) <A/ where each \(A_\alpha \)  is a finite subset of \(M_\alpha \) . We say that a structure is hyperfinite if its underlying set is hyperfinite.

A hyperfinite subset of an ultraproduct \(\widehat{\mathcal {M}}=\prod _{\alpha <\lambda }\mathcal {M}_\alpha / is necessarily an internal subset of \) M\( as every hyperfinite subset is expressible as an ultraproduct of subsets of \) M\(.\)
Theorem 6.13 
Let \(p(\bar{x})\)  be a graph-like type with Łoś conjugate \((k_n)_{n\in \omega }\)  and let \(H\subseteq \mathbb {G}_L\) . Then the following are equivalent:

\(H\)  is hyperfinite with \(\eta _L[\lambda ]\subseteq H\) .

There is a graph-like distribution \(f\)  for \(p(\bar{x})\)  such that \(i_f[G_f]=H\) .

Moreover, if \(H=\prod _{\alpha <\lambda }H_\alpha / with each \) H\( finite, then \) f\( can be taken so that \) if[Gf]\( is the subgraph of \) GL\( induced by \) H\( and so that, if \) (G)<\( is the distribution graph sequence of \) f\(, the graph \) G\( is the subgraph of \) k1(),k2()\( induced by \) H\( for all \) <\(.\)
\((2)\Rightarrow (1)\) : The ultragraph \(\mathbb {G}_f\)  is hyperfinite because the distribution graph sequence of \(f\)  consists of finite graphs. Let \(i_\alpha \)  be the inclusion \(g_1(\alpha )\rightarrow k_1(\alpha )\) . Then the image of \(i_f\)  is equal to \(\prod _{\alpha <\lambda } i_\alpha [G_\alpha ]/, so we have that the set \) H=if[Gf]\( is hyperfinite. This is a specific case of internal functions preserving hyperfinite sets.\)\((1)\Rightarrow (2)\) : Let \(\mathbb {H}=\langle H,E^{\mathbb {H}}\rangle \)  be the subgraph of \(\mathbb {G}_L\)  induced by \(H\)  and pick finite \(H_\alpha \subseteq k_1(\alpha )\)  so that \(H=\prod _{\alpha <\lambda }H_\alpha /. Then \) H=<H/ where each \(\mathbb {H}_\alpha \)  is the finite subgraph of \(\mathbb {K}_\alpha :=\langle k_1(\alpha ),k_2(\alpha )\rangle \)  induced by \(H_\alpha \) . We claim that \((\mathbb {H}_\alpha )_{\alpha <\lambda }\)  is the distribution graph sequence of a graph-like distribution \(f\)  of \(p(\bar{x})\) . We verify that \((\mathbb {H}_\alpha )_{\alpha <\lambda }\)  satisfies the conditions of Lemma REF  (\(g_1(\alpha )=H_\alpha \)  and \(g_2(\alpha )=E^{\mathbb {H}_\alpha }\)  following the definition of a graph distribution sequence).
Conditions \((1)\) -\((3)\)  of Lemma REF  are equivalent to \(\mathbb {H}_\alpha \)  being a subgraph of \(\mathbb {K}_\alpha \)  given that \(p(\bar{x})\)  is graph-like. Condition \((4)\)  is equivalent to \(\eta _L[\lambda ]\)  inducing a complete subgraph in \(\mathbb {H}\) , which is equivalent to \(\eta _L[\lambda ]\)  inducing a complete subgraph of \(\mathbb {G}_L\) .
The result now follows from the fact that \(i_f\)  is the inclusion of \(\mathbb {H}\)  in \(\mathbb {G}_L\) .
Theorem 6.14 
Suppose that \(p(\bar{x})\)  is a graph-like \(\varphi \) - and \(\lambda \) -type with Łoś map \(L\) . Then \(p(\bar{x})\)  is realized in \(\widehat{\mathcal {M}}\)  if and only if the image of \(\eta _L:\lambda \rightarrow \mathbb {G}_L\)  is a subset of an internal \(A\subseteq G_L\)  that induces a complete subgraph.

(\(\Rightarrow \) ): The type \(p(\bar{x})\)  is realized if and only if there is a multiplicative distribution \(j\)  for \(p(\bar{x})\)  by Fact REF . Then, by Corollary REF , \(j\)  is a graph-like distribution for \(p(\bar{x})\)  and, by Lemma REF  and Lemma REF , with \(\mathbb {G}_j\)  being an internal complete subgraph of \(\mathbb {G}_L\) . Moreover, by Lemma REF , \(i_j\circ \eta _j=\eta _L\)  so \(i_j[\mathbb {G}_j]\)  contains the image of \(\eta _L\) . Thus \(i_j[\mathbb {G}_j]\)  is an internal subset of \(\mathbb {G}_L\)  extending \(\eta _L[\lambda ]\)  and inducing a complete subgraph.
(\(\Leftarrow \) ): By Lemma REF  we have that \(\eta _f[\lambda ]=\eta _L[\lambda ]\)  for any graph-like distribution \(f\)  of \(p(\bar{x})\) . Using Corollary REF  then shows that every graph-like distribution has a multiplicative refinement, which is equivalent to \(p(\bar{x})\)  being realized by Fact REF .
Corollary 6.15 
If \(p(\bar{x})\)  is a graph-like type and \(f\)  is a graph-like distribution such that \(i_f[\mathbb {G}_f]\)  is an induced subgraph of \(\mathbb {G}_L\)  then the type \(p(\bar{x})\)  is realized if and only if \(f\)  has a multiplicative refinement.

\((\Rightarrow )\) : If \(p(\bar{x})\)  is realized, then, by Theorem REF , there is a complete internal subgraph \(\mathbb {K}\)  of \(\mathbb {G}_L\)  containing \(\eta _L[\lambda ]=i_f\circ \eta _f[\lambda ]\) . We must have that \(i_f\)  preserves non-edges because the image of \(i_f\)  is an induced subgraph and we already know that \(i_f\)  is injective. By Lemma REF (2) and (4) and the internal definition of \(i_f\) , we have that \(\mathbb {K}^{\prime }:=i_f^{-1}[\mathbb {K}]\)  is a complete internal subgraph of \(\mathbb {G}_f\)  containing \(\eta _f[\lambda ]\) . Thus, by Corollary REF , the distribution \(f\)  has a multiplicative refinement.
\((\Leftarrow )\) : If \(f\)  has a multiplicative refinement, then \(p(\bar{x})\)  is realized by Fact REF .
Corollary 6.16 
For a graph-like type \(p(\bar{x})\)  with representatives witnessing \(p(\bar{x})\)  being graph-like, \(p(\bar{x})\)  is realized in \(\widehat{\mathcal {M}}\)  if and only if every distribution \(f\)  extends to a distribution \(\hat{f}\)  that has a multiplicative refinement. Moreover, the extension \(\hat{f}\)  can be taken so that if \((g_n)_{n\in \omega }\)  is the conjugate of \(f\)  and \((\hat{g}_n)_{n\in \omega }\)  is the conjugate of \(\hat{f}\)  then

\(g_1(\alpha )=\hat{g}_1(\alpha )\)  and

\(\langle \hat{g}_1(\alpha ),\hat{g}_2(\alpha )\rangle \)  is an induced subgraph of \(\langle k_1(\alpha ),k_2(\alpha )\rangle \)  where \((k_n)_{n\in \omega }\)  is the Łoś conjugate of \(p(\bar{x})\) .


(\(\Rightarrow \) ): Let \(\hat{g}_1(\alpha )=g_1(\alpha )\)  and \(\hat{g}_2(\alpha )=k_2(\alpha )\cap [g_1(\alpha )]^2\) . Then \(\mathbb {G}_{\hat{f}}\)  is an induced subgraph of \(\mathbb {G}_L\)  and we can use Corollary REF .
(\(\Leftarrow \) ): The existence of any distribution having a multiplicative refinement is equivalent to \(p(\bar{x})\)  having a multiplicative refinement by Fact REF .

Graph-like Formula Sets and their Shapes
It is frequently useful (as in the definition of \(\mathrm {SOP}_2\) -types) to restrict attention to certain subsets of the possible parameters for a \(\varphi \) -type by specifying where the representatives for the parameters can come from in each index structure \(\mathcal {M}_\alpha \) . We will generally choose these parameters to be such that the resulting \(\varphi \) -types are guaranteed to be graph-like. We begin with some definitions that allow us to talk about this situation more concretely.
Definition 7.1 
Given a formula \(\varphi (\bar{x};\bar{y})\)  in a language \(\mathcal {L}\) , a \(\varphi \) -set is a nonempty collection \(A\subseteq M^n\)  where \(M\)  is the universe of some structure \(\mathcal {M}\)  in the language \(\mathcal {L}\)  and the length of the tuple \(\bar{y}\)  is \(n\) .

Note: unless explicitly stated, we will not require \(\mathcal {M}\)  to be an ultraproduct.
Definition 7.2 
If \(\varphi (\bar{x},\bar{y})\)  is a formula and \(A\)  is a \(\varphi \) -set in some structure \(\mathcal {M}\)  then we call \(A\)  a graph-like \(\varphi \) -set if for all \(B\subseteq A\)  such that \(2\le |B|<\aleph _0\)  we have that the set \(\lbrace \varphi (\bar{x};\bar{a}):\bar{a}\in B\rbrace \)  is consistent if and only if for all \(C\in [B]^2\)  the set \(\lbrace \varphi (\bar{x};\bar{a}):\bar{a}\in C\rbrace \)  is consistent.

We study what the collection of graphs arising from these types look like and what these collections can tell us about the possible range of types that can be created by using parameters from \(A\) .
Definition 7.3 
If \(A\)  is a graph-like \(\varphi \) -set coming from the structure \(\mathcal {M}\)  then the shape of \(A\), denoted \(\mathrm {Sh}(A)\) , is defined to be the set of pairs \((\mathbb {G},\theta )\)  where

there is an \(m\in \omega \setminus \lbrace 0\rbrace \)  so that \(\mathbb {G}\)  is a finite simple graph with vertices \(\lbrace 1,2,\ldots ,m\rbrace \) ,

\(\theta \)  is a function \(G\rightarrow A\) ,

for each \(i\in G\)  we have that \(\mathcal {M}\vDash \exists \bar{x},\,\varphi (\bar{x};\theta (i))\) , and

there is an edge between distinct \(i\)  and \(j\)  in \(\mathbb {G}\)  if and only if
\(\mathcal {M}\vDash \exists \bar{x},\,\varphi (\bar{x};\theta (i))\wedge \varphi (\bar{x};\theta (j)).\) 


Definition 7.4 
Let \((A_\alpha )_{\alpha <\lambda }\)  be a sequence of \(\varphi \) -sets in the structures \((\mathcal {M}_\alpha )_{\alpha <\lambda }\) . We say that a \(\varphi \) -type \(p(\bar{x})\)  of \(\widehat{M}=\prod _{\alpha <\lambda }\mathcal {M}_\alpha / is an \emph {\) (A)\(-type} when there is a sequence \) (r)<\( of representatives for the parameters in \) p(x)\( such that for each index \) <\( the set \) {r():<}\( is a subset of \) A\(. That is, \) p(x)\( is an \) (A)\(-type precisely when the parameters for \) p(x)\( come from the set \) A.

The next result is a demonstration of the fact that \(\mathrm {Sh}(A_\alpha )\)  (where \((A_\alpha )_{\alpha <\lambda }\)  is a sequence of \(\varphi \) -sets) captures the notion of which graphs are induced subgraphs of the corresponding graph in the distribution graph sequence for the Łoś ultragraph of an \((A_\alpha )\) -type. This will allow us to apply Corollary REF  to distributions \(f\)  of the \((A_\alpha )\) -type \(p(\bar{x})\)  whose distribution graph sequence comes from \(\mathrm {Sh}(A_\alpha )\)  for each \(\alpha <\lambda \) . That is, all such distributions \(f\)  having multiplicative refinements will be equivalent to all \((A_\alpha )\) -types in \(\widehat{\mathcal {M}}\)  being realized in \(\widehat{\mathcal {M}}\) . The remainder of this section will be dedicated to determining the form that such distributions must take and how to interpret these statements using the conjugate distribution and ultragraph.
Lemma 7.5 
Let \((A_\alpha )_{\alpha <\lambda }\)  be a sequence of graph-like \(\varphi \) -sets coming from structures \((\mathcal {M}_\alpha )_{\alpha <\lambda }\)  all in the common language \(\mathcal {L}\)  and let \(p(\bar{x})\)  be an \((A_\alpha )\) -type. Let \(f\)  be a distribution for \(p(\bar{x})\)  with representatives \((\bar{r}_\beta )_{\beta <\lambda }\)  witnessing that \(p(\bar{x})\)  is an \((A_\alpha )\) -type and let \((g_n)_{n\in \omega }\)  and \((\mathbb {G}_\alpha )_{\alpha <\lambda }\)  be the conjugate and distribution graph sequence of \(f\) . Fix \(\alpha <\lambda \) . Then there is an element \((\mathbb {G},\theta )\)  of \(\mathrm {Sh}(A_\alpha )\)  and a graph isomorphism \(\psi \colon \mathbb {G}_\alpha \rightarrow \mathbb {G}\)  with the property that \(\theta (\psi (\beta ))=\bar{r}_\beta (\alpha )\)  for each \(\beta \in \mathbb {G}_\alpha \)  if and only if \(\mathbb {G}_\alpha \)  is an induced subgraph of \(\langle k_1(\alpha ),k_2(\alpha )\rangle \)  where \((k_n)_{n\in \omega }\)  is the Łoś conjugate for \(p(\bar{x})\) .

Let \(\beta _0,\ldots ,\beta _m\)  enumerate the vertices of \(\mathbb {G}_\alpha \)  and define \(G:=\lbrace 1,\ldots ,m\rbrace \) ,
\(\theta (i):=\bar{r}_{\beta _i}(\alpha )\) 
for each \(i\in G\) , and \(\psi (\beta _i):=i\) . Let \(\mathbb {G}\)  be the unique graph with underlying set \(G\)  and such that \((\mathbb {G},\theta )\in \mathrm {Sh}(A_\alpha )\) . Then \(\mathbb {G}_\alpha \)  being an induced subgraph of \(\langle k_1(\alpha ),k_2(\alpha )\rangle \)  is the same as saying that there is an edge between \(\beta ,\gamma \)  in \(\mathbb {G}_\alpha \)  if and only if
\(\mathcal {M}_\alpha \vDash \exists \bar{x},\,\varphi (\bar{x},\bar{r}_\beta (\alpha ))\wedge \varphi (\bar{x},\bar{r}_\gamma (\alpha ))\) 
which is equivalent to saying that \(\psi (\beta )\)  and \(\psi (\gamma )\)  are edge related in \(\mathbb {G}\) . Note that we did not have any choice (up to permuting the enumeration given for \(\mathbb {G}_\alpha \) ) in picking \(G\) , \(\theta \) , and \(\psi \) .
It will be useful in characterizing the distributions of \((A_\alpha )\) -types to know which sequences of graphs \((\mathbb {G}_\alpha )_{\alpha <\lambda }\)  occurring in \(\mathrm {Sh}(A_\alpha )\)  can appear as the distribution graph sequence of an \((A_\alpha )\) -type (see Theorem REF ). For such a graph sequence, it is necessary that we can find an induced subgraph \(\mathbb {H}\)  of \(\mathbb {G}:=\prod _{\alpha <\lambda }\mathbb {G}_\alpha / that is complete, has cardinality \)\(, and has maps \) G\( such that the induced map \) : G maps \(\mathbb {H}\)  bijectively to \(\lambda \subseteq \lambda ^ (this \) H\( will be the image of \) f\( where \) f\( is the distribution under consideration). As the following lemma shows, this is enough.\)
Lemma 7.6 
Let \((A_\alpha )_{\alpha <\lambda }\)  be a sequence of graph-like \(\varphi \) -sets coming from the structures \((\mathcal {M}_\alpha )_{\alpha <\lambda }\)  all in the common language \(\mathcal {L}\) . Suppose that

there is a set \(B\in  and a sequence \) (G,)B\( such that for all \) B\( we have that \) (G,)Sh(A)\(,\item for each \) B\( there is a subset \) Y\( of \)\( with \) |Y|=|G|\( and for each \)\( the set \) X:={B:Y}\( is an element of \) , and

there are fixed bijections \(\iota _\alpha \colon Y_\alpha \rightarrow \mathbb {G}_\alpha \)  for each \(\alpha \in B\)  such that the sequence \((\iota _\alpha )_{\alpha \in B}\)  satisfies
\(\lbrace \alpha \in B:\mathbb {G}_\alpha \vDash \iota _\alpha (\beta )\mathrel {E}\iota _\alpha (\gamma )\rbrace \in for each \) 
,}[]2\(.\) 
Then there is a graph-like \(\varphi \) -type \(p(\bar{x})\)  in \(\widehat{\mathcal {M}}=\mathcal {M}_\alpha ^ and a distribution \) f\( for \) p(x)\( for which\begin{enumerate}\item (\mathbb {H}_\alpha )_{\alpha <\lambda }, the distribution graph sequence of f, is such that \mathbb {H}_\alpha \cong \mathbb {G}_\alpha  for all \alpha \in B,\item \mathrm {ess}(f)= B, and\item for all \alpha \in B we have that \mathbb {H}_\alpha  is an induced subgraph of \langle k_1(\alpha ),k_2(\alpha )\rangle  where (k_n)_{n\in \omega } is the Łoś conjugate.\end{enumerate}\)
Convention 7.7 In order to make sense of (3) in the lemma statement and several similar statements made in the proof below, we say that \(\mathbb {G}_\alpha \vDash \psi (\bar{a})\)  is false if any of the elements of \(\bar{a}\)  are not in the underlying set of \(\mathbb {G}_\alpha \)  or are undefined values of a function.

We begin by defining the type \(p(\bar{x})\)  and the distribution \(f\) , and then check that these values of \(p(\bar{x})\)  and \(f\)  satisfy conditions \((4)\) –\((6)\) . For each \(\beta \in \lambda \)  fix a function \(\bar{r}_\beta \)  defined by \(\alpha \mapsto \theta _\alpha (\iota _\alpha (\beta ))\)  when \(Y_\alpha \)  is defined and \(\beta \in Y_\alpha \) , and \(\bar{r}_\beta (\alpha )\)  is an arbitrary value of \(A_\alpha \)  for all other values of \(\alpha \)  in \(\lambda \) . Define a collection of formulas \(p(\bar{x})\)  by
\(p(\bar{x}):=\lbrace \varphi \left(\bar{x},\bar{r}_\beta /):\beta <\lambda \rbrace .\right.\) 
The collection \(p(\bar{x})\)  is a type because, for any finite \(\Delta \subseteq \lambda \)  with \(|\Delta |\ge 2\) , we have that
\(\llbracket \Delta \rrbracket ^{p(\bar{x})} &=\lbrace \alpha \in \lambda :\forall \lbrace \beta ,\gamma \rbrace \in [\Delta ]^2,\,\mathcal {M}_\alpha \vDash \exists \bar{x},\,\varphi (\bar{x},\bar{r}_\beta (\alpha ))\wedge \varphi (\bar{x},\bar{r}_\gamma (\alpha ))\rbrace \\&\supseteq \lbrace \alpha \in B:\forall \lbrace \beta ,\gamma \rbrace \in [\Delta ]^2,\, \mathbb {G}_\alpha \vDash \iota _\alpha (\beta )\mathrel {E}\iota _\alpha (\gamma )\rbrace \\&=\bigcap _{\lbrace \beta ,\gamma \rbrace \in [\Delta ]^2}\lbrace \alpha \in B:\mathbb {G}_\alpha \vDash \iota _\alpha (\beta )\mathrel {E}\iota _\alpha (\gamma )\rbrace \\&\in {align*}by condition~(3) of the lemma statement as well as the fact that \Delta  (and hence [\Delta ]^2) is finite. Moreover, p(\bar{x}) is an (A_\alpha )-type and therefore a graph-like type.\) 
We use Theorem REF  to find a distribution \(\hat{f}\)  of \(p(\bar{x})\)  and then show that there is a refinement \(f\)  of \(\hat{f}\)  satisfying conditions (4)–(6). Define
\(H_\alpha :=\left\lbrace \begin{array}{ll} Y_\alpha ; &\alpha \in B\\ \lbrace 0\rbrace ; &\text{otherwise} \end{array}\right.\) 
and consider the hyperfinite set \(H:=\prod _{\alpha <\lambda }H_\alpha /. In particular, \) Hk1()\(, so \) H\( is a hyperfinite subset of \) GL\(. Furthermore, condition (2) guarantees that \) L[]H\(. By Theorem~\ref {extendingetalequalsdistribution}, there is a graph-like distribution \) f\( such that \) if[Gf]\( is the subgraph of \) GL\( induced by \) H\( and such that the distribution graph sequence \) (G)<\( of \) f\( consists of the subgraphs of \) k1(),k2()\( induced by \) H\(. We claim that \) GG\( is a graph isomorphism for all \) B\(. Let \) ,\( be distinct elements of \) G\(. Then{\begin{@align*}{1}{-1}\beta \mathrel {E}^{\hat{\mathbb {G}}_\alpha }\gamma &\iff \lbrace \beta ,\gamma \rbrace \in k_2(\alpha )\\&\iff \mathcal {M}_\alpha \vDash \exists \bar{x},\, \varphi (\bar{x},\bar{r}_\beta (\alpha ))\wedge \varphi (\bar{x},\bar{r}_\gamma (\alpha ))\\&\iff \mathcal {M}_\alpha \vDash \exists \bar{x},\, \varphi (\bar{x},\theta _\alpha (\iota _\alpha (\beta )))\wedge \varphi (\bar{x},\theta _\alpha (\iota _\alpha (\gamma )))\\&\iff \iota _\alpha (\beta ) \mathrel {E}^{\mathbb {G}_\alpha }\iota _\alpha (\gamma ).\end{@align*}}This is enough to show that \)\( is a graph isomorphism as \)\( is defined to be a bijection between the underlying sets of \) G\( and \) G\(. Moreover, by Corollary~\ref {indsublug}, the type \) p(x)\( is realized in \) M\( if and only if \) f\( has a multiplicative refinement.\) As suggested by the above results, the desired refinement \(f\)  of \(\hat{f}\)  is the same distribution but with the information carried by \(\mathbb {G}_\alpha \)  removed when \(\alpha \in \lambda \setminus B\) . This can be achieved by setting \(f(\Delta )=\hat{f}(\Delta )\cap B\)  for all \(\Delta \in \mathcal {P}_\omega (\lambda )\) . As \(B\in , the ultragraph of \) f\( will be isomorphic to the ultragraph of \) f\(. This isomorphism sends \) f[]\( to \) f[]\( so Corollary~\ref {multiffint} implies that \) f\( has a multiplicative refinement if and only if \) f\( has a multiplicative refinement.\)
For most of our applications we will not need to keep careful track of the function \(\theta \)  associated with an element of \(\mathrm {Sh}(A)\) , so we focus instead on the isomorphism types of the graphs \(\mathbb {G}\)  that appear in \(\mathrm {Sh}(A)\) .
Definition 7.8 If \(A\)  is a graph-like \(\varphi \) -set coming from the structure \(\mathcal {M}\)  then the isomorphism shape of \(A\), denoted \(\mathrm {isoSh}(A)\) , is the collection
\(\lbrace \mathrm {isoType}(\mathbb {G}):(\mathbb {G},\theta )\in \mathrm {Sh}(A)\rbrace \) 
of graph isomorphism types that arise from \(\mathrm {Sh}(A)\) , where \(\mathrm {isoType}(\mathbb {G})\)  is the isomorphism type of the graph \(\mathbb {G}\) .

Lemma 7.9 
Let \((A_\alpha )_{\alpha <\lambda }\)  be a sequence of graph-like \(\varphi \) -sets coming from the structures \((\mathcal {M}_\alpha )_{\alpha <\lambda }\)  and let \(f\colon \mathcal {P}_\omega (\lambda )\rightarrow  be a graph-like function such that\begin{enumerate}\item f is monotone and satisfies condition (2) in the definition of a distribution~(Definition~\ref {distribution}) and\item the graph sequence of f, given by (\mathbb {G}_\alpha )_{\alpha <\lambda }, is such that the isomorphism type of \mathbb {G}_\alpha  is an element of \mathrm {isoSh}(A_\alpha ) for all \alpha \in \mathrm {ess}(f).\end{enumerate}Then there is an \) (A)\(-type \) p(x)\( of \) M:=<M/ and representatives \((\bar{r}_\beta )_{\beta <\lambda }\)  such that \(f\)  has a multiplicative refinement if and only if \(p(\bar{x})\)  is realized.

We proceed by checking that \(f\)  gives us enough information to satisfy conditions (1)–(3) of Lemma REF .
REF (1): \(\mathrm {ess}(f)\in  and, as \) G\( has its isomorphism type in \) isoSh(A)\(, we may choose some \) (G',)Sh(A)\( and an isomorphism \) GG'\( for each \) ess(f)\(.\)REF (2): For each \(\alpha \in \mathrm {ess}(f)\) , let \(Y_\alpha =G_\alpha \) . Then
\(X_\beta =\lbrace \alpha \in \lambda :\beta \in G_\alpha \rbrace =f(\lbrace \beta \rbrace )\in by Equation~(\ref {disteqconj}).\) 
REF (3): For each \(\lbrace \beta ,\gamma \rbrace \in [\lambda ]^2\)  we have that
\(\lbrace \alpha \in \mathrm {ess}(f):\mathbb {G}^{\prime }_\alpha \vDash \iota _{\alpha }(\beta ) \mathrel {E} \iota _\alpha (\gamma )\rbrace =f(\lbrace \beta ,\gamma \rbrace )\in by the same reasoning as above.\) 
We then have that there is an \((A_\alpha )\) -type \(p(\bar{x})\)  for which \((\mathbb {G}_\alpha )_{\alpha <\lambda }\)  is the distribution graph sequence of a distribution \(f^{\prime }\)  that has a multiplicative refinement if and only if \(p(\bar{x})\)  is realized. Since graph-like functions are determined by their graph sequence, we must have that \(f\)  has a multiplicative refinement if and only if \(p(\bar{x})\)  is realized.
Sometimes we will want to talk about induced subgraphs of graphs \(\mathbb {G}\)  arising in \(\mathrm {Sh}(A)\)  but will not care about the specific mapping \(\theta \)  that tell us what element of \(A\)  each vertex corresponds to. In order to do this, we introduce some terminology to speak about induced subgraphs of isomorphism types.
Convention 7.10 Given an isomorphism type \(\mathrm {isoType}(\mathbb {G})\) , we will say that a graph \(\mathbb {H}\)  (or isomorphism type \(\mathrm {isoType}(\mathbb {H})\) ) is an induced subgraph of \(\mathrm {isoType}(\mathbb {G})\)  and write \(\mathbb {H}\le \mathrm {isoType}(\mathbb {G})\)  if there is an injective graph homomorphism \(\psi \colon \mathbb {H}\rightarrow \mathbb {G}\)  that also preserves non-edges.

We will characterize the isomorphism shape not by which isomorphism types belong to the isomorphism shape, but by the minimal graphs that cannot appear as induced subgraphs of elements of the isomorphism shape. This follows, roughly speaking, from the fact that induced subgraphs of \(\mathbb {G}\)  with \((\mathbb {G},\theta )\in \mathrm {Sh}(A)\)  are easily obtained by taking a subset of the vertices in \(\mathbb {G}\)  and the corresponding restriction to the function \(\theta \)  and from the well-used fact in graph combinatorics that classes \(\mathcal {C}\)  of graphs that are closed under taking subgraphs are characterized by the minimal graphs not occurring in \(\mathcal {C}\) .
Lemma 7.11 
Suppose that \(A\)  is a graph-like \(\varphi \) -set in the structure \(\mathcal {M}\)  and \(\mathbb {H}\)  a graph such that \(\mathrm {isoType}(\mathbb {H})\)  is not an element of \(\mathrm {isoSh}(A)\) . If \(\mathrm {isoType}(\mathbb {G})\in \mathrm {isoSh}(A)\)  then \(\mathbb {H}\nleq \mathrm {isoType}(\mathbb {G})\) .

Suppose that there were an element \((\mathbb {G},\theta )\in \mathrm {Sh}(A)\)  with \(\psi \colon \mathbb {H}\rightarrow \mathbb {G}\)  an injective homomorphism preserving non-edges. Let \(C\)  be \(\psi [H]\) . We may assume without loss of generality that \(C\)  is an initial segment of \(\lbrace 1,2,\ldots ,m\rbrace =G\) . Define \(\theta \text{\,}\mathord {\upharpoonright }\text{\,}C\)  be the restriction of \(\theta \)  to \(C\)  and \(\mathbb {G}_C\)  to be the subgraph of \(\mathbb {G}\)  induced by \(C\) . Then \((\mathbb {G}_C,\theta \text{\,}\mathord {\upharpoonright }\text{\,}C)\in \mathrm {Sh}(A)\)  with \(\mathbb {G}_C\cong \mathbb {H}\) , a contradiction.
Theorem 7.12 
Suppose that \(A\)  is a graph-like \(\varphi \) -set in the structure \(\mathcal {M}\)  and that \(\Xi \)  is a collection of isomorphism types of finite graphs such that both

\(\Xi \cap \mathrm {isoSh}(A)=\emptyset \)  and

whenever the \(\mathrm {isoType}\mathbb {H}\)  is not an element of \(\mathrm {isoSh}(A)\)  there is some \(\xi \in \Xi \)  for which \(\xi \le \mathrm {isoType}(\mathbb {H}\) ).

Then
\(\mathrm {isoSh}(A)=\lbrace \mathrm {isoType}(\mathbb {G}):\forall \xi \in \Xi ,\, \xi \nleq \mathrm {isoType}(\mathbb {G})\rbrace .\) 

Suppose that \(\mathrm {isoType}(\mathbb {H})\)  is not in \(\mathrm {isoSh}(A)\) . Then, by assumption \((2)\) , there exists \(\xi \)  in \(\Xi \)  with \(\xi \le \mathrm {isoType}(\mathbb {H})\) . If \(\mathrm {isoType}(\mathbb {G})\in \mathrm {isoSh}(A)\) , then by assumption \((1)\)  and Lemma REF  it cannot be that any element of \(\Xi \)  is an induced subgraph of \(\mathrm {isoType}(\mathbb {G})\) .
Knowing the set of \(\le \) -minimal isomorphism types of graphs that cannot appear in \(\mathrm {isoSh}(A)\)  (call this set \(\Gamma \) ) is enough to determine all of \(\mathrm {isoSh}(A)\) . We will extract some extra information that is implicit in this characterization of isomorphism shapes in order to characterize the functions that can appear as distributions for \((A_\alpha )\) -types. We know that graphs \(\mathbb {H}\)  whose isomorphism types appear in \(\Gamma \)  cannot be induced subgraphs of graphs arising in \(\mathrm {Sh}(A)\) , but \(\mathbb {H}\)  may still appear as a subgraph of graphs arising in \(\mathrm {Sh}(A)\) . More precisely, \(\mathrm {isoType}(\mathbb {G})\)  is an element of \(\mathrm {isoSh}(A)\)  exactly in the case that whenever a graph \(\mathbb {H}\) , representing an element of \(\Gamma \) , is a subgraph of \(\mathbb {G}\) , we must have that \(\mathbb {H}\)  is not an induced subgraph of \(\mathbb {G}\)  (that is, \(\mathbb {G}\)  must contain edges that do not occur in \(\mathbb {H}\) ).
Definition 7.13 
Let \(S\)  be a set of graphs (or graph isomorphism types) and \(\mathbb {H}\)  a graph such that for each \(\mathbb {G}\in S\)  we have that \(\mathbb {H}\nleq \mathrm {isoType}(\mathbb {G})\) . A collection \(B\subseteq [H]^2\setminus E^\mathbb {H}\)  is called necessary for \(\mathbb {H}\)  in \(S\) if whenever \(\mathbb {G}\in S\)  and there is an injective graph homomorphism \(\psi \colon \mathbb {H}\rightarrow \mathbb {G}\)  then some element of
\(\lbrace \lbrace \psi (a),\psi (b)\rbrace :(a,b)\in B\rbrace \) 
appears in the edge relation for \(\mathbb {G}\) .

Remark 7.14 The definition of necessary sets for \(\mathbb {H}\)  in \(S\)  depends only on the isomorphism types of graphs that occur in \(S\) . Because of this, we sometimes speak of necessary sets for \(\mathbb {H}\)  in a collection of isomorphism types of graphs.

We will typically be interested in necessary sets that are minimal in cardinality or minimal under the \(\subseteq \)  relation. Our applications are in the particular case that \(S=\mathrm {isoSh}(A)\)  for some graph-like \(\varphi \) -set \(A\)  and \(\mathbb {H}\)  is a minimal graph not appearing as an induced subgraph of any graph arising in \(\mathrm {Sh}(A)\) . In this situation, we will be able to use Theorem REF  to gain some information about the structure of the conjugate for a distribution \(f\)  of an \((A_\alpha )\) -type, which can then be translated into information about the distribution \(f\)  and will allow us to recognize what sorts of distributions are allowed for \((A_\alpha )\) -types.
Lemma 7.15 
Suppose that \(p(\bar{x})\)  is a \(\lambda \) -type in \(\widehat{\mathcal {M}}=\prod _{\alpha <\lambda }\mathcal {M}_\alpha / and that \) f\( is a graph-like distribution for \) p(x)\( with distribution graph sequence \) (G)<\(. Let \) H\( be a graph that is not an induced subgraph of any of the \) isoType(G)\( and let \) BH[H]2EH\(. Then \) f\( satisfies\)\(\bigcap _{\lbrace a,b\rbrace \in E^{\mathbb {H}}}f(\lbrace x(a),x(b)\rbrace )\subseteq \bigcup _{\lbrace c,d\rbrace \in B_{\mathbb {H}}}f(\lbrace x(c),x(d)\rbrace )\)\( for all injective functions \) xH\( if and only if the set \) BH\( is necessary for \) H\( in \) {G:ess(f)}\(.\)
(\(\Leftarrow \) ): Let \(x\colon H\rightarrow \lambda \)  be an injective function. We wish to show that if
\(\alpha \in \bigcap _{\lbrace a,b\rbrace \in E^\mathbb {H}} f(\lbrace x(a),x(b)\rbrace )\,\text{ then }\,\alpha \in \bigcup _{\lbrace c,d\rbrace \in B_\mathbb {H}}f(\lbrace x(c),x(d)\rbrace ).\) 
By the definition of the distribution graph sequence, saying \(\alpha \)  is an element of \(f(\lbrace x(a),x(b)\rbrace )\)  is equivalent to the statement that \(x(a)\)  and \(x(b)\)  are edge related in \(\mathbb {G}_\alpha \) . We then have that (REF ) is equivalent to
\(\mathbb {G}_\alpha \vDash \bigwedge _{\lbrace a,b\rbrace \in E^\mathbb {H}}x(a)\mathrel {E} x(b)\rightarrow \bigvee _{\lbrace c,d\rbrace \in B_\mathbb {H}} x(c)\mathrel {E} x(d)\) 
for all \(\alpha <\lambda \) . This says that if \(x\)  can be thought of as an injective graph homomorphism \(\mathbb {H}\rightarrow \mathbb {G}_\alpha \) , then one of the edges in \(B_\mathbb {H}\)  must also appear in \(\mathbb {G}_\alpha \) . This follows from the definition of \(B_\mathbb {H}\)  being necessary for \(\mathbb {H}\)  in the collection of \(\mathbb {G}_\alpha \) .
\((\Rightarrow )\) : Suppose that \(x:\mathbb {H}\rightarrow \mathbb {G}_\alpha \)  is an injective graph homomorphism. As \(G_\alpha \subseteq \lambda \)  and \(x\)  is a homomorphism, we have that
\(\alpha \in \bigcap _{\lbrace a,b\rbrace \in E^{\mathbb {H}}}f(\lbrace x(a),x(b)\rbrace )=\big \lbrace \alpha \in \lambda :\forall \lbrace a,b\rbrace \in E^{\mathbb {H}},\, \lbrace x(a),x(b)\rbrace \in E^{\mathbb {G}_\alpha }\big \rbrace .\) 
By assumption we then have that
\(\alpha \in \bigcup _{\lbrace c,d\rbrace \in B_\mathbb {H}}f(\lbrace x(c),x(d)\rbrace )=\big \lbrace \alpha \in \lambda :\exists \lbrace c,d\rbrace \in B_{\mathbb {H}},\, \lbrace x(c),x(d)\rbrace \in E^{\mathbb {G}_\alpha }\big \rbrace .\) 
That is, there is some pair \(\lbrace c,d\rbrace \in B_\mathbb {H}\)  for which \(x(c)\)  and \(x(d)\)  are edge related in \(\mathbb {G}_\alpha \) , as required.
Theorem 7.16 
Suppose that the sequence \((A_\alpha )_{\alpha <\lambda }\)  is a sequence of graph-like \(\varphi \) -sets in the structures \((\mathcal {M}_\alpha )_{\alpha <\lambda }\)  having a common language and such that for all \(\alpha ,\delta <\lambda \)  we have that \(\mathrm {isoSh}(A_\alpha )=\mathrm {isoSh}(A_\delta )\) . Let \(\Gamma \)  be the collection of \(\le \) -minimal isomorphsim types of graphs not contained in \(\mathrm {isoSh}(A_0)\) , and for each graph \(\mathbb {H}\in \Gamma \) , let \(B_{\mathbb {H}}\)  be a necessary set for \(\mathbb {H}\)  in \(\mathrm {isoSh}(A_0)\) . Then every \(\lambda \) -type that is also an \((A_\alpha )\) -type is realized in \(\widehat{\mathcal {M}}\)  if and only if every graph-like function \(f\colon \mathcal {P}_\omega (\lambda )\rightarrow  satisfying\begin{equation}\bigcap _{\lbrace a,b\rbrace \in E^{\mathbb {H}}}f(\lbrace x(a),x(b)\rbrace )\subseteq \bigcup _{\lbrace c,d\rbrace \in B_{\mathbb {H}}}f(\lbrace x(c),x(d)\rbrace )\end{equation}for all \) H\( and all injective functions \) xH\( has a multiplicative refinement.\)
(\(\Rightarrow \) ): Let \(f\)  be a graph-like function satisfying (), let \(g_1,g_2\)  belong to the conjugate of \(f\) , and fix \(\mathbb {H}\in \Gamma \) . By Lemma REF , the \(B_\mathbb {H}\)  are necessary for \(\mathbb {H}\)  in the graph sequence of \(f\) . Thus, if \(\mathbb {H}\in \Gamma \)  and \(B_\mathbb {H}\)  is non-empty, we must have that \(\mathbb {H}\)  cannot be an induced subgraph of \(\mathbb {G}_\alpha :=\langle g_1(\alpha ),g_2(\alpha )\rangle \)  for all \(\alpha <\lambda \) . Even if \(B_\mathbb {H}\)  is empty, we then have that \(\mathbb {H}\)  cannot even be a subgraph of any of the \(\mathbb {G}_\alpha \)  since in this case the right-hand side of () is \(\emptyset \) , so \(\mathbb {H}\nleq \mathbb {G}_\alpha \)  for all \(\mathbb {H}\in \Gamma \)  and all \(\alpha <\lambda \) . Then the graphs \(\mathbb {G}_\alpha \)  are elements of \(\mathrm {Sh}(A_0)\)  by Theorem REF . By Lemma REF , there is an \((A_\alpha )\) -type \(p(\bar{x})\)  that is realized if and only if \(f\)  has a multiplicative refinement, and, by assumption, all \((A_\alpha )\) -types are realized in \(\widehat{\mathcal {M}}\) .
(\(\Leftarrow \) ): Let \(p(\bar{x})\)  be an \((A_\alpha )\) -type of \(\widehat{\mathcal {M}}\)  having cardinality \(\lambda \)  and choose a set of representatives \((r_\beta )_{\beta <\eta }\)  for the parameters of \(p(\bar{x})\)  from \(\prod _{\alpha <\lambda }A_\alpha \)  and notice that these representatives witness \(p(\bar{x})\)  being graph-like. Let \(f\)  be a distribution for \(p(\bar{x})\)  using the same representatives. By Corollary REF  it must be that \(f\)  is a refinement of graph-like distribution \(\hat{f}\)  with the property that \((\hat{g}_n)_{n\in \omega }\) , the conjugate of \(\hat{f}\) , is such that \(\hat{g}_1=g_1\)  (where \(g_1\)  comes from the conjugate of \(f\) ) and the graphs \(\hat{\mathbb {G}}_\alpha :=\langle \hat{g}_1(\alpha ),\hat{g}_2(\alpha )\rangle \)  are induced subgraphs of \(\langle k_1(\alpha ),k_2(\alpha )\rangle \)  where \((k_n)_{n\in \omega }\)  is the Łoś conjugate of \(p(\bar{x})\) . In particular, for all \(\alpha \in \mathrm {ess}(f)\)  we know that \(\hat{\mathbb {G}}_\alpha \)  is isomorphic to a graph arising in \(\mathrm {Sh}(A_\alpha )\)  by Lemma REF . Lemma REF  guarantees that \(\hat{f}\)  satisfies (), so \(\hat{f}\)  has a multiplicative refinement by assumption. Thus, by Fact REF , the type \(p(\bar{x})\)  is realized.
Theorem 7.17 
Let \( be a regular ultrafilter on the infinite cardinal \)\(, \) A\( be a graph-like \)\(-set in the structure \) M\(, and \)\( be the set of \)\(-minimal graph isomorphism types not occurring in \) isoSh(A)\(. Then the following are equivalent:\begin{enumerate}\item Every (A)-type of \widehat{\mathcal {M}}:=\mathcal {M}^ with cardinality \le \lambda  is realized.\item If (\mathbb {G}_\alpha )_{\alpha <\lambda } is a sequence of (possibly infinite) graphs with the property that for every \gamma \in \Gamma  and \alpha <\lambda  we have that \gamma \nleq \mathrm {isoType}(\mathbb {G}_\alpha ) (i.e.\ every finite induced subgraph of \mathrm {isoType}(\mathbb {G}_\alpha ) is an element of \mathrm {isoSh}(A)), then the ultraproduct \mathbb {G}:=\mathbb {G}_\alpha ^ has the property that every complete H\subseteq \mathbb {G} with |H|=\lambda  extends to an internal complete subgraph of \mathbb {G}.\end{enumerate}\)
\((1)\Rightarrow (2)\) :
We proceed by constructing an \((A)\) -type \(p(\bar{x})\)  in \(\widehat{\mathcal {M}}\)  by taking advantage of the fact that the isomorphism types of the factors of \(\mathbb {G}\)  belong to \(\mathrm {isoSh}(A)\) . We then show that a multiplicative distribution for \(p(\bar{x})\)  in \(\widehat{\mathcal {M}}\)  gives instructions for extending \(H\)  to an internal complete subgraph of \(\mathbb {G}\) .
For each \(\alpha <\lambda \)  choose a pair \((\mathbb {G}^{\prime }_\alpha ,\theta _\alpha )\)  in \(\mathrm {Sh}(A)\)  with a graph isomorphism \(\psi _\alpha \colon \mathbb {G}_\alpha \rightarrow \mathbb {G}^{\prime }_\alpha \) . Enumerate the elements of \(H\)  as \((h_\beta )_{\beta <\lambda }\)  and pick representatives \(x_\beta \in \prod _{\alpha <\lambda }\mathbb {G}_\alpha \)  for each \(h_\beta \) . For each \(\alpha ,\beta <\lambda \) , define
\(\bar{r}_\beta (\alpha )=\theta _\alpha (\psi _\alpha (x_\beta (\alpha )))\) 
and consider the collection of formulas \(p(\bar{x})=\lbrace \varphi (\bar{x},\bar{r}_\beta /:\beta <\lambda \rbrace \) . We claim that \(p(\bar{x})\)  is an \((A)\) -type of \(\widehat{\mathcal {M}}\) . It will be enough to check that \(p(\bar{x})\)  is a type as the image of \(\theta _\alpha \)  is always a subset of \(A\) .
If \(\Delta \in \mathcal {P}_\omega (\lambda )\) , then, because \(A\)  is graph-like, we have that
\(\llbracket \Delta \rrbracket ^{p(\bar{x})} &=\lbrace \alpha \in \lambda :\forall \lbrace \beta ,\gamma \rbrace \in [\Delta ]^2,\,\mathcal {M}_\alpha \vDash \exists \bar{x},\,\varphi (\bar{x},\bar{r}_\beta (\alpha ))\wedge \varphi (\bar{x},\bar{r}_\gamma (\alpha ))\rbrace \\&=\lbrace \alpha \in \lambda : \forall \lbrace \beta ,\gamma \rbrace \in [\Delta ]^2,\, \mathbb {G}^{\prime }_\alpha \vDash \psi _\alpha (x_\beta (\alpha ))\mathrel {E} \psi _\alpha (x_\gamma (\alpha ))\rbrace \\&=\lbrace \alpha \in \lambda : \forall \lbrace \beta ,\gamma \rbrace \in [\Delta ]^2,\, \mathbb {G}_\alpha \vDash x_\beta (\alpha )\mathrel {E} x_\gamma (\alpha )\rbrace \\&=\bigcap _{\lbrace \beta ,\gamma \rbrace \in [\Delta ]^2}\lbrace \alpha \in \lambda :\mathbb {G}_\alpha \vDash x_\beta (\alpha )\mathrel {E} x_\gamma (\alpha )\rbrace \) 

Then, as \(x_\beta /h_\beta \)  and \(x_\gamma /h_\gamma \)  are neighbors in \(\mathbb {G}\)  and \([\Delta ]^2\)  is finite, we have that this last set is an element of \( by Łoś theorem and the fact that ultrafilters are closed under finite intersection.\) By assumption, the type \(p(\bar{x})\)  is realized in \(\widehat{\mathcal {M}}\)  so, by Fact REF , we may choose a multiplicative distribution \(f\)  for \(p(\bar{x})\)  and we may assume that \(\mathrm {ess}(f)=\lambda \)  (if not, let \(f^{\prime }(\Delta )=f(\Delta )\)  if \(\Delta \ne \lbrace 0\rbrace \)  and set \(f^{\prime }(\lbrace 0\rbrace )=f(\lbrace 0\rbrace )\cup (\lambda \setminus \mathrm {ess}(f))\) . Then \(f^{\prime }\)  is a multiplicative distribution of \(p(\bar{x})\)  and \(\mathrm {ess}(f^{\prime })=\lambda \) ). We will use the information contained in \(f\)  to extend \(H\) .
Let \((g_n)_{n\in \omega }\)  be the conjugate of \(f\) . For each \(\alpha <\lambda \) , define \(\mathbb {H}_\alpha \)  to be the subgraph of \(\mathbb {G}_\alpha \)  induced by the set
\(\psi _\alpha ^{-1}[\lbrace \psi _\alpha (x_\beta (\alpha )):\beta \in g_1(\alpha )\rbrace ]=\lbrace x_\beta (\alpha ):\beta \in g_1(\alpha )\rbrace .\) 
Because \(\psi _\alpha \)  and \(\psi ^{-1}_\alpha \)  are graph isomorphisms and because the graph \(\langle g_1(\alpha ),g_2(\alpha )\rangle \)  is complete by Lemma REF , we must have that \(\mathbb {H}_\alpha \)  is complete for all \(\alpha <\lambda \) . Thus \(\widehat{\mathbb {H}}:=\prod _{\alpha <\lambda }\mathbb {H}_\alpha / is complete by Łoś theorem and is internal by construction. Furthermore, \) H\( extends \) H\( as \) x()H\( whenever \) f({})\( and \) f({}).
\((2)\Rightarrow (1)\) : Let \(p(\bar{x})\)  be an \((A)\) -type of \(\widehat{\mathcal {M}}\)  of cardinality \(\lambda \) . We then have that \(p(\bar{x})\)  is a graph-like type, witnessed by representations of the parameters coming from \(A^\lambda \) . The type \(p(\bar{x})\)  is realized in \(\widehat{\mathcal {M}}\)  if and only if the Łoś ultragraph \(\mathbb {G}_L\)  has the property that the complete subgraph induced by \(\eta _L[\lambda ]\)  extends to an internal complete subgraph of \(\mathbb {G}_L\)  (see Theorem REF ).

Applications to the \(\mathrm {SOP}\)  Hierarchy
\(\mathrm {SOP}_2\)  and Comparability in Trees
We know from the definition of \(\mathrm {SOP}_2\)  (Definition REF ) that whenever \(A\)  is a \(\varphi \) -set whose elements form an \(\mathrm {SOP}_2\) -tree within the structure \(\mathcal {M}\)  then any \(B\subseteq A\)  creates a consistent collection of formula
\(p_B(\bar{x})=\lbrace \varphi (\bar{x},\bar{b}):\bar{b}\in B\rbrace \) 
if and only if \(B\)  is a subset of a branch of the \(\mathrm {SOP}_2\) -tree whose elements come from \(A\) . In other words, \(p_B(\bar{x})\)  is consistent if and only if every pair \(\bar{b},\bar{b}^{\prime }\in B\)  is comparable in the \(\mathrm {SOP}_2\) -tree (that is, \(B\)  is a linear sub-order of the tree). We thus have that the \(\varphi \) -set \(A\)  is graph-like and the shape of \(A\)  is the collection of all finite graphs \(\mathbb {G}\)  that can be obtained from taking a finite (multi-)subset of the full binary tree. There are edges between the two distinct vertices \(b\)  \(b^{\prime }\)  in \(\mathbb {G}\)  if and only if \(b\)  and \(b^{\prime }\)  are comparable in the full binary tree. Fortunately, most of the combinatorial work of determining the isomorphism types of such graphs has already been done by [1]}.
Definition 8.1 
We say that a tuple \((\varphi , A)\)  witnesses \(\mathrm {SOP}_2\)  in a structure \(\mathcal {M}\) if there is an \(\mathrm {SOP}_2\) -tree
\((\varphi (\bar{x};\bar{y}),(\bar{a}_\eta )_{\eta \in 2^{<\omega }})\) 
in \(\mathcal {M}\)  such that \(A=\lbrace a_\eta :\eta \in 2^{<\omega }\rbrace \) .

Lemma 8.2 
Suppose that \(\varphi \)  is a formula and \(A\)  is a \(\varphi \) -set such that the pair \((\varphi ,A)\)  witnesses \(\mathrm {SOP}_2\)  in the structure \(\mathcal {M}\) . Then \(A\)  is a graph-like \(\varphi \) -set and the set \(\Gamma \)  of \(\le \) -minimal isomorphism types not in \(\mathrm {isoSh}(A)\)  are the two isomorphism types:
\(C_4:=\hbox{\begin{tikzpicture}{enclosed/.style={draw, circle, inner sep=0pt, minimum size=.1cm, fill=black}}\end{tikzpicture}\node [enclosed] (1) at (0.75,.75) {};\node [enclosed] (2) at (1.5,.75) {};\node [enclosed] (3) at (0.75,0) {};\node [enclosed] (4) at (1.5,0) {};}(1) -- (2);(2) -- (4);(1) -- (3);(3) -- (4);\) 
    and    4:=  .
\(\) 
Because \((\varphi , A)\)  witnesses \(\mathrm {SOP}_2\)  in \(\mathcal {M}\) , there is a surjection \(h:2^{<\omega }\rightarrow A\)  with the property that a subset \(B\)  of \(2^{<\omega }\)  is linearly ordered if and only if the collection of formulas
\(p_B(\bar{x})=\lbrace \varphi (\bar{x},h(s)): s\in B\rbrace \) 
is consistent in \(\mathcal {M}\) . If \(s\in 2^{<\omega }\) , we will denote \(h(s)\)  by \(\bar{a}_s\) . Let \(\Delta \in \mathcal {P}_\omega (2^{<\omega })\) . Then the set of formula \(\lbrace \varphi (\bar{x},\bar{a}_s):s\in \Delta \rbrace \)  is consistent (equivalently, realized) in \(\mathcal {M}\)  if and only if the set \(\Delta \)  is linearly ordered as a suborder of \(2^{<\omega }\)  if and only if the elements of \(\Delta \)  are pair-wise comparable in the ordering on \(2^{<\omega }\) . Thus the elements \((\mathbb {G},\theta )\)  of \(\mathrm {Sh}(A)\)  where \(\theta \colon G \rightarrow A\)  is injective are such that \(\mathbb {G}\)  is the graph of the comparability relation for a finite suborder of \(2^{<\omega }\)  (equivalently, \(\mathbb {G}\)  is the graph of the comparability relation for a finite forest of subtrees of \(2^{<\omega }\) ; i.e. the connected components of \(\mathbb {G}\)  correspond to finite subtrees of \(2^{<\omega }\) ). Every finite collection of finite trees can be embedded as a suborder of \(2^{<\omega }\) , so the shape of \(A\)  contains every possible disjoint union of finitely many comparability graphs arising from finite trees. We claim that no other isomorphism types appear in \(\mathrm {isoSh}(A)\) . We postpone the proof of the claim to study the structure of these isomorphism types in more detail.
By [1]} a finite connected graph \(\mathbb {G}=(G,E)\)  is the comparability graph of a tree if and only if for all distinct \(x_0,x_1,x_2,x_3\in G\)  the formula
\(x_0\mathrel {E}x_1\mathrel {E}x_2\mathrel {E}x_3\rightarrow (x_0\mathrel {E} x_2)\vee (x_1\mathrel {E} x_3)\) 
holds (called the diagonal property). Clearly, every graph \(\mathbb {G}\)  with \(|G|\le 3\)  satisfies the diagonal property. Suppose that a graph with vertices \(\lbrace 0,1,2,3\rbrace \)  does not satisfy the diagonal property. We may suppose that \(0\mathrel {E}1\mathrel {E} 2\mathrel {E} 3\) . If these are the only edges, the graph is \(\ell _4\)  and clearly not diagonal. Now there are only 3 possible edges that can be added, \(\lbrace 0,3\rbrace ,\lbrace 1,3\rbrace ,\)  or \(\lbrace 0,2\rbrace \) . If just \(\lbrace 0,3\rbrace \)  is added, we have a graph isomorphic to \(C_4\) , which is not diagonal. We wish to show that the remaining possibilities are all diagonal.
The complete graph on 4 elements is the comparability graph of a tree that is a 4 element linear order. Up to isomorphism, the remaining possibilities are the comparability graphs of the two trees
\(\hbox{\begin{tikzpicture}{enclosed/.style={draw, circle, inner sep=0pt, minimum size=.1cm, fill=black}}\end{tikzpicture}\node [enclosed] (1) at (0,0) {};\node [enclosed] (2) at (0,0.3) {};\node [enclosed] (3) at (0,0.6) {};\node [enclosed] (4) at (.3,.3) {};}(1) -- (2);(2) -- (3);(1) -- (4);\) 
         
\(and so are diagonal.\) 
If \(\mathbb {G}\)  is a non-diagonal graph with greater than 4 vertices, there must be a 4-vertex induced subgraph of \(\mathbb {G}\)  that is not diagonal (pick the four vertices to be a set of vertices witnessing the fact that the graph is not diagonal). Thus a graph \(\mathbb {G}\)  is diagonal if and only if \(\mathbb {G}\)  is the disjoint union of a collection of comparability graphs of trees if and only if \(C_4\nleq \mathbb {G}\)  and \(\ell _4\nleq \mathbb {G}\) .
It remains to check that \(\mathrm {isoSh}(A)\)  consists of precisely the finite graph isomorphism types that are diagonal. We already know that the \((\mathbb {G},\theta )\in \mathrm {Sh}(A)\)  with \(\theta \)  injective have the property that \(\mathbb {G}\)  is diagonal (such graphs are the comparability graphs of a finite subtree of the full binary tree). Suppose that \((\mathbb {G},\theta )\in \mathrm {Sh}(A)\)  and \(\theta \)  is not injective. Suppose that \(\mathbb {G}\)  is not diagonal. As before, we need only look at a set of vertices \(V:=\lbrace v_0,v_1,v_2,v_3\rbrace \)  that witness the failure of the diagonal property. In particular, \(V\)  must have the property that the subgraph of \(\mathbb {G}\)  induced by \(V\)  is either \(C_4\)  or \(\ell _4\)  as these are the only non-diagonal 4-vertex graphs. Because \((V,\theta \text{\,}\mathord {\upharpoonright }\text{\,}V)\)  is an element of \(\mathrm {Sh}(A)\)  and because \(V\)  is diagonal, \(\theta \text{\,}\mathord {\upharpoonright }\text{\,}V\)  is not injective. Suppose that \(\theta (v_i)=\theta (v_j)\)  for a distinct pair of indices \(i,j\in \lbrace 0,1,2,3\rbrace \) . Then the two vertices \(v_i\)  and \(v_j\)  share the same neighbors (other than each other) and are neighbors of each other by the definition of \(\mathrm {Sh}(A)\) . One can check that no distinct pair of vertices in \(C_4\)  or \(\ell _4\)  satisfy this condition. Thus \(\mathbb {G}\)  is diagonal.
In order to use the information in Lemma REF  to characterize the graph-like distributions of \(\mathrm {SOP}_2\) -types, we will need to determine the necessary sets for the two graph isomorphism types in \(\mathrm {isoSh}(A)\) .
Lemma 8.3 
With \(\varphi \) , \(A\) , and \(\Gamma \)  as in Lemma REF , the \(\subseteq \) -minimal necessary sets for the elements of \(\Gamma \)  in \(\mathrm {Sh}(A)\)  are the edges:
\(\hbox{\begin{tikzpicture}[circle dotted/.style={line width = 0.3mm, dash pattern= on .05mm off 1mm, line cap = round}]{enclosed/.style={draw, circle, inner sep=0pt, minimum size=.1cm, fill=black}}\end{tikzpicture}\node [enclosed] (1) at (0.75,.75) {};\node [enclosed] (2) at (1.5,.75) {};\node [enclosed] (3) at (0.75,0) {};\node [enclosed] (4) at (1.5,0) {};}(1) -- (2);(2) -- (4);(1) -- (3);(3) -- (4);[circle dotted] (1) -- (4);[circle dotted] (2) -- (3);\) 
    and    
\(where the dotted edges represent the elements of the corresponding necessary sets.\) 
By the diagonal characterization of graphs arising from the comparability relation on finite trees in [1]}, the analysis in the proof of Lemma REF , and Lemma REF , the above sets are necessary for \(\ell _4\)  and \(C_4\) . Since both \(C_4\)  and \(\ell _4\)  become diagonal when any one of the dotted edges is added, these necessary sets are \(\subseteq \) -minimal.
This analysis allows us to give both a characterization of the distributions of \(\mathrm {SOP}_2\) -types as well as giving a new characterization of good ultrafilters in terms of which complete subgraphs of ultragraphs with factors coming from \(\mathrm {Sh}(A)\)  can be extended to internal complete subgraphs.
Theorem 8.4 
Let \( be a regular ultrafilter on the infinite cardinal \)\(. Then the following are equivalent:\begin{enumerate}\item  is good.\item If \mathcal {M} is a structure and (\varphi ,A) witness \mathrm {SOP}_2 in \mathcal {M} then every (A)-type of cardinality \le \lambda  in \widehat{\mathcal {M}}:=\mathcal {M}^ is realized in \widehat{\mathcal {M}}.\item For all sequences of graphs (\mathbb {G}_\alpha )_{\alpha <\lambda } such that C_4\nleq \mathbb {G}_\alpha  and \ell _4\nleq \mathbb {G}_\alpha  for all \alpha <\lambda  the ultraproduct \mathbb {G}:=\mathbb {G}_\alpha ^ has the property that every complete H\subseteq \mathbb {G} with |H|=\lambda  is contained within an internal complete subgraph of \mathbb {G}.\item Every graph-like function f:P_\omega (\lambda )\rightarrow  that satisfiesf(\lbrace x_0,x_1\rbrace )\cap f(\lbrace x_1,x_2\rbrace )\cap f(\lbrace x_2,x_3\rbrace )\subseteq f(\lbrace x_0,x_2\rbrace )\cup f(\lbrace x_1,x_3\rbrace ) for all distinct x_0,x_1,x_2,x_3\in \lambda  has a multiplicative refinement.\end{enumerate}\)
\((1)\)\(\iff \)\((2)\) : This is a restatement of the fact that a regular ultrafilter \( is good if and only if \)  realizes all \(\mathrm {SOP}_2\) -types over sets of size \(\lambda \) , which is proved by Malliaris and Shelah in [4]} (see Conclusion 11.9 and Main Theorem 11.11).
\((2)\)\(\iff \)\((3)\) : This is a special case of Theorem REF .
\((2)\)\(\iff \)\((4)\) : Combining Theorem REF  and Lemma REF  we have that every \((A)\) -type of \(\widehat{\mathcal {M}}\)  of cardinality \(\lambda \)  is realized in \(\widehat{\mathcal {M}}\)  if and only if both
\(f(\lbrace x_0,x_1\rbrace )\cap f(\lbrace x_1,x_2\rbrace )\cap f(\lbrace x_2,x_3\rbrace )&\subseteq f(\lbrace x_0,x_2\rbrace )\cup f(\lbrace x_1,x_3\rbrace )\\f(\lbrace x_0,x_3\rbrace )\cap f(\lbrace x_0,x_1\rbrace )\cap f(\lbrace x_1,x_2\rbrace )\cap f(\lbrace x_2,x_3\rbrace )&\subseteq f(\lbrace x_0,x_2\rbrace )\cup f(\lbrace x_1,x_3\rbrace )\) 

whenever \(x_0,x_1,x_2,x_3\)  are distinct elements of \(\lambda \) . As the intersection on the left-hand side of the second condition is always a subset of the left-hand side of the first condition, both conditions are satisfied if and only if the first condition is satisfied.
Remark 8.5 The condition on \(f\)  in statement \((4)\)  of Theorem REF  is a direct translation of requiring that the distribution graph sequence for \(f\)  consists of graphs satisfying the diagonal property. That is, by Lemma REF , statement \((4)\)  requires that the distribution graph sequence of \(f\)  consists of induced subgraphs of the Łoś graph sequence for some \(\mathrm {SOP}_2\) -type in \(\widehat{\mathcal {M}}\) .

Cuts in Linear Orders and \(\mathrm {SOP}\)
We make an analysis of types that witness a cut in an ultrapower of an infinite linear order being filled. This analysis follows the same basic structure as the analysis of \(\mathrm {SOP}_2\) -types presented above, but is slightly complicated by the shape corresponding to such types being more complicated. We first characterize the graphs \(\mathbb {G}\)  whose vertices are open intervals in some linear order \(\mathbb {L}\)  and which have an edge between two intervals \(I_1\)  and \(I_2\)  if and only if \(I_1\cap I_2\)  is nonempty in \(\mathbb {L}\) . Such graphs will be the elements of the shapes of the types being studied. Conveniently, the isomorphism types of these graphs will not depend on the linear order under consideration (see Lemma REF  below). Because of this, we will call such graphs interval intersection graphs without any reference to the linear order from which the intervals come from.
Lemma 8.6 
Suppose that \(\mathbb {L}=(L,<)\)  is an infinite linear order and that \(\varphi (x;a,b)\)  is the formula \(a<x<b\) . Then \(L^2\)  is a graph-like \(\varphi \) -set and the set \(\Gamma \)  of \(\le \) -minimal graphs not in \(\mathrm {Sh}(L^2)\)  consists exactly of the graphs/graph families:
\(\mathrm {I}:=\hbox{\begin{tikzpicture}{enclosed/.style={draw, circle, inner sep=0pt, minimum size=.1cm, fill=black}}\end{tikzpicture}\node [enclosed] (1) at (0,0) {};\node [enclosed] (2) at (0,.75*0.5) {};\node [enclosed] (3) at (0,1.5*0.5) {};\node [enclosed] (4) at (-0.65*0.5,-0.375*0.5) {};\node [enclosed] (5) at (-1.3*0.5,-.75*0.5) {};\node [enclosed] (6) at (0.65*0.5,-0.375*0.5) {};\node [enclosed] (7) at (1.3*0.5,-.75*0.5) {};}(1) -- (2);(2) -- (3);(1) -- (4);(4) -- (5);(1) -- (6);(6) -- (7);\) 
         II:=         III:=
\(\) 
IVm:=         Vn:=
\(where \) 
4\(, \) m2\(, and \) n1\( (in \) V1\( the nodes labeled \) 1\( and \) n\( are the same node).\)
That \(L^2\)  is a graph-like \(\varphi \) -set follows from the fact that \(\lbrace \varphi (x;a_i,b_i):i\in \lbrace 0,1,\dots ,n\rbrace \rbrace \)  is consistent if and only if the interval \((\max _i a_i,\min _j b_j)\)  is non-empty and that this is equivalent to the intersection \((a_i,b_i)\cap (a_j,b_j)\)  being nonempty for all \(i,j\in \lbrace 0,1,\dots ,n\rbrace \) .
The statement of the lemma is now equivalent to asking that the above graphs are the \(\le \) -minimal graphs that cannot arise in the following way: the vertices are a finite collection of possibly repeated non-empty open intervals in \(\mathbb {L}\)  and there is an edge between two intervals if and only if their intersection is non-empty.
This result (with distinct intervals) is proved in the particular case that \(\mathbb {L}=\mathbb {R}\)  by Lekkekerker and Boland [5]}. Our strategy will be to reduce the general case to the case of distinct intervals in \(\mathbb {R}\) . That is, we show that \(\mathrm {isoSh}(\mathbb {L}^2)\)  is equal to the set of isomorphism types of interval intersection graphs in \(\mathbb {R}\)  arising from distinct intervals.
First, we note that we may assume that \(\mathbb {L}\)  contains \((\omega ,<)\)  as a suborder (if not, the reverse order on \(\mathbb {L}\)  works). Suppose that \(\mathbb {G}\)  is the intersection graph for the collection of open intervals \(\lbrace (a_i,b_i):i\in \lbrace 0,1,\dots ,n\rbrace \rbrace \)  where \(a_i,b_i\in \mathbb {R}\) . We may then construct a set of intervals in \(\omega \)  by stretching out all of the \((a_i,b_i)\)  and translating them to the positive half of \(\mathbb {R}\)  so that the images of \((a_i,b_i)\)  and \((a_j,b_j)\)  intersect in \(\omega \)  if and only if \((a_i,b_i)\cap (a_j,b_j)\ne \emptyset \)  and hence our new intervals have an intersection graph isomorphic to the intersection graph of the \((a_i,b_i)\) . Mapping these intervals to intervals of \(\mathbb {L}\)  via the inclusion \(\omega \hookrightarrow \mathbb {L}\)  does not change the intersection graph so long as we did not allow intersections to look like \((n,n+1)\)  in \(\omega \)  (this can be achieved by choosing how much to stretch out the original intervals in \(\mathbb {R}\) ). Thus the set of intersection graphs in \(\mathbb {L}\)  contains all of the intersection graphs in \(\mathbb {R}\) .
For the other inclusion, suppose that \(\mathbb {G}=(\lbrace I_i:i\in \lbrace 0,1,\dots ,n\rbrace \rbrace ,E)\)  is the intersection graph for the (possible repeating) non-empty intervals \(I_i\)  in \(\mathbb {L}\) . Let \(I_i=(a_i,b_i)\)  and, for each \(\lbrace I_i,I_j\rbrace \in E\) , choose an element \(e_{ij}\in I_i\cap I_j\) . Define an order \(\mathbb {M}\)  with underlying set the union of the sets
\(&\lbrace a_i:i\in \lbrace 0,1,\dots ,n\rbrace \rbrace \\&\lbrace b_i:i\in \lbrace 0,1,\dots ,n\rbrace \rbrace \\&\lbrace e_{ij}:i<j,\lbrace I_i,I_j\rbrace \in E\rbrace \) 

and with ordering given by \(<^\mathbb {L}\) . \(\mathbb {M}\)  is finite and so isomorphic to an initial segment of \(\omega \) . The map \(\mathbb {M}\hookrightarrow \omega \hookrightarrow \mathbb {R}\)  sends the intervals \(I_i\)  to intervals of \(\mathbb {R}\)  having the same intersection graph as the \(I_i\) . If the intervals \(I_{i_0},\dots ,I_{i_m}\)  are equal (and none of the other intervals are equal to \(I_{i_0}\) ), then we may take the distinct intervals
\(\left\lbrace \left(a_{i_0}+\frac{j}{m+1},b_{i_0}-\frac{j}{m+1}\right):j\in \lbrace 0,\dots ,m\rbrace \right\rbrace \) 
to be the intervals corresponding to the \(I_{i_j}\)  without changing the intersection graph.
For the next several propositions we fix the following suppositions: \(\mathcal {M}\)  is a structure with an infinite \(L\subseteq M\)  (not necessarily definable!) and a definable binary relation \(<\)  on \(\mathcal {M}\)  such that \(<\)  restricts to a linear ordering on \(L\)  that contains a copy of \(\omega \)  (as an ordered set). Let \(\varphi (x;y,z)\)  be the formula \(y<x<z\) .
The following fact from [5]} will be useful for determining minimal necessary sets for the graphs that cannot arise as the intersection graph of a finite collection of intervals.
Definition 8.7 A graph \(\mathbb {G}\)  has an irreducible cycle of length \(n\) if there are \(n\)  distinct vertices \(v_1,\dots ,v_n\)  of \(\mathbb {G}\)  such that \(v_1v_2\ldots v_{n-1}v_nv_1\)  is a path and there is an edge between \(v_i\)  and \(v_j\)  if and only if \(i=j\pm 1\pmod {n}\)  .

Fact 8.8 
A finite graph \(\mathbb {G}\)  is not able to be represented as the intersection graph of a finite collection of intervals if and only if it has at least one of the two following properties:

\(\mathbb {G}\)  has an irreducible cycle of length \(\ge 4\) .

\(\mathbb {G}\)  has a collection of three vertices that are pairwise not neighbors and, for each of the three vertices \(v\) , there is a path \(P\)  between the other two vertices such that \(v\)  is not a neighbor of any vertex in \(P\) .


Definition 8.9 A graph \(\mathbb {G}\)  is called asteroidal if it satisfies the condition of Fact REF (2). If \(\mathbb {G}\)  is a graph and the vertices \(A=\lbrace v_1,v_2,v_3\rbrace \)  witness \(\mathbb {G}\)  being asteroidal, we will say that \(A\)  is an asteroidal set in \(\mathbb {G}\).

We will use the notion of asteroidal sets to help us to determine the necessary sets for the minimal asteroidal graphs given in Lemma REF . In particular, we know that if \(A\)  is asteroidal in the graph \(\mathbb {G}\)  and \(\mathbb {G}^{\prime }\)  is an interval intersection graph extending \(\mathbb {G}\)  then there must be some \(a\in A\)  and \(g\in \mathbb {G}\)  such that \(a\)  and \(g\)  are neighbors in \(\mathbb {G}^{\prime }\)  but not in \(\mathbb {G}\)  (see Lemma REF ). There does not appear to be a nice way other than this to determine what the necessary sets are, so the proofs determining the minimal necessary sets will largely proceed by ruling out all of the elements not in the necessary set one at a time.
Lemma 8.10 
Let \(\mathbb {G}\)  be an asteroidal graph and \(A=\lbrace v_1,v_2,v_3\rbrace \)  be asteroidal in \(\mathbb {H}\)  with paths \(P_{v_i}\)  between the nodes \(A\setminus \lbrace v_i\rbrace \)  for each \(1\le i\le 3\)  witnessing \(A\)  being asteroidal in \(\mathbb {G}\) . Then any interval intersection graph \(\mathbb {G}^{\prime }\)  having \(\mathbb {G}\)  as a subgraph must induce a new edge in \(\mathbb {G}\)  that is in the set \(\bigcup _i (\lbrace v_i\rbrace \times [P_{v_i}])\)  where \([P_{v_i}]\subseteq G\)  is the set of vertices in the path \(P_{v_i}\) .

If \(\mathbb {G}^{\prime }\)  does not induce any new edges between elements of \(A\)  and the paths \(P_{v_i}\) , the \(P_{v_i}\)  will also witness the fact that \(A\)  is asteroidal in \(\mathbb {G}^{\prime }\) , a contradiction.
We start by analyzing the class of graphs labeled \(\mathrm {III}_\ell \)  because knowing the necessary sets for this class of graphs will be useful in finding the minimal necessary sets for all of the other classes.
Lemma 8.11 
The edges \(A_\ell :=\lbrace \lbrace 1,3\rbrace \rbrace \cup \lbrace \lbrace 2,k\rbrace :4\le k\le \ell \rbrace \) , or any translation of \(A_\ell \)  by an automorphism of \(\mathrm {III}_\ell \) , forms a \(\subseteq \) -minimal necessary set for \(\mathrm {III}_\ell \)  in \(L^2\) .

That this set is necessary is proven by Lekkekerker and Boland in [5]} (note that the word acyclic in the referenced lemma means that the graph has no irreducible cycles of length greater than 3, so every interval intersection graph is acyclic in this sense). It will then be enough to find an interval intersection graph \(\mathbb {G}\)  for each \(e\in A_\ell \)  such that \(\mathbb {G}\)  extends \(\mathrm {III}_\ell \) , \(e\)  is an edge of \(\mathbb {G}\) , and no other \(e^{\prime }\in A_\ell \)  is an edge in \(\mathbb {G}\) .
Let \(e=\lbrace i,j\rbrace \)  where \(i\in \lbrace 1,2\rbrace \)  and consider the graph \(\mathbb {G}\)  that is \(\mathrm {III}_\ell \)  with all of the edges \(\lbrace j,k\rbrace \)  for \(k\ne j\)  added. If \(e=\lbrace 1,3\rbrace \) , no new edges incident to 2 are added and if \(j\ne 3\)  then no elements of \(A_\ell \)  are added except \(e\) . We claim that \(\mathbb {G}\)  is an interval intersection graph.
Since \(j\)  is a neighbor of every element of \(\mathbb {G}\) , we may construct a collection of intervals that have an intersection graph isomorphic to the subgraph of \(\mathbb {G}\)  induced by \(G\setminus \lbrace j\rbrace \)  and then take \(j\)  to be the union of these intervals. The induced subgraph looks like
\(\hbox{\begin{tikzpicture} [circle dotted/.style={line width = 0.3mm, dash pattern= on .05mm off 1mm, line cap = round}]{enclosed/.style={draw, circle, inner sep=0pt, minimum size=.1cm, fill=black}}\end{tikzpicture}\node [enclosed, label=above:$(j+1)$] (1) at (0,0) {};\node [enclosed, label=above:$(j+2)$] (2) at (3*0.5,0) {};\node [enclosed, label=above:$\ell $] (3) at (6*0.5,0) {};\node [enclosed, label=above:$1$] (4) at (9*0.5,0) {};\node [enclosed, label=above:$2$] (5) at (12*0.5,0) {};\node [enclosed, label=above:$(j-1)$] (6) at (15*0.5,0) {};}(1) -- (2);[dashed] (2) -- (3);(3) -- (4);(4) -- (5);[dashed] (5) -- (6);\) 
\(which is the intersection graph of a collection of intervals that barely overlap at the endpoints.\) 
The definition of necessary sets for \(\mathbb {G}\)  in \(S\)  implies that any translation of a necessary set for \(\mathbb {G}\)  by an automorphism is a necessary set (in particular, composition with an automorphism of \(\mathbb {G}\)  is a permutation of the injective graph homomorphisms from \(\mathbb {G}\)  to any other graph).
Lemma 8.12 The 6 edges (the two dotted edges below and their images under permutation of the `arms') shown below form a \(\subseteq \) -minimal necessary set for \(\mathrm {I}\)  in \(L^2\) .
\(\hbox{\begin{tikzpicture} [circle dotted/.style={line width = 0.3mm, dash pattern= on .05mm off 1mm, line cap = round}]{enclosed/.style={draw, circle, inner sep=0pt, minimum size=.1cm, fill=black}}\end{tikzpicture}\node [enclosed] (1) at (0,0) {};\node [enclosed] (2) at (0,.75*0.5) {};\node [enclosed] (3) at (0,1.5*0.5) {};\node [enclosed] (4) at (-0.65*0.5,-0.375*0.5) {};\node [enclosed] (5) at (-1.3*0.5,-.75*0.5) {};\node [enclosed] (6) at (0.65*0.5,-0.375*0.5) {};\node [enclosed] (7) at (1.3*0.5,-.75*0.5) {};}(1) -- (2);(2) -- (3);(1) -- (4);(4) -- (5);(1) -- (6);(6) -- (7);[circle dotted] (1) edge[bend right = 60] (3);[circle dotted] (2) -- (4);\) 
\(\) 
For \(0\le n\le 3\) , we will call the vertices along the `arm' at the angle \(\pi /2+2n\pi /3\)  by \(a_{n1}\)  and \(a_{n2}\)  where \(a_{n1}\)  is the neighbor of the center vertex and \(a_{n2}\)  is the outermost vertex on the given arm. We will denote the center vertex by \(c\) . We then have that the set \(A=\lbrace a_{n2}:0\le n\le 2\rbrace \)  is asteroidal in \(\mathrm {I}\) . By Lemma REF , any intersection graph having \(\mathrm {I}\)  as a subgraph must add an edge incident to one of the elements of \(A\) , so we will start our search for necessary edges here.
Let \(\mathbb {G}\)  be an intersection graph and \(i:\mathrm {I}\rightarrow \mathbb {G}\)  an injective graph homomorphism (we will denote \(i(a_{kj})\)  by \(a^{\prime }_{kj}\) ). We may assume that \(a^{\prime }_{02}\)  has an edge that does not occur in \(\mathbb {G}\)  since any permutation of \(A\)  can be achieved by a graph automorphism of \(\mathrm {I}\) . If \(a^{\prime }_{02}\mathrel {E}^{\mathbb {G}}a^{\prime }_{12}\)  then the set of vertices \(\lbrace a^{\prime }_{12},a^{\prime }_{02},a^{\prime }_{01},c^{\prime },a^{\prime }_{11}\rbrace \)  can be taken to form a subgraph of \(\mathbb {G}\)  isomorphic to \(\mathrm {III}_5\)  with the nodes labeled in the order given. From the necessary sets found for \(\mathrm {III}_n\) , one of the edges \(e_1:=\lbrace a^{\prime }_{02},a^{\prime }_{11}\rbrace ,\lbrace a^{\prime }_{12},a^{\prime }_{01}\rbrace ,e_2:=\lbrace a^{\prime }_{02},c^{\prime }\rbrace \)  must also appear in \(\mathbb {G}\) . We note that the first two edges differ by an automorphism of \(\mathrm {I}\)  so we may treat only one of them explicitly (note that the proposed necessary set is stable under automorphism of \(\mathrm {I}\) ). If the edge \(e_1\)  is in \(\mathbb {G}\) , then the set \(\lbrace a^{\prime }_{02},a^{\prime }_{11},c^{\prime },a^{\prime }_{01}\rbrace \)  forms a subgraph isomorphic to \(\mathrm {III}_4\) , which means that either \(e_2\)  or \(e_3=\lbrace a^{\prime }_{11},a^{\prime }_{01}\rbrace \)  appear in \(\mathbb {G}\) .
Thus the statement that either \(e_1\)  or \(e_2\)  appears in \(\mathbb {G}\)  can be reduced to the statement that either \(e_2\)  or \(e_3\)  (the dotted edges) appear in \(\mathbb {G}\) . To show the desired result it will be enough to check that there are two intersection graphs having \(\mathrm {I}\)  as a subgraph with the edge \(e_2\)  but not \(e_3\)  and vice versa. To do this, we note that the following two graphs are interval intersection graphs in \(\mathbb {R}\)  (with labels indicating a possible set of intervals with the given intersection graph):
\(\hbox{\begin{tikzpicture} [circle dotted/.style={line width = 0.3mm, dash pattern= on .05mm off 1mm, line cap = round}, scale=2]{enclosed/.style={draw, circle, inner sep=0pt, minimum size=.1cm, fill=black}}\end{tikzpicture}\node [enclosed, label={[label distance=-1.25mm, xshift=-.45mm, yshift=-.5mm]176:\tiny $(4{,}\,9)$}] (1) at (0,0) {};\node [enclosed, label={[label distance=-0.75mm]left:\tiny $(6{,}\,7)$}] (2) at (0,.75*0.5) {};\node [enclosed, label={[label distance=-0.75mm]left:\tiny $(6{,}\,7)$}] (3) at (0,1.5*0.5) {};\node [enclosed, label={[label distance=-0.75mm, yshift=.5mm]left:\tiny $(2{,}\,5)$}] (4) at (-0.65*0.5,-0.375*0.5) {};\node [enclosed, label={[label distance=-0.75mm]left:\tiny $(1{,}\,3)$}] (5) at (-1.3*0.5,-.75*0.5) {};\node [enclosed, label={[label distance=-0.75mm, yshift=.5mm]right:\tiny $(8{,}\,11)$}] (6) at (0.65*0.5,-0.375*0.5) {};\node [enclosed, label={[label distance=-0.75mm]right:\tiny $(10{,}\,12)$}] (7) at (1.3*0.5,-.75*0.5) {};}(1) -- (2);(2) -- (3);(1) -- (4);(4) -- (5);(1) -- (6);(6) -- (7);(1) edge[bend right = 60] (3);\) 
         
\(The other edges belong in the \) 
\(-minimal necessary set by symmetric arguments.\)
Lemma 8.13 The dotted edges in
\(\hbox{\begin{tikzpicture} [circle dotted/.style={line width = 0.3mm, dash pattern= on .05mm off 1mm, line cap = round}]{enclosed/.style={draw, circle, inner sep=0pt, minimum size=.1cm, fill=black}}\end{tikzpicture}\node [enclosed, label={[label distance=0mm,xshift=-1mm,yshift=-.2mm]290:$v_4$}] (1) at (0,0) {};\node [enclosed, label=below:$v_3$] (2) at (-0.75*1,0) {};\node [enclosed, label=below:$v_2$] (3) at (-1.5*1,0) {};\node [enclosed, label=right:$v_1$] (4) at (0,0.75*1) {};\node [enclosed, label=below:$v_5$] (5) at (0.75*1,0) {};\node [enclosed, label=below:$v_6$] (6) at (1.5*1,0) {};\node [enclosed, label=right:$v_7$] (7) at (0,-.75*1) {};}(1) -- (2);(2) -- (3);(1) -- (5);(5) -- (6);(4) -- (1);(4) -- (2);(4) -- (3);(4) -- (5);(4) -- (6);(1) -- (7);\) 
[circle dotted] (4) edge[bend right = 110, looseness = 4] (7);
[circle dotted] (1) edge[bend right = 60] (3);
[circle dotted] (2) edge[bend left = 30] (5);
[circle dotted] (1) edge[bend left = 60] (6);
\(form a necessary set of minimal cardinality for \) 
II\( in \) L2\(.\)
As before, we recognize that the set \(A=\lbrace v_2,v_6,v_7\rbrace \)  is asteroidal in \(\mathrm {II}\)  and start our analysis with edges that are adjacent to elements of \(A\) . We start by noticing that the edges \(\lbrace v_2,v_4\rbrace ,\lbrace v_4,v_6\rbrace ,\)  and \(\lbrace v_1,v_7\rbrace \)  must be in any necessary set as \(\mathrm {II}\)  becomes an interval intersection graph in \(\mathbb {R}\)  when any one of these edges is added. For example, the collections of intervals given by:
\(\hbox{\begin{tikzpicture} [circle dotted/.style={line width = 0.3mm, dash pattern= on .05mm off 1mm, line cap = round}, scale=1.5]{enclosed/.style={draw, circle, inner sep=0pt, minimum size=.1cm, fill=black}}\end{tikzpicture}\node [enclosed, label={[label distance=0mm,xshift=-1mm,yshift=-.2mm]290:\tiny $(2{,}\,8)$}] (1) at (0,0) {};\node [enclosed, label=below:\tiny $(4{,}\,6)$] (2) at (-0.75*1,0) {};\node [enclosed, label=below:\tiny $(4{,}\,6)$] (3) at (-1.5*1,0) {};\node [enclosed, label={[yshift=-.5mm]above:\tiny $(5{,}\,10)$}] (4) at (0,0.75*1) {};\node [enclosed, label=below:\tiny $(7{,}\,10)$] (5) at (0.75*1,0) {};\node [enclosed, label=below:\tiny $(9{,}\,10)$] (6) at (1.5*1,0) {};\node [enclosed, label=right:\tiny $(1{,}\,3)$] (7) at (0,-.75*1) {};}(1) -- (2);(2) -- (3);(1) -- (5);(5) -- (6);(4) -- (1);(4) -- (2);(4) -- (3);(4) -- (5);(4) -- (6);(1) -- (7);\) 
(1) edge[bend right = 60] (3);
\((note that the case of the edge \) 
v4,v6}\( being added is symmetric to the case of \) {v2,v4}\().\) It remains to find any intersection graphs \(\mathbb {G}\)  with \(\mathrm {II}\)  as a subgraph and which fail to contain any of the edges so far found. The remaining choices for adding an edge incident to an element of \(A\)  are (up to symmetry) \(e_1=\lbrace v_2,v_7\rbrace \) , \(e_2=\lbrace v_2,v_5\rbrace \) , and \(e_3=\lbrace v_2,v_6\rbrace \) . Note that the edge \(\lbrace v_3,v_7\rbrace \)  (or the symmetric \(\lbrace v_5,v_7\rbrace \) ) can be added to \(\mathrm {II}\)  without changing the fact that \(A\)  is asteroidal. Thus another edge incident to an element of \(A\)  must be still be added to produce an intersection graph, allowing us to ignore the edge \(\lbrace v_3,v_7\rbrace \) .
Suppose first that an intersection graph \(\mathbb {G}\)  extends \(\mathrm {II}\)  and has the edge \(e_1\) . Then the vertices \(\lbrace v_1,v_4,v_7,v_2\rbrace \)  form a cycle of length 4, and so either the edge \(\lbrace v_1,v_7\rbrace \)  or the edge \(\lbrace v_2,v_4\rbrace \)  belong to \(\mathbb {G}\) . Both of these edges are already accounted for, so all intersection graphs with the edge \(\lbrace v_2,v_7\rbrace \)  are already accounted for.
Now suppose that \(\mathbb {G}\)  is an intersection graph containing the edge \(\lbrace v_2,v_5\rbrace \) . But then \(\mathbb {G}\)  contains the 4-cycle \(v_2,v_3,v_4,v_5\)  and so must contain either the edge \(\lbrace v_3,v_5\rbrace \)  or the edge \(\lbrace v_2,v_4\rbrace \) . The latter is already covered, so adding \(\lbrace v_3,v_5\rbrace \)  to the necessary set will cover all intersection graphs with the edge \(\lbrace v_2,v_5\rbrace \)  (and, by a symmetric argument, all intersection graphs with the edge \(\lbrace v_3,v_6\rbrace \) ). It remains to check that the edge \(\lbrace v_3,v_5\rbrace \)  occurs in an intersection graph not having any of the other edges in the proposed necessary set. The graph \(\mathrm {II}\)  with the edges \(\lbrace v_2,v_5\rbrace \)  and \(\lbrace v_3,v_5\rbrace \)  added accomplishes this goal. In particular, the collection of real intervals
\(\hbox{\begin{tikzpicture} [circle dotted/.style={line width = 0.3mm, dash pattern= on .05mm off 1mm, line cap = round}, scale=1.5]{enclosed/.style={draw, circle, inner sep=0pt, minimum size=.1cm, fill=black}}\end{tikzpicture}\node [enclosed, label={[label distance=0mm,xshift=-1mm,yshift=-.2mm]290:\tiny $(2{,}\,7)$}] (1) at (0,0) {};\node [enclosed, label=below:\tiny $(6{,}\,9)$] (2) at (-0.75*1,0) {};\node [enclosed, label={[xshift=.5mm]below:\tiny $(8{,}\,10)$}] (3) at (-1.5*1,0) {};\node [enclosed, label={[yshift=-.5mm]above:\tiny $(4{,}\,13)$}] (4) at (0,0.75*1) {};\node [enclosed, label=below:\tiny $(5{,}\,12)$] (5) at (0.75*1,0) {};\node [enclosed, label=below:\tiny $(11{,}\,14)$] (6) at (1.5*1,0) {};\node [enclosed, label=right:\tiny $(1{,}\,3)$] (7) at (0,-.75*1) {};}(1) -- (2);(2) -- (3);(1) -- (5);(5) -- (6);(4) -- (1);(4) -- (2);(4) -- (3);(4) -- (5);(4) -- (6);(1) -- (7);\) 
(3) edge[bend left = 60] (5);
(2) edge[bend left = 30] (5);
\(has this intersection graph.\) 
Finally suppose that \(\mathbb {G}\)  is an intersection graph extending \(\mathrm {II}\)  and containing the edge \(\lbrace v_2,v_6\rbrace \) . Then the vertices \(\lbrace v_2,v_6,v_5,v_4,v_3\rbrace \)  form a subgraph isomorphic to \(\mathrm {III}_5\)  labels occurring in the given order, so one of the edges \(\lbrace v_2,v_5\rbrace \) , \(\lbrace v_6,v_4\rbrace \) , or \(\lbrace v_6,v_3\rbrace \)  must also be in \(\mathbb {G}\) . Any graph containing the first two of these edges has already been explicitly covered, and any intersection graph with \(\lbrace v_3,v_6\rbrace \)  is covered by an argument symmetric to the argument for graphs containing \(\lbrace v_2,v_5\rbrace \) . Thus every such \(\mathbb {G}\)  already has an edge in our proposed necessary set.
This necessary set is of minimal cardinality because all necessary sets must contain all but one of the proposed edges
Lemma 8.14 The dotted edges in
\(\hbox{\begin{tikzpicture}[circle dotted/.style={dash pattern= on .05mm off 1mm, line cap = round, line width = 0.3mm}]{enclosed/.style={draw, circle, inner sep=0pt, minimum size=.1cm, fill=black}}\end{tikzpicture}\node [enclosed, label=left:$\beta $] (bl) at (-3*0.75,0) {};\node [enclosed, label=right:$\delta $] (br) at (3*0.75,0) {};\node [enclosed, label={[label distance=-2mm]135:$\gamma $}] (u) at (0,1*0.75) {};\node [enclosed, label=above:$\alpha $] (uu) at (0,2*0.75) {};\node [enclosed, label=below:$1$] (1) at (-2*0.75,0) {};\node [enclosed, label=below:$2$] (2) at (-1*0.75,0) {};\node [enclosed, label=below:$3$] (3) at (0,0) {};\node [enclosed, label=below:$m$] (n) at (2*0.75,0) {};}\) 
in 1,2,3,n
(u) – ();
(bl) – (1);
(n) – (br);
(uu) – (u);
[evaluate=as using +1] in 1,2
() – ();
[dashed] (3) – (n);
[circle dotted] (1) edge[bend right = 50] (n);
[circle dotted] (u) – (bl);
[circle dotted] (u) – (br);
[circle dotted] (uu) – (1);
[circle dotted] (uu) – (2);
[circle dotted] (uu) – (n);
[circle dotted] (uu) edge[bend left = 20] (3);
\(form a necessary set of minimal cardinality for \) 
IVm\( in \) L2\(.\)
As before, we start by identifying the set \(A=\lbrace \alpha ,\beta ,\delta \rbrace \)  as being asteroidal in \(\mathrm {IV}_m\) .
The edges \(\lbrace \beta ,\gamma \rbrace \) , \(\lbrace \gamma ,\delta \rbrace \) , and \(\lbrace \alpha ,i\rbrace \)  for each \(1\le i\le m\)  must be in every necessary set for \(\mathrm {IV}_m\)  as \(\mathrm {IV}_m\)  becomes an intersection graph as soon as any one of the above edges is added. Up to symmetry, representative examples of these intersection graphs are:
\(\hbox{\begin{tikzpicture}[circle dotted/.style={dash pattern= on .05mm off 1mm, line cap = round, line width = 0.3mm}]{enclosed/.style={draw, circle, inner sep=0pt, minimum size=.1cm, fill=black}}\end{tikzpicture}\node [enclosed, label=left:\tiny {$(3,4)$}] (bl) at (-1.5*0.75,0) {};\node [enclosed, label=right:\tiny {$(7,8)$}] (br) at (1.5*0.75,0) {};\node [enclosed, label={[label distance=-2mm, xshift=.3mm]45:\tiny {$(1,6)$}}] (u) at (0,1*0.75) {};\node [enclosed, label=above:\tiny {$(1,2)$}] (uu) at (0,2*0.75) {};\node [enclosed, label=below:\tiny {$(3,6)$}] (1) at (-.5*0.75,0) {};\node [enclosed, label=below:\tiny {$(5,8)$}] (2) at (.5*0.75,0) {};}\) 
in 1,2
(u) – ();
(bl) – (1);
(2) – (br);
(uu) – (u);
[evaluate=as using +1] in 1
() – ();
(u) edge (bl);
   
\(It remains to show that any intersection graph extending \) 
IVm\( and not containing any of the aforementioned edges must contain the edge \) {1,m}\( (and that such intersection graphs do exist).\) If \(\mathbb {G}\)  extends \(\mathrm {IV}_m\)  and \(\lbrace \alpha ,\beta \rbrace \)  is in \(\mathbb {G}\)  then \(\lbrace \alpha ,\beta ,1,\gamma \rbrace \)  forms a 4-cycle and so either \(\lbrace \alpha ,1\rbrace \)  is in \(\mathbb {G}\)  or \(\lbrace \beta ,\gamma \rbrace \)  is in \(\mathbb {G}\) . However, both of these options are already covered, so \(\lbrace \alpha ,\beta \rbrace \)  cannot be in a \(\subseteq \) -minimal necessary set. A symmetric argument gets the same result for the edge \(\lbrace \alpha ,\delta \rbrace \) .
Now, in order to avoid \(A\)  being asteroidal, an intersection graph extending \(\mathrm {IV}_m\)  and having none of the previously mentioned edges must have one of the edges \(\lbrace \beta ,\delta \rbrace \) , \(\lbrace \beta ,m\rbrace \) , or \(\lbrace \delta ,1\rbrace \) . If \(\lbrace \beta ,\delta \rbrace \)  is an edge of \(\mathbb {G}\)  then the vertices \(\lbrace \beta ,\delta ,m,\gamma ,1\rbrace \)  form a 5-cycle so one of the edges \(\lbrace 1,m\rbrace ,\lbrace \gamma ,\delta \rbrace ,\)  or \(\lbrace \gamma ,\beta \rbrace \)  must appear in \(\mathbb {G}\) , but we have already ruled out the latter two, so \(\lbrace 1,m\rbrace \)  must be in \(\mathbb {G}\) .
If \(\lbrace \beta ,m\rbrace \)  is in \(\mathbb {G}\)  then the vertices \(\lbrace \beta ,m,\gamma ,1\rbrace \)  form a 4-cycle and so either \(\lbrace \beta ,\gamma \rbrace \)  is in \(\mathbb {G}\)  or \(\lbrace 1,m\rbrace \)  is in \(\mathbb {G}\) . We already know that graphs with \(\lbrace \beta ,\gamma \rbrace \)  are covered, so we must have that \(\lbrace 1,m\rbrace \)  is in \(\mathbb {G}\) . A symmetric argument for \(\lbrace \delta ,1\rbrace \)  also shows that \(\lbrace 1,m\rbrace \)  must be an edge in \(\mathbb {G}\) .
The result now follows from the fact that the extension of \(\mathrm {IV}_m\)  with the vertices \(\lbrace \beta ,\delta \rbrace \cup \lbrace 1,\dots ,m\rbrace \)  inducing a complete subgraph and otherwise having only the edges from \(\mathrm {IV}_m\)  is an intersection graph. An example of intervals producing such a graph could be given by setting all of the vertices labelled \(1,\dots ,m\)  to the same non-empty interval and also identify the vertices labelled \(\beta \)  and \(\delta \) . These identifications lead to a quotient graph of the proposed graph that is isomorphic to a graph that is a single irreducible path, which was shown to be an intersection graph in Lemma REF .
Lemma 8.15 
The dotted edges in
\(\hbox{\begin{tikzpicture}[circle dotted/.style={line width = 0.3mm, dash pattern= on .05mm off 1mm, line cap = round}, scale=1.5]{enclosed/.style={draw, circle, inner sep=0pt, minimum size=.1cm, fill=black}}\end{tikzpicture}}\node [enclosed, label=above left:\) 
\(] (o1) at ({cos(deg(2*pi/3))*},{sin(deg(2*pi/3))*}) {};\node [enclosed, label=above right:\)\(] (o2) at ({cos(deg(pi/3))*},{sin(deg(pi/3))*}) {};\)enclosed, label=left:\(\alpha \) ] (u1) at (cos(deg(5*pi/6))*,sin(deg(5*pi/6))*) ;
enclosed, label=[yshift=-1.3mm]above:\(\beta \) ] (u2) at (cos(deg(pi/2))*,sin(deg(pi/2))*) ;
enclosed, label=right:\(\gamma \) ] (u3) at (cos(deg(/2))*, sin(deg(/2))*) ;
/in 1/1,2/2,3/3
enclosed, label=below:] () at ((-1)/3-,0) ;
enclosed, label=below:\(n\) ] (4) at (,0) ;
in o1,o2
in 1,2,3,4
() – ();

(o1) – (o2);
[evaluate=as using +1] in 1,2
() – ();
[dashed] (3) – (4);
(1) – (u1);
(o1) – (u1);
(o1) – (u2);
(o2) – (u2);
(o2) – (u3);
(4) – (u3);
in 1,2,3
[circle dotted] (u2) edge[bend left = 10] ();
[circle dotted] (u2) edge[bend right = 10] (4);
[circle dotted] (o1) edge[bend left = 80, looseness = 2.4] (u3);
[circle dotted] (o2) edge[bend right = 80, looseness = 2.4] (u1);
\(form the unique necessary set of minimal cardinality for \) 
Vn\( in \) L2\(.\)
We first note that the set \(A=\lbrace \alpha ,\beta ,\gamma \rbrace \)  is asteroidal in \(\mathrm {V}_n\) . We also note that if any one of the edges \(\lbrace \gamma ,\delta \rbrace \) , \(\lbrace \alpha ,\epsilon \rbrace \) , or \(\lbrace \beta ,i\rbrace \)  for some \(1\le i\le n\)  are added to \(\mathrm {V}_n\) , then the resulting graph is an intersection graph, and so every necessary set for \(\mathrm {V}_n\)  contains the edges \(\lbrace \alpha ,\epsilon \rbrace \) , \(\lbrace \gamma ,\delta \rbrace \) , and \(\lbrace \beta ,i\rbrace \)  for each \(1\le i\le n\) . Representative examples of such graphs are (up to symmetry):
\(\hbox{\begin{tikzpicture}[circle dotted/.style={line width = 0.3mm, dash pattern= on .05mm off 1mm, line cap = round}, scale=1.25]{enclosed/.style={draw, circle, inner sep=0pt, minimum size=.1cm, fill=black}}\end{tikzpicture}}\node [enclosed, label={[label distance=-1mm]above left:\tiny {(1,8)}}] (o1) at ({cos(deg(2*pi/3))*},{sin(deg(2*pi/3))*}) {};\node [enclosed, label={[label distance=-1mm]above right:\tiny {(1,9)}}] (o2) at ({cos(deg(pi/3))*},{sin(deg(pi/3))*}) {};\) 
enclosed, label=left:\({(3,7)}\) ] (u1) at (cos(deg(5*pi/6))*,sin(deg(5*pi/6))*) ;
enclosed, label=[label distance=-.5mm, yshift=-1.3mm]above left:\({(1,2)}\) ] (u2) at (cos(deg(pi/2))*,sin(deg(pi/2))*) ;
enclosed, label=right:\({(10,11)}\) ] (u3) at (cos(deg(pi/6))*, sin(deg(pi/6))*) ;
enclosed, label=below:\({(3,6)}\) ] (1) at (-,0) ;
enclosed, label=below:\({(5,9)}\) ] (2) at (0,0) ;
enclosed, label=below:\({(7,11)}\) ] (3) at (,0) ;
in o1,o2
in 1,2,3
() – ();

(o1) – (o2);
[evaluate=as using +1] in 1,2
() – ();
(1) – (u1);
(o1) – (u1);
(o1) – (u2);
(o2) – (u2);
(o2) – (u3);
(3) – (u3);
(o2) edge[bend right = 80, looseness = 2] (u1);
   [circle dotted/.style=line width = 0.3mm, dash pattern= on .05mm off 1mm, line cap = round, scale=1.25]
enclosed/.style=draw, circle, inner sep=0pt, minimum size=.1cm, fill=black


enclosed, label=[label distance=-1mm]above left:\({(1,10)}\)] (o1) at (cos(deg(2*pi/3))*1,sin(deg(2*pi/3))*1) ;
enclosed, label=[label distance=-1mm]above right:\({(3,12)}\)] (o2) at (cos(deg(pi/3))*1,sin(deg(pi/3))*1) ;
enclosed, label=left:\({(1,2)}\) ] (u1) at (cos(deg(5*pi/6))*1.5*1,sin(deg(5*pi/6))*1.5*1) ;
enclosed, label=[yshift=-.5mm]above:\({(6,7)}\) ] (u2) at (cos(deg(pi/2))*1.5*1,sin(deg(pi/2))*1.5*1) ;
enclosed, label=right:\({(11,12)}\) ] (u3) at (cos(deg(pi/6))*1.5*1, sin(deg(pi/6))*1.5*1) ;
enclosed, label=below:\({(3,5)}\) ] (1) at (-1,0) ;
enclosed, label=below:\({(4,9)}\) ] (2) at (0,0) ;
enclosed, label=below:\({(8,10)}\) ] (3) at (1,0) ;
in o1,o2
in 1,2,3
() – ();

(o1) – (o2);
[evaluate=as using +1] in 1,2
() – ();
(1) – (u1);
(o1) – (u1);
(o1) – (u2);
(o2) – (u2);
(o2) – (u3);
(3) – (u3);
(u2) – (2);

\(\) 
Suppose that \(\mathbb {G}\)  is an intersection graph extending \(\mathrm {V}_n\)  and containing the edge \(\lbrace \alpha ,\beta \rbrace \) . Then the vertices \(\lbrace \alpha ,\beta ,\epsilon ,1\rbrace \)  form a 4-cycle, and so one of the edges \(\lbrace \beta ,1\rbrace \)  or \(\lbrace \alpha ,\epsilon \rbrace \)  must be contained in \(\mathbb {G}\)  as well. However, we already know that both of these edges must be in the necessary set.
If \(\mathbb {G}\)  contains the edge \(\lbrace \alpha ,\gamma \rbrace \)  then the vertices \(\lbrace \alpha ,\gamma ,\epsilon ,\delta \rbrace \)  form a 4-cycle, so one of the edges \(\lbrace \alpha ,\epsilon \rbrace \)  or \(\lbrace \gamma ,\delta \rbrace \)  must be in \(\mathbb {G}\) . Again, we already know that both of these edges must be in every necessary set.
At this point, no other edges can prevent \(A\)  from being asteroidal in an extension, so we have covered all the required cases.
Now that we have computed the minimal necessary sets for each of the minimal graphs that cannot appear as induced subgraphs of interval intersection graphs, we can state a theorem for \(\mathrm {SOP}\)  that is an analogue of Theorem REF .
Theorem 8.16 Let \( be a regular ultrafilter on the infinite cardinal \)\(. The following are equivalent:\begin{enumerate}\item  is good.\item  saturates some theory with \mathrm {SOP}.\item If (\mathbb {G}_\alpha )_{\alpha <\lambda } is a sequence of finite graphs such that \mathrm {I},\mathrm {II},\mathrm {III}_\ell ,\mathrm {IV}_m,\mathrm {V}_n\nleq \mathbb {G}_\alpha  for each \alpha  and \ell \ge 4,m\ge 2, and n\ge 1, then every complete \mathbb {H}\subseteq \mathbb {G}_\alpha ^:\mathbb {G} with |\mathbb {H}|\le \lambda  has some internal complete subgraph of \mathbb {G} containing it.\item Every graph-like function f:\mathcal {P}_\omega (\lambda )\rightarrow  that satisfies the conditions given by specializing the subset relation~(\ref {necdisteqn}) to the necessary sets found for \mathbb {H}=\mathrm {I},\mathrm {II},\mathrm {III}_\ell ,\mathrm {IV}_m,\mathrm {V}_n in Lemmas~\ref {IIInecsets}--\ref {Vnecsets} has a multiplicative refinement.\end{enumerate}\)
\((1)\)\(\iff \)\((2)\) : Follows from e.g. [8]}.
\((2)\)\(\iff \)\((3)\) : A special case of Theorem REF .
\((2)\)\(\iff \)\((4)\) : Follows from Theorem REF  and Lemmas REF –REF .

\(\mathrm {SOP}_n\)  for \(n>2\)
In this section, our goal is to show that graph-like distributions corresponding to types whose realizations would fill a cut in an ultrapower of an infinite linear order (that is, types that characteristically appear in theories with \(\mathrm {SOP}\) ) also appear as graph-like distributions for types that appear in theories with \(\mathrm {SOP}_3\) , regardless of whether they also have \(\mathrm {SOP}\) . In essence this will show that distributions in theories with \(\mathrm {SOP}_n\)  for \(n\ge 3\)  are not only complicated enough to guarantee that the theory is Keisler maximal but are complicated enough to mimic the distributions of theories where models contain infinite linear orders. This argument is a close cousin to the argument made in [8]} that theories with \(\mathrm {SOP}_3\)  are Keisler maximal, but is more elementary.
Theorem 8.17 
Suppose that \( is a regular ultrafilter on the infinite cardinal \)\(, \) L=(L,<)\( is a linear order, \) (x;y,z)\( is the formula \) y<x<z\(, and \) p(x)={(x;a,b):<}\( is a type of \) L. Then, for every distribution \(f\)  of \(p(\bar{x})\)  and graph-like distribution \(\hat{f}\)  extending \(f\)  and every complete first-order theory \(T\)  with \(\mathrm {SOP}_3\) , there is a model \(\mathbb {M}\vDash T\)  and a graph-like type \(q(\bar{y})\)  of \(\mathbb {M}^ with a distribution \) f'\( satisfying \) f=f'\( (up to bijection between \) p(x)\( and \) q(y)\().\)
Fix representations of \(a_\beta ,b_\beta \)  and a distribution \(f\)  of \(p(\bar{x})\)  given these representations. Since \(p\)  is graph-like under any choice of representations in \(L\) , there is a graph-like distribution \(\hat{f}\)  extending \(f\) . Let the distribution graph sequence of \(\hat{f}\)  be \((\mathbb {G}_\alpha )_{\alpha <\lambda }\)  where each \(\mathbb {G}_\alpha \)  is a finite intersection graph (see Lemma REF ). Let \(I(\lambda )\)  be the collection of open intervals \(I\)  in \(\lambda \)  with the property that \(\min (I)\)  is a successor ordinal. For each \(\alpha <\lambda \)  let \(i_\alpha :\lambda \rightarrow I(\lambda )\)  be a function such that \(i_\alpha \text{\,}\mathord {\upharpoonright }\text{\,}_{\mathbb {G}_\alpha }\)  is a bijection and \(i_\alpha (\beta )\)  and \(i_\alpha (\gamma )\)  intersect if and only if \(\beta \)  and \(\gamma \)  are neighbors in \(\mathbb {G}_\alpha \) . Furthermore, we require that no two intervals in the image of \(i_\alpha \)  have endpoints in common. Let the functions \(\ell ,r:I(\lambda )\rightarrow \lambda \)  be the functions defined by
\(\ell (I)=\inf (I)\;\text{ and }\;r(I)=\sup (I).\) 
The function \(\ell (I)\)  is well-defined by the requirement that \(\min (I)\)  be a successor ordinal.
By [8]}, \(T\)  has \(\mathrm {SOP}_3\)  if and only if there is a model \(\mathbb {M}\vDash T\)  containing an indiscernible sequence \((\bar{a}_i)_{i\in \omega }\)  and formulas \(\theta (\bar{x},\bar{y})\)  and \(\eta (\bar{x},\bar{y})\)  such that

the set \(\lbrace \theta (\bar{x},\bar{y}),\eta (\bar{x},\bar{y})\rbrace \)  is contradictory,

for some sequence \((b_j)_{j\in \omega }\)  we have
\(i\le j\Rightarrow \theta (\bar{b}_j,\bar{a}_i)\;\,\text{ and }\;\,i>j\Rightarrow \eta (\bar{b}_j,\bar{a}_i)\) 

for \(i<j\) , the set \(\lbrace \theta (\bar{x},\bar{a}_j),\eta (\bar{x},\bar{a}_i)\rbrace \)  is contradictory.

Using compactness, we may extend the sequences \(\bar{a}\)  and \(\bar{b}\)  to sequences indexed by \(\lambda \) . Let \((\bar{a}_i)_{i\in \lambda }\) , \((\bar{b}_j)_{j\in \lambda }\) , \(\theta (\bar{x},\bar{y})\) , and \(\eta (\bar{x},\bar{y})\)  be as above. We then define
\(\psi (\bar{x};\bar{y},\bar{z})\equiv \theta (\bar{x},\bar{y})\wedge \eta (\bar{x},\bar{z}).\) 
Furthermore, define \((\bar{c}_\beta )_{\beta \in \lambda }\)  and \((\bar{d}_\beta )_{\beta \in \lambda }\)  in \(\mathbb {M}^ by the representations\)\(\bar{c}_\beta [\alpha ]=\bar{a}_{\ell (i_{\alpha }(\beta ))}\;\text{ and }\;\bar{d}_\beta [\alpha ]=\bar{a}_{r(i_{\alpha }(\beta ))}.\)\(We claim that the set of formula\)\(q(\bar{x})=\lbrace \psi (\bar{x};\bar{c}_\beta ,\bar{d}_\beta ):\beta <\lambda \rbrace \)\(is a graph-like type with distribution \) f\(.\) In order to check that \(q(\bar{x})\)  is graph-like, suppose that \(\Delta \in \mathcal {P}_\omega (\lambda )\)  is such that \(|\Delta |\ge 2\) . We wish to show that
\(L_q(\Delta )=\bigcap _{\Phi \in [\Delta ]^2}L_q(\Phi ),\) 
where \(L_q\)  is the Łoś map for \(q(\bar{x})\) . In order to do this, we will instead show that
\(L_q(\Delta )=\Big \lbrace \alpha \in \lambda :\bigcap i_\alpha [\Delta ]\ne \emptyset \Big \rbrace ,\) 
which will be enough because of the fact that an intersection of open intervals is non-empty if and only if the intersection of every pair of intervals in the collection is non-empty. Suppose that \(j\in \bigcap i_\alpha [\Delta ]\) . Then we have that \(\mathbb {M}\vDash \psi (\bar{b}_j;\bar{c}_\beta [\alpha ],\bar{d}_\beta [\alpha ])\)  for each \(\beta \in \Delta \)  because \(\ell (i_\alpha (\beta ))<j<r(i_\alpha (\beta ))\)  by the definition of \(j\) . Now suppose that \(\bigcap i_\alpha [\Delta ]=\emptyset \) . Then there is some distinct pair \(\beta ,\gamma \in \Delta \)  such that \(r(i_\alpha (\beta ))\le \ell (i_\alpha (\gamma ))\) . Furthermore, because the intervals in the image of \(i_\alpha \)  cannot repeat endpoints, this inequality is strict. In particular, this means that the formula
\(\psi (\bar{x};\bar{c}_\beta [\alpha ],\bar{d}_\beta [\alpha ])\wedge \psi (\bar{x};\bar{c}_\gamma [\alpha ],\bar{d}_\gamma [\alpha ])\) 
cannot be satisfied in \(\mathbb {M}\) .
We check that \(\hat{f}\)  is a distribution of the type \(q(\bar{x})\)  with the given representations. By the fact that \(q(\bar{x})\)  and \(\hat{f}\)  are graph-like, it will be enough to check that \({\hat{f}(\Delta )\subseteq L(\Delta )}\)  for all \(\Delta \in \mathcal {P}_\omega (\lambda )\)  with \({|\Delta |\le 2}\) . However, this follows immediately from Equation (REF ) and the fact that \(\hat{f}\)  is a distribution for \(p(\bar{x})\) .
Corollary 8.18 Theorem REF  is true whenever \(T\)  is replaced with a theory with \(\mathrm {SOP}_n\)  for \(n>3\) .

By [8]}, \(\mathrm {SOP}_n\Rightarrow \mathrm {SOP}_3\)  whenever \(n\ge 3\) .
Given the difficulty in proving that theories with \(\mathrm {SOP}_2\)  are maximal in Keisler's order, we believe that the above theorem is not true for \(T\)  with \(\mathrm {SOP}_2\) . We note that if this conjecture is true, then \(\mathrm {SOP}_3\)  and \(\mathrm {SOP}_2\)  must be different on the level of theories as has been previously conjectured by Shelah.
Acknowledgements
Much thanks goes to Ágnes Szendrei for boundless advice given throughout the writing process and for suggesting looking at distributions related to \(\mathrm {SOP}_n\)  for \(n>2\) . This material is based upon work supported by the National Science Foundation grant no. DMS1500254.
