uu.seUppsala University Publications
Change search

Cite
Citation style
• apa
• ieee
• modern-language-association
• vancouver
• Other style
More styles
Language
• de-DE
• en-GB
• en-US
• fi-FI
• nn-NO
• nn-NB
• sv-SE
• Other locale
More languages
Output format
• html
• text
• asciidoc
• rtf
Random tournaments and random circuits
Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Mathematics.
1999 (English)Doctoral thesis, comprehensive summary (Other academic)
##### Abstract [en]

This thesis is devoted to two different topics in the area of probabilistic combinatorics: asymptotic behaviour of subgraph counts in a random tournament and random circuit decompositions of complete graphs.

Let Tn be a random tournament on n vertices, chosen uniformly from all 2(n2) such tournaments, and let D be an arbitrary directed graph. Then the number of copies of D in Tn is a random variable which, after normalization, converges in distribution as n tends to infinity. The limit distribution is determined, and it turns out to be normal for a typical D, but for some D it is a quadratic polynomial in normal variables. It is also shown that the variance of the number of copies of D in Tn is a polynomial in n and that the degree of this polynomial is, for a typical D, 2v - 3, where v is the number of vertices of D. However, examples are given for which this degree is as low as v.

Some directed graphs turn out to appear the same number of times in all tournaments with a fixed number of vertices. A partial characterization of these directed graphs is given.

In the complete undirected or directed graph on n vertices, choose a random decomposition of the set of all edges into circuits, uniformly from all such decompositions. Letting Lk be the fraction of edges contained in the k-th longest circuit in this decomposition, it is shown that (L1, L2,...) converges to a Poisson-Dirichlet distribution as n tends to infinity. It is also shown that the numbersof circuits of given lengths converge jointly to independent Poisson variables, and that the expected number of circuits is log n + O(1) in the undirected case and 2 log n + O(1) in the directed case.

##### Place, publisher, year, edition, pages
Uppsala: Acta Universitatis Upsaliensis , 1999. , p. 11
##### Series
Uppsala Dissertations in Mathematics, ISSN 1401-2049 ; 14
##### Keywords [en]
Mathematics, Poisson-Dirichlet distribution, random circuit decomposition, random tournament, subgraph count
MATEMATIK
Mathematics
Mathematics
##### Identifiers
ISBN: 91-506-1380-4 (print)OAI: oai:DiVA.org:uu-58DiVA, id: diva2:166421
##### Public defence
1999-12-17, Room 247, Building 2, Polacksbacken, Uppsala University, Uppsala, 13:15
Available from: 1999-11-26 Created: 1999-11-26Bibliographically approved

#### Open Access in DiVA

No full text in DiVA
##### By organisation
Department of Mathematics
Mathematics

isbn
urn-nbn

#### Altmetric score

isbn
urn-nbn
Total: 645 hits

Cite
Citation style
• apa
• ieee
• modern-language-association
• vancouver
• Other style
More styles
Language
• de-DE
• en-GB
• en-US
• fi-FI
• nn-NO
• nn-NB
• sv-SE
• Other locale
More languages
Output format
• html
• text
• asciidoc
• rtf