Colin Cooper -King's College, University of London

The cover time of random walks on random graphs

Abstract: Let G=(V,E) be a connected graph. For v in V let C_v be the expected time taken for a simple random walk on G starting at v to visit every vertex of G.

The cover time C_G of G is defined as C_G=max_{{v in V}}C_v.

It is a result of Feige that for a connected n vertex graph the cover time lies between n log n and 4n³/27 asymptotically.

We discuss some techniques for finding precise values of cover time which apply readily to random graphs. We obtain the cover time of: G_{n,p} after connectivity, random regular graphs, the preferential attachment graph and the giant component of G_{n,p} after p=1/n.

It is seen that an important quantity in obtaining the cover time is the expected number of returns to a given vertex during the mixing time.

We also discuss the topic of crawling on web-graphs (a random walk on a growing web graph starting at vertex 1) to obtain the limiting proportion of vertices visited.

Colloquium - 16 Uhr s.t.

Taral Guldahl Seierstad -Humboldt-Universität zu Berlin

The giant component in the minimum degree graph process

Abstract: We consider a random graph process as follows. We start with an empty graph on n vertices. At every stage we choose a vertex of minimum degree at random, and join it with an edge to another vertex chosen at random from all the other vertices in the graph. We prove that this process exhibits a "phase transition" similar to the standard random graph, G(n,p), where the order of the largest component grows quickly during a short period of time. In particular we prove that there is a constant h = 0.8607..., such that if we consider the graph process when t*n edges have been added, then with high probability, the largest component has logarithmic order when t<h, whereas there is a unique component of linear order when t>h.