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

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

Search outside of DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 623 hits
CiteExportLink to record
Permanent link

Direct link
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