BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Depth-First Search in a Random Digraph - Svante Janson (Uppsala Un
 iversitet)
DTSTART:20220906T153000Z
DTEND:20220906T163000Z
UID:TALK178481@talks.cam.ac.uk
CONTACT:Jason Miller
DESCRIPTION:We study the Depth-First Search algorithm\, applied to a rando
 m digraph ($=$ directed graph).\nThe random digraph is constructed by givi
 ng the vertices i.i.d.\\ outdegrees\, and choosing the endpoint of all arc
 s independently and uniformly at random.\n(Loops and multiple edges are al
 lowed\, but not important.)  \nThe Depth-First Search can be regarded as b
 uilding a forest which eventually contains all vertices. One important pro
 perty is the depth of vertices in this forest\,\ni.e.\\ the distance to th
 e root.\nA particularly simple case is when the outdegree distribution is 
 geometric. Its lack of memory implies that that the depths of the evrtices
  form a Markov process\, which can be analyzed.\nFor a general outdegree d
 istribution\, this is no longer true\; as a substitute\, we study a relate
 d process\, which is Markov\, and then are able to draw conclusions also f
 or the depth.  (Based on joint work with Philippe Jacquet.)
LOCATION:MR9\, Centre for Mathematical Sciences
END:VEVENT
END:VCALENDAR