uu.seUppsala University Publications
Change search
ReferencesLink to record
Permanent link

Direct link
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. , 11 p.
Uppsala Dissertations in Mathematics, ISSN 1401-2049 ; 14
Keyword [en]
Mathematics, Poisson-Dirichlet distribution, random circuit decomposition, random tournament, subgraph count
Keyword [sv]
National Category
Research subject
URN: urn:nbn:se:uu:diva-58ISBN: 91-506-1380-4OAI: oai:DiVA.org:uu-58DiVA: 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

By organisation
Department of Mathematics

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 309 hits
ReferencesLink to record
Permanent link

Direct link