Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • 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
Degrees in Random Graphs and Tournament Limits
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.ORCID iD: 0000-0002-0592-1808
2018 (English)Doctoral thesis, comprehensive summary (Other academic)
Description
Abstract [en]

This thesis consists of an introduction and six papers on the topics of degree distributions in random graphs and tournaments and their limits.

The first two papers deal with a dynamic random graph, evolving in time through duplication and deletion of vertices and edges. In Paper I we study the degree densities of this model. We show that these densities converge almost surely and determine their limiting values exactly as well as asymptotically for large degrees. In Paper II we study the evolution of the maximum degree and provide a precise growth rate thereof.

Paper III deals with a dynamic random tree model known as the vertex-splitting tree model. We show that the degree densities converge almost surely and find an infinite linear system of equations which they must satisfy. Unfortunately we are not able to show that this system has a unique solution except in special cases.

Paper IV is about self-converse generalised tournaments. A self-converse generalised tournament can be seen as a matrix whose entries take values in [0,1] and whose diagonally opposite elements sum to 1. We characterise completely the marginals of such a matrix, and show that such marginals can always be realised by a self-converse generalised tournament.

In Paper V, we define and develop the theory of tournament limits and tournament kernels. We characterise transitive and irreducible tournament limits and kernels, and prove that any tournament limit and kernel has an essentially unique decomposition into irreducible tournament limits or kernels interlaced by a transitive part.

In Paper VI, we study the degree distributions of tournament limits, or equivalently, the marginals of tournament kernels. We describe precisely which distributions on [0,1] which may appear as degree distributions of tournament limits and which functions from [0,1] to [0,1] may appear as the marginals of tournament kernels. Moreover, we show that any distribution or marginal on this form may be realised by a tournament limit or tournament kernel. We also study those distributions and marginals which can be realised by a unique tournament limit or kernel, and find that only the transitive tournament limit/kernel gives rise to a degree distribution or marginal with this property.

Place, publisher, year, edition, pages
Uppsala: Department of Mathematics, 2018. , p. 26
Series
Uppsala Dissertations in Mathematics, ISSN 1401-2049 ; 105
Keywords [en]
Random graphs, degree distributions, degree sequences, graph limits, tournaments
National Category
Mathematics
Research subject
Mathematics
Identifiers
URN: urn:nbn:se:uu:diva-339025ISBN: 978-91-506-2677-3 (print)OAI: oai:DiVA.org:uu-339025DiVA, id: diva2:1175059
Public defence
2018-03-09, Polhemssalen, Ångströmlaboratoriet, Lägerhyddsvägen 1, Uppsala, 13:15 (English)
Opponent
Supervisors
Available from: 2018-02-14 Created: 2018-01-17 Last updated: 2018-02-14
List of papers
1. Asymptotic Degree Distribution Of A Duplication-Deletion Random Graph Model
Open this publication in new window or tab >>Asymptotic Degree Distribution Of A Duplication-Deletion Random Graph Model
2015 (English)In: Internet Mathematics, ISSN 1542-7951, E-ISSN 1944-9488, Vol. 11, no 3, p. 289-305Article in journal (Refereed) Published
Abstract [en]

We study a discrete-time duplication-deletion random graph model and analyze its asymptotic degree distribution. The random graphs consist of disjoint cliques. In each time step, either a new vertex is brought in with probability 0 < p < 1 and attached to an existing clique, chosen with probability proportional to the clique size, or all the edges of a random vertex are deleted with probability 1 p. We prove almost sure convergence of the asymptotic degree distribution and find its exact values in terms of a hypergeometric integral, expressed in terms of the parameter p. In the regime 0 < p< 1/2 , we show that the degree sequence decays exponentially at rate p/1-p, whereas it satisfies a power law with exponent 2, if 1/2 < p< 1. At the threshold p = 1/2, the degree sequence lies between a power law and exponential decay.

National Category
Mathematics
Identifiers
urn:nbn:se:uu:diva-311631 (URN)10.1080/15427951.2015.1009523 (DOI)000388715000006 ()
Available from: 2016-12-30 Created: 2016-12-30 Last updated: 2018-01-17Bibliographically approved
2. The dominating colour of an infinite Pólya urn model
Open this publication in new window or tab >>The dominating colour of an infinite Pólya urn model
2016 (English)In: Journal of Applied Probability, ISSN 0021-9002, E-ISSN 1475-6072, Vol. 53, no 3, p. 914-924Article in journal (Refereed) Published
Abstract [en]

We study a Pólya-type urn model defined as follows. Start at time 0 with a single ball of some colour. Then, at each time n≥1, choose a ball from the urn uniformly at random. With probability ½<p<1, return the ball to the urn along with another ball of the same colour. With probability 1−p, recolour the ball to a new colour and then return it to the urn. This is equivalent to the supercritical case of a random graph model studied by Backhausz and Móri (2015), (2016) and Thörnblad (2015). We prove that, with probability 1, there is a dominating colour, in the sense that, after some random but finite time, there is a colour that always has the most number of balls. A crucial part of the proof is the analysis of an urn model with two colours, in which the observed ball is returned to the urn along with another ball of the same colour with probability p, and removed with probability 1−p. Our results here generalise a classical result about the Pólya urn model (which corresponds to p=1).

National Category
Probability Theory and Statistics
Identifiers
urn:nbn:se:uu:diva-274483 (URN)10.1017/jpr.2016.49 (DOI)000386349900019 ()
Available from: 2016-01-21 Created: 2016-01-21 Last updated: 2018-01-17Bibliographically approved
3. Almost sure convergence of vertex degree densities in the vertex splitting model
Open this publication in new window or tab >>Almost sure convergence of vertex degree densities in the vertex splitting model
2016 (English)In: Communications in Statistics. Stochastic Models, ISSN 1532-6349, E-ISSN 1532-4214, Vol. 32, no 4, p. 575-592Article in journal (Refereed) Published
Abstract [en]

We study the limiting degree distribution of the vertex splitting model introduced in Ref.([3]). This is a model of randomly growing ordered trees, where in each time step the tree is separated into two components by splitting a vertex into two, and then inserting an edge between the two new vertices. Under some assumptions on the parameters, related to the growth of the maximal degree of the tree, we prove that the vertex degree densities converge almost surely to constants which satisfy a system of equations. Using this, we are also able to strengthen and prove some previously non-rigorous results mentioned in the literature.

Keywords
Almost sure convergence, degree densities, random trees, vertex splitting, 05C80, 05C05
National Category
Probability Theory and Statistics
Identifiers
urn:nbn:se:uu:diva-303159 (URN)10.1080/15326349.2016.1182029 (DOI)000380246200003 ()
Available from: 2016-09-15 Created: 2016-09-15 Last updated: 2018-01-17Bibliographically approved
4. Eplett's theorem for self-converse generalised tournaments
Open this publication in new window or tab >>Eplett's theorem for self-converse generalised tournaments
2018 (English)In: The Australasian Journal of Combinatorics, ISSN 1034-4942, Vol. 70, no 3, p. 329-335Article in journal (Refereed) Published
Abstract [en]

The converse of a tournament is obtained by reversing all arcs. If a tournament is isomorphic to its converse, it is called self-converse. Eplett provided a necessary and sufficient condition for a sequence of integers to be realisable as the score sequence of a self-converse tournament. In this paper we extend this result to generalised tournaments.

National Category
Mathematics
Identifiers
urn:nbn:se:uu:diva-335318 (URN)000424085800004 ()
Available from: 2017-12-04 Created: 2017-12-04 Last updated: 2018-03-28Bibliographically approved
5. Decomposition of tournament limits
Open this publication in new window or tab >>Decomposition of tournament limits
2018 (English)In: European journal of combinatorics (Print), ISSN 0195-6698, E-ISSN 1095-9971, Vol. 67, p. 96-125Article in journal (Refereed) Published
Abstract [en]

The theory of tournament limits and tournament kernels is developed by extending common notions for finite tournaments to this setting; in particular we study transitivity and irreducibility of limits and kernels. We prove that each tournament kernel and each tournament limit can be decomposed into a direct sum of irreducible components, with transitive components interlaced. We also show that this decomposition is essentially unique.

National Category
Mathematics
Identifiers
urn:nbn:se:uu:diva-335316 (URN)10.1016/j.ejc.2017.07.023 (DOI)000413385900007 ()
Available from: 2017-12-04 Created: 2017-12-04 Last updated: 2018-02-05Bibliographically approved
6. Tournament limits: Degree distributions, score functions and self-converseness
Open this publication in new window or tab >>Tournament limits: Degree distributions, score functions and self-converseness
(English)Manuscript (preprint) (Other academic)
National Category
Mathematics
Identifiers
urn:nbn:se:uu:diva-335319 (URN)
Available from: 2017-12-04 Created: 2017-12-04 Last updated: 2018-01-17

Open Access in DiVA

fulltext(399 kB)89 downloads
File information
File name FULLTEXT01.pdfFile size 399 kBChecksum SHA-512
ce44789d97001c9f36b2931b79ca9d6f780cb855db03bd40ef5ab78542aa48f1459096a34048738c6dc5440ca800e307ab1b926caeca9169b8639a1dc9b43cdc
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Thörnblad, Erik
By organisation
Department of Mathematics
Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 89 downloads
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

isbn
urn-nbn

Altmetric score

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

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • 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