Subgraphs of random graphs

Abstract:

Let $\Delta \subseteq {[\omega ]^2}$ be an undirected graph on $\omega$, and let $u \in [0, 1]$. Following P. Erdös and A. Hajnal, we write $(\omega , 2, u) \Rightarrow \Delta$ to mean: whenever ${E_1} \subseteq [0, 1]$ is a measurable set of Lebesgue measure at least $u$ for every $I \in {[\omega ]^2}$, then there is some $t \in [0, 1]$ such that $\Delta$ appears in the graph ${\Gamma _t} = \{ I: t \in {E_I}\}$ in the sense that there is a strictly increasing function $f: \omega \to \omega$ such that $\{ f(i), f(j)\} \in {\Gamma _t}$ whenever $\{ i, j\} \in \Delta$. We give an algorithm for determining when $(\omega , 2, u) \Rightarrow \Delta$ for finite $\Delta$, and we show that for infinite $\Delta , (\omega , 2, u) \Rightarrow \Delta$ if there is a $\upsilon < u$ such that $(\omega , 2, \upsilon ) \Rightarrow {\Delta ^\prime }$ for every finite $\Delta ’ \subseteq \Delta$. Our results depend on a new condition, expressed in terms of measures on $\beta \omega$, sufficient to imply that $\Delta$ appears in $\Gamma$ (Theorem 2F), and enable us to identify the extreme points of some convex sets of measures (Theorem 5H).