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)}$?

$\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$ Jul 20, 2016 at 23:31

1 Answer 1

6
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.