๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Small variance of subgraph counts in a random tournament

โœ Scribed by Pontus Andersson

Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
78 KB
Volume
49
Category
Article
ISSN
0167-7152

No coin nor oath required. For personal study only.

โœฆ Synopsis

It is known that, for 'most' digraphs D on v vertices, the variance of the number of copies of D in a random tournament on n vertices (chosen uniformly from all such tournaments) is of degree 2v -3 as a polynomial in n. Here we prove that there are arbitrarily large D for which this degree is as small as v.

๐Ÿ“œ SIMILAR VOLUMES

On the asymptotic distributions of subgr
On the asymptotic distributions of subgraph counts in a random tournament
โœ Pontus Andersson ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 191 KB ๐Ÿ‘ 2 views

A random tournament T is obtained by independently orienting the edges of n 1 the complete graph on n vertices, with probability for each direction. We study the 2 asymptotic distribution, as n tends to infinity, of a suitable normalization of the number of subgraphs of T that are isomorphic to a gi