×

zbMATH — the first resource for mathematics

On the maximum cardinality of a consistent set of arcs in a random tournament. (English) Zbl 0531.05036
Let \(f(T_ n)\) denote the maximum number of arcs possible in an acyclic subgraph of a random tournament \(T_ n\). The author shows that \(f(T_ n)<n(n-1)/4+1.73n^{3/2}\) with probability tending to one as n tends to infinity, thereby sharpening a result of J. Spencer [Period. Math. Hung. 11, 131-144 (1980; Zbl 0349.05011)].
Reviewer: J.W.Moon

MSC:
05C20 Directed graphs (digraphs), tournaments
05C80 Random graphs (graph-theoretic aspects)
60C05 Combinatorial probability
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Chernoff, H, A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations, Ann. math. statist., 23, 493-509, (1963)
[2] Erdös, P; Moon, J.W, On sets of consistent arcs in a tournament, Canad. math. bull., 8, 269-271, (1965) · Zbl 0137.43301
[3] Erdös, P; Spencer, J, ()
[4] Spencer, J, Optimal ranking of tournaments, Networks, 1, 135-138, (1971) · Zbl 0236.05110
[5] Spencer, J, Optimally ranking unrankable tournaments, Period. math. hungar., 11, 2, 131-144, (1980) · Zbl 0349.05011
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.