Subgraphs of random graphs
HTML articles powered by AMS MathViewer
- by D. H. Fremlin and M. Talagrand PDF
- Trans. Amer. Math. Soc. 291 (1985), 551-582 Request permission
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).Additional Information
- © Copyright 1985 American Mathematical Society
- 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