On the longest path of a randomly weighted tournament

If D has finite mean μ, then ℓ(G,D)≥μ(n−1) is a trivial lower bound, with equality if D is constant, as by Redei's Theorem, every tournament has a Hamilton path. However, already for very simple nontrivial distributions, it is challenging to determine ℓ(G,D) even asymptotically, and even if the tournament is small and fixed. We consider the two natural distributions of the random weighted model, the continuous uniform distribution U[0,1] and the symmetric Bernoulli distribution U{0,1}. Our first result is that for any tournament, both ℓ(G,U{0,1}) and ℓ(G,U[0,1]) are larger than the above trivial 0.5(n−1) lower bound in the sense that 0.5 can be replaced by a larger constant. To this end we prove the existence of dense partial squares of Hamilton paths in any tournament, a combinatorial result which seems of independent interest. Regarding upper bounds, while for some tournaments one can prove that both ℓ(G,U{0,1}) and ℓ(G,U[0,1]) are n−o(n), we prove that there are other tournaments for which both ℓ(G,U{0,1}) and ℓ(G,U[0,1]) are significantly smaller. In particular, for every n, there are n-vertex tournaments for which ℓ(G,U{0,1})≤0.614(n−1). Finally, we state several natural open problems arising in this setting.