摘要：We introduce a natural generalization of the Erdös-Rényi random graph model in which random instances of a fixed motif are added independently. The binomial random motif graph G(H,n,p) is the random (multi)graph obtained by adding an instance of a fixed graph H on each of the copies of H in the complete graph on n vertices, independently with probability p. We establish that every monotone property has a threshold in this model, and determine the thresholds for connectivity, Hamiltonicity, the existence of a perfect matching, and subgraph appearance. Moreover, in the first three cases we give the analogous hitting time results; with high probability, the first graph in the random motif graph process that has minimum degree one (or two) is connected and contains a perfect matching (or Hamiltonian respectively).
关键词：Random graph; Connectivity; Hamiltonicty; Small subgraphs
