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: Let be an undirected graph on , and let . Following P. Erdös and A. Hajnal, we write to mean: whenever is a measurable set of Lebesgue measure at least for every , then there is some such that appears in the graph in the sense that there is a strictly increasing function such that whenever . We give an algorithm for determining when for finite , and we show that for infinite if there is a such that for every finite . Our results depend on a new condition, expressed in terms of measures on , sufficient to imply that appears in (Theorem 2F), and enable us to identify the extreme points of some convex sets of measures (Theorem 5H).