Phase transitions in random graphs and random graph processes

• Applicant: Professorin Dr. Mihyun Kang
• Subject Area: Mathematics
• Term: from 2011 to 2015
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 191445217

• Final Report Year: 2015

Final Report Abstract

The objective of the research project “Phase transitions in random graph and random graph processes” was to to investigate the phase transitions in random graphs and random graph processes, by means of combination of complementary methods such as analytic approaches, probabilistic methods, and combinatorial counting techniques. The specific goal of the project was to determine the critical edge density for the phase transition, the size distribution of the giant component, connectivity threshold, subgraph containment, component structure, to name a few. During the whole duration of the project period, the applicant conducted successfully the research project and achieved the goals of the project. The main results of the project include (1) Giant component in random hypergraphs; (2) Connectivity threshold of Achlioptas processes; (3) Giant component in random graph processes; (4) Giant component in multi-type random graph model; (5) Connectivity of random graphs from addable classes; (6) Properties of stochastic Kronecker graphs; (7) Bootstrap percolation in inhomogeneous random graphs; (8) Bootstrap percolation in random hypergraphs.

Publications

• Properties of stochastic Kronecker graphs, 37 pages
  M. Kang, M. Karoński, C. Koch, T. Makai
  
• Pursuing the giant in random graph processes, 28 pages
  M. Drmota, M. Kang and K. Panagiotou
  
• On the connectivity of random graphs from addable classes, Journal of Combinatorial Theory B, 103:306–312, 2013
  M. Kang and K. Panagiotou
  (See online at https://doi.org/10.1016/j.jctb.2012.12.001)
• Local limit theorems for the giant component of random hypergraphs, Combinatorics, Probability and Computing, 23:331– 366, 2014
  M. Behrisch, A. Coja-Oghlan and M. Kang
  (See online at https://doi.org/10.1017/S0963548314000017)
• On the connectivity threshold of Achlioptas processes, Journal of Combinatorics, 5:291–304, 2014
  M. Kang and K. Panagiotou
  (See online at https://dx.doi.org/10.4310/JOC.2014.v5.n3.a2)
• The asymptotic number of connected d-uniform hypergraphs, Combinatorics, Probability and Computing, 23:367– 385, 2014
  M. Behrisch, A. Coja-Oghlan and M. Kang
  (See online at https://doi.org/10.1017/S0963548314000029)