Temps de frappe du pire des pires

Question

Considérez une simple marche aléatoire sur un graphique non dirigé et laissez $ h_ {ij} $ être l'heure de frappe de $ i $ à $ j $. Combien plus gros peut $$ h _ { rm max} = max_ {i, j} h_ {ij}, $$ être comparé à $$ h _ { rm Ave} = frac {1} {n ^ 2} sum_ {i = 1} ^ n sum_ {j = 1} ^ n h_ {ij}. $$ pour tous les exemples auxquels je peux penser, ces deux quantités sont à peu près du même ordre de grandeur.

Pour en faire une question formelle, définissez $$ phi (n) = max _ { mbox {graphiques non dirigés avec} n mbox {nœuds}} frac {h _ { rm max}} {h _ { rm Ave }}. $$ à quelle vitesse $ phi (n) $ grandit-elle avec $ n $?