Penn Arts & Sciences Logo

Probability and Combinatorics

Tuesday, January 11, 2005 - 4:30pm

Joel Spencer

Courant Institute

Location

University of Pennsylvania

DRL 4N30

Let $C(k,l)$ be the number of labelled connected graphs with $k$ vertices, $k-1+l$ edges. We employ random graphs and breadth first search techniques to find the asymptotics of $C(k,l)$ whenever $k$ and $l$ tend to infinity. The probabilistic analysis has, at its heart, a biased bridge. We place $k-1$ balls into $k$ bins, ball $j$ going into bin $i$ with probability $p(1-p)^{i-1}/(1-p^k)$, a truncated exponential with ``tilt" $p$. With $Z_t$ balls in bin $t$ the ``queue walk" has $Y_0=1$, $Y_t=Y_{t-1}+Z_t-1$ and thus $Y_k=0$. When $p\gg k^{-3/2}$ we analyze the probability that the walk has $Y_t>0$ for all $0\leq t