Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
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^{\prime} \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?)


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

DOI: http://dx.doi.org/10.1090/S0002-9947-1985-0800252-6
PII: S 0002-9947(1985)0800252-6
Keywords: Random graphs, $ \beta\omega$, extreme points
Article copyright: © Copyright 1985 American Mathematical Society