Subgraphs of random graphs

Authors:
D. H. Fremlin and M. Talagrand

Journal:
Trans. Amer. Math. Soc. **291** (1985), 551-582

MSC:
Primary 60C05; Secondary 05C80

DOI:
https://doi.org/10.1090/S0002-9947-1985-0800252-6

MathSciNet review:
800252

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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).

Retrieve articles in *Transactions of the American Mathematical Society*
with MSC:
60C05,
05C80

Retrieve articles in all journals with MSC: 60C05, 05C80

Additional Information

Keywords:
Random graphs,
<!– MATH $\beta \omega$ –> <IMG WIDTH="31" HEIGHT="39" ALIGN="MIDDLE" BORDER="0" SRC="images/img1.gif" ALT="$\beta \omega$">,
extreme points

Article copyright:
© Copyright 1985
American Mathematical Society