0
$\begingroup$

Build a random tournament $T=(V,E)$ on $V=\{1,\ldots, n\}$ in the following fashion: for $i < j\in \{1,\ldots, n\}$ let the probability be $0.5$ whether $(i,j)\in E$ or $(j,i)\in E$ (in a tournament, exactly one of these is the case).

Let $E(n)$ be the expected value of the longest directed circuit in $T$.

Is there a formula for $E(n)$? If not: do we know anything about $\lim_{n\to\infty}\frac{E(n)}{\sqrt{n}}$ or $\lim_{n\to\infty}\frac{E(n)}{\log(n)}$?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ A simpler question is the length of the longest directed path: that's $n$, in any tournament on $n$ vertices. $\endgroup$
    – Gerry Myerson
    Commented Jul 20, 2016 at 23:31

1 Answer 1

Reset to default
6
$\begingroup$

A random tournament is strongly connected with probability tending to 1 exponentially fast, and all strongly connected tournaments have hamiltonian cycles.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .