Document Open Access Logo

Thresholds in Random Motif Graphs

Authors Michael Anastos , Peleg Michaeli , Samantha Petti

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2019.66.pdf
  • Filesize: 0.56 MB
  • 19 pages

Document Identifiers

Author Details

Michael Anastos
  • Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, Pennsylvania, USA
Peleg Michaeli
  • School of Mathematical Sciences, Tel Aviv University, Israel
Samantha Petti
  • School of Mathematics, Georgia Institute of Technology, Atlanta, Georgia, USA

Funding

  • Michaeli, Peleg: This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement number 676970, RANDGEOM).
  • Petti, Samantha: This material is based upon work supported by the National Science Foundation Graduate Research Fellowship under Grant No. DGE-1650044.

Acknowledgements

We thank Alan Frieze for helpful discussions and for connecting the authors.

Cite As Get BibTex

Michael Anastos, Peleg Michaeli, and Samantha Petti. Thresholds in Random Motif Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 66:1-66:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.66

Abstract

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).

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Random graphs
  • Mathematics of computing → Paths and connectivity problems
Keywords
  • Random graph
  • Connectivity
  • Hamiltonicty
  • Small subgraphs

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Noga Alon and Joel H. Spencer. The probabilistic method. Wiley Series in Discrete Mathematics and Optimization. John Wiley & Sons, Inc., Hoboken, NJ, fourth edition, 2016. Google Scholar
  2. Uri Alon. Network motifs: theory and experimental approaches. Nature Reviews Genetics, 8(6):450-461, 2007. Google Scholar
  3. Albert-László Barabási and Réka Albert. Emergence of scaling in random networks. Science, 286(5439):509-512, 1999. URL: https://doi.org/10.1126/science.286.5439.509.
  4. Béla Bollobás. Random graphs. Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London, 1985. Google Scholar
  5. Béla Bollobás and Andrew Thomason. Hereditary and monotone properties of graphs. In The mathematics of Paul Erdős, II, volume 14 of Algorithms Combin., pages 70-78. Springer, Berlin, 1997. URL: https://doi.org/10.1007/978-3-642-60406-5_7.
  6. Paul Erdős and Alfréd Rényi. On random graphs. I. Publicationes Mathematicae Debrecen, 6:290-297, 1959. Google Scholar
  7. Paul Erdős and Alfréd Rényi. On the evolution of random graphs. Magyar Tud. Akad. Mat. Kutató Int. Közl., 5:17-61, 1960. Google Scholar
  8. Alan Frieze, Navin Goyal, Luis Rademacher, and Santosh Vempala. Expanders via random spanning trees. SIAM Journal on Computing, 43(2):497-513, 2014. URL: https://doi.org/10.1137/120890971.
  9. Alan Frieze and Michał Karoński. Introduction to random graphs. Cambridge University Press, Cambridge, 2016. URL: https://doi.org/10.1017/CBO9781316339831.
  10. Alan Frieze, Michał Karoński, and Luboš Thoma. On perfect matchings and Hamilton cycles in sums of random trees. SIAM Journal on Discrete Mathematics, 12(2):208-216, 1999. URL: https://doi.org/10.1137/S0895480196313790.
  11. Edgar N. Gilbert. Random graphs. Annals of Mathematical Statistics, 30:1141-1144, 1959. URL: https://doi.org/10.1214/aoms/1177706098.
  12. Svante Janson, Tomasz Łuczak, and Andrzej Rucinski. Random graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience, New York, 2000. URL: https://doi.org/10.1002/9781118032718.
  13. Michael Krivelevich and Peleg Michaeli. Small subgraphs in the trace of a random walk. Electronic Journal of Combinatorics, 24(1):Paper 1.28, 22, 2017. Google Scholar
  14. Ron Milo, Shai Shen-Orr, Shalev Itzkovitz, Nadav Kashtan, Dmitri B. Chklovskii, and Uri Alon. Network motifs: simple building blocks of complex networks. Science, 298(5594):824-827, 2002. Google Scholar
  15. Samantha Petti and Santosh S. Vempala. Approximating Sparse Graphs: The Random Overlapping Communities Model. arXiv e-prints, February 2018. URL: http://arxiv.org/abs/1802.03652.
  16. Daniel Poole. On the strength of connectedness of a random hypergraph. Electronic Journal of Combinatorics, 22(1):Paper 1.69, 16, 2015. Google Scholar
  17. Sen Song, Per Jesper Sjöström, Markus Reigl, Sacha B. Nelson, and Dmitri B. Chklovskii. Highly nonrandom features of synaptic connectivity in local cortical circuits. PLoS biology, 3(3):e68, 2005. Google Scholar
  18. Duncan J. Watts and Steven H. Strogatz. Collective dynamics of "small-world" networks. Nature, 393(6684):440-442, 1998. URL: https://doi.org/10.1038/30918.
  19. Nicholas C. Wormald. Models of random regular graphs. In Surveys in combinatorics, 1999 (Canterbury), volume 267 of London Math. Soc. Lecture Note Ser., pages 239-298. Cambridge Univ. Press, Cambridge, 1999. Google Scholar
  20. Esti Yeger-Lotem, Shmuel Sattath, Nadav Kashtan, Shalev Itzkovitz, Ron Milo, Ron Y. Pinter, Uri Alon, and Hanah Margalit. Network motifs in integrated cellular networks of transcription-regulation and protein-protein interaction. Proceedings of the National Academy of Sciences of the United States of America, 101(16):5934-5939, 2004. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact