Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



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

References [Enhancements On Off] (What's this?)

  • P. Erdős and A. Hajnal, Some remarks on set theory. IX. Combinatorial problems in measure theory and set theory, Michigan Math. J. 11 (1964), 107–127. MR 171713

Similar Articles

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