Tid: 27 september 1999 kl 1515-1700

Plats : Seminarierummet 3733, Institutionen för matematik, KTH, Lindstedts väg 25, plan 7. Karta!

Föredragshållare: Johan Jonasson, Matematisk statistik, Chalmers Tekniska Högskola. Publikationslista (List of Publications).

Titel: My three favorite proofs and some related open problems.


1. Matthews' theorem on the cover time for a simple random walk on a finite graph: Let $\,T(u,v)$ denote the time taken for a random walk starting from $\,u$ to hit $\,v$. Set $h = \min_{u \neq v}E[T(u,v)]$ and $H = \max_{u,v}E[T(u,v)]$ and let $\,C_u$ denote the cover time, i.e the time taken for a random walk starting from $\,u$ to visit every vertex of the graph. Then $h \log n \leq 
 E[C_u] \leq H \log n$ for any $\,u$, where $\,n$ is the number of vertices in the graph.

2. To properly mix a deck of $\,n$ cards using the ordinary riffle shuffle, $2\log_2 n$ shuffles suffices.

3. The exact critical value for iid percolation on the triangular lattice is $2\sin(\pi/18)$.

In connection to these results we also give some examples of intriguing open problems.

Till seminarielistan
To the list of seminars