Theorem (Szele 1943) There is a tournament on n players with at least n!2-(n-1)Hamiltonian paths. Pick a random tournament T on n players [n]. For every permutation x of [n], 1 πis a Hamiltonian path x is not a Hamiltonian path Hamiltonian paths:= π E[X]=Pr[XI =1]=2-(n-1)There is a tournament on n players with at least n!2￾(n￾1) Hamiltonian paths. Theorem (Szele 1943) For every permutation π of [n], π is a Hamiltonian path π is not a Hamiltonian path X￾ = ￾ 1 0 Pick a random tournament T on n players [n]. X = ￾ ￾ # Hamiltonian paths: X￾ E[X￾] = Pr[X￾ = 1] = 2￾(n￾1)