Inhomogeneous random graphs

Standard - GACR GA26-23695S [Registered results] 2026 - 2028

Principal Investigator: Mgr. Jan Hladký, Ph.D.

The project will study central questions regarding a general model of random graphs based on graphons (and in sparse regimes, based on unbounded kernels).

Three areas are in focus

  1. Sparse inhomogeneous random graph (as introduced by Bollobas, Janson, and Riordan) and their connection to branching processes. A new class of extremal problems (including questions about the giant component) is proposed, and an inhomogeneous variant of the result about k-cores of Pittel, Spencer, and Wormald is given.
  2. A statistical question of community detection in inhomogeneous random graph models. In particular, a novel framework which will allow to refine breakthrough results of Abbe and Sandon is proposed.
  3. Development of tools from statistical mechanics for inhomogeneous random graphs (in particular in connection with the Belief propagation algorithm and with the interpolation method of Bayati, Gamarnik, and Tetali).