AG 1   Info

AG Audience

English

30 Minutes

Saarbrücken

In my PhD work I studied several random graph processes that involve some power of choice – e.g., in each step we get *two* random edges and are allowed to select the 'better' one from those for inclusion in the evolving graph. Usually our goal is to minimize or maximize the number of steps until the evolving graph satisfies some given property – e.g., contains a triangle or a linear-sized ('giant') component. What is the best we can achieve, and how should we play?

I will present several variations on this theme and point out some surprising phenomena that occur in these processes.

Reto Spöhel

--email hidden

passcode not visible

logged in users only