随机图的■-全局性

■-Universality of Random Graphs

■(n,Δ,d_(m))表示一类n个点的图,其最大度为Δ,最大密度为d_(m)。如果图G包含■中所有的图■,那么称图G是■-全局性的。运用概率方法证明了当概率p大于某个阈值时,图G~■(n,p)以趋近于1的概率是■(n,Δ,d_(m))-全局性的。

Using■(n,Δ,d_(m))to denote the family of all n vertices graphs with maximum degree at mostΔand maximum density at most d_(m).A graph G is universal for■(we write G is■-universal),if G contains a copy of every graph H∈■.Using probability methods to prove that when the probability p is greater than a certain threshold,a graph G~■(n,p)is high probability■(n,Δ,d_(m))-universality.