2026-07-23T20:01:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11281 2024-03-06T10:47:53Z ddc:004 open_access

Thresholds in Random Motif Graphs Anastos, Michael Michaeli, Peleg Petti, Samantha Random graph Connectivity Hamiltonicty Small subgraphs 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Michael Anastos and Peleg Michaeli and Samantha Petti 2019 Is Part Of LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2019.66 urn:nbn:de:0030-drops-112819 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.66 eng https://creativecommons.org/licenses/by/3.0/legalcode