On the evolution of a random tournament
Let \(T(n, p)\) denote a random tournament with nodes \(1, 2,\dots, n\) such that for each pair of nodes \(i\) and \(j\), \(1\leq i< j\leq n\), the probability that the arc joining \(i\) and \(j\) is oriented from \(i\) to \(j\) is \(p\). The authors determine the threshold functions for small subgraphs of \(T(n, p)\); and they determine, for a wide range of \(p= p(n)\), the size of the largest strong component of \(T(n, p)\). In particular, they show that if \(p\leq 1/2\) then the limit as \(n\to \infty\) of the probability that \(T(n, p)\) is strongly connected equals \(0\), \((1- e^{- c})^2\), or 1 if \(np\) tends to \(0\), \(c\), or \(\infty\).
scientific article; zbMATH DE number 858093