Long paths and cycles in dynamical graphs

Forskningsoutput: TidskriftsbidragArtikel i vetenskaplig tidskrift

Abstract

We study the large-time dynamics of a Markov process whose states are finite directed graphs. The number of the vertices is described by a supercritical branching process, and the edges follow a certain mean-field dynamics determined by the rates of appending and deleting. We find sufficient conditions under which asymptotically a.s. the order of the largest component is proportional to the order of the graph. A lower bound for the length of the longest directed path in the graph is provided as well. We derive an explicit formula for the limit as time goes to infinity, of the expected number of cycles of a given finite length. Finally, we study the phase diagram.

Detaljer

Författare
Enheter & grupper
Forskningsområden

Ämnesklassifikation (UKÄ) – OBLIGATORISK

  • Sannolikhetsteori och statistik

Nyckelord

Originalspråkengelska
Sidor (från-till)385-417
TidskriftJournal of Statistical Physics
Volym110
Utgåva nummer1-2
StatusPublished - 2003
PublikationskategoriForskning
Peer review utfördJa