On the evolution of a random tournament
type: Item
instance of: scholarly article
title: On the evolution of a random tournament
zbMATH Open document ID: 0842.05081
DOI: 10.1016/0012-365X(94)00279-R
author: Tomasz Łuczak
author: Jacek Gruszka
author: Andrzej Ruciński
published in: Discrete Mathematics
publication date: 1996-03-24T00:00:00Z
review text: 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\).
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 858093
zbMATH Keywords: random tournament
zbMATH Keywords: threshold functions
reviewed by: J. W. Moon
MaRDI profile type: Publication
cites work: Stochastic Competition Graphs
cites work: Q3997075
cites work: Q3203051
cites work: Q5585195
cites work: Almost all Tournaments are Irreducible
cites work: Q4697464
full work available at URL: 0012-365x(94)00279-r
OpenAlex ID: W2114498279
description: scientific article; zbMATH DE number 858093