Distribution of tree parameters by martingale approach

Mikhail Isaev; Angus Southwell; Maksim Zhukovskii

doi:10.1017/S0963548321000523

Distribution of tree parameters by martingale approach

Mikhail Isaev, Angus Southwell, Maksim Zhukovskii

School of Mathematics

Research output: Contribution to journal › Article › Research › peer-review

2 Citations (Scopus)

Abstract

For a uniform random labelled tree, we find the limiting distribution of tree parameters which are stable (in some sense) with respect to local perturbations of the tree structure. The proof is based on the martingale central limit theorem and the Aldous-Broder algorithm. In particular, our general result implies the asymptotic normality of the number of occurrences of any given small pattern and the asymptotic log-normality of the number of automorphisms.

Original language	English
Pages (from-to)	737-764
Number of pages	28
Journal	Combinatorics, Probability and Computing
Volume	31
Issue number	5
DOIs	https://doi.org/10.1017/S0963548321000523
Publication status	Published - Sept 2022

Keywords

martingale central limit theorem
pattern counts
random trees
tree automorphisms

Access to Document

10.1017/S0963548321000523Licence: CC BY

Cite this

@article{63ef86fb4a4c47aa8565e427e2b087e1,

title = "Distribution of tree parameters by martingale approach",

abstract = "For a uniform random labelled tree, we find the limiting distribution of tree parameters which are stable (in some sense) with respect to local perturbations of the tree structure. The proof is based on the martingale central limit theorem and the Aldous-Broder algorithm. In particular, our general result implies the asymptotic normality of the number of occurrences of any given small pattern and the asymptotic log-normality of the number of automorphisms.",

keywords = "martingale central limit theorem, pattern counts, random trees, tree automorphisms",

author = "Mikhail Isaev and Angus Southwell and Maksim Zhukovskii",

note = "Funding Information: The first author{\textquoteright}s research is supported by Australian Research Council Discovery Project DP190100977 and by Australian Research Council Discovery Early Career Researcher Award DE200101045. The second author{\textquoteright}s research is supported by an Australian Government Research Training Program (RTP) Scholarship. The third author{\textquoteright}s research is supported by the Ministry of Science and Higher Education of the Russian Federation in the framework of MegaGrant no 075-15-2019-1926 and the Russian Foundation for Basic Research (grant 20-31-70025). Publisher Copyright: {\textcopyright} The Author(s), 2022. Published by Cambridge University Press.",

year = "2022",

month = sep,

doi = "10.1017/S0963548321000523",

language = "English",

volume = "31",

pages = "737--764",

journal = "Combinatorics, Probability and Computing",

issn = "1469-2163",

publisher = "Cambridge University Press",

number = "5",

}

TY - JOUR

T1 - Distribution of tree parameters by martingale approach

AU - Isaev, Mikhail

AU - Southwell, Angus

AU - Zhukovskii, Maksim

N1 - Funding Information: The first author’s research is supported by Australian Research Council Discovery Project DP190100977 and by Australian Research Council Discovery Early Career Researcher Award DE200101045. The second author’s research is supported by an Australian Government Research Training Program (RTP) Scholarship. The third author’s research is supported by the Ministry of Science and Higher Education of the Russian Federation in the framework of MegaGrant no 075-15-2019-1926 and the Russian Foundation for Basic Research (grant 20-31-70025). Publisher Copyright: © The Author(s), 2022. Published by Cambridge University Press.

PY - 2022/9

Y1 - 2022/9

N2 - For a uniform random labelled tree, we find the limiting distribution of tree parameters which are stable (in some sense) with respect to local perturbations of the tree structure. The proof is based on the martingale central limit theorem and the Aldous-Broder algorithm. In particular, our general result implies the asymptotic normality of the number of occurrences of any given small pattern and the asymptotic log-normality of the number of automorphisms.

AB - For a uniform random labelled tree, we find the limiting distribution of tree parameters which are stable (in some sense) with respect to local perturbations of the tree structure. The proof is based on the martingale central limit theorem and the Aldous-Broder algorithm. In particular, our general result implies the asymptotic normality of the number of occurrences of any given small pattern and the asymptotic log-normality of the number of automorphisms.

KW - martingale central limit theorem

KW - pattern counts

KW - random trees

KW - tree automorphisms

UR - http://www.scopus.com/inward/record.url?scp=85129645839&partnerID=8YFLogxK

U2 - 10.1017/S0963548321000523

DO - 10.1017/S0963548321000523

M3 - Article

AN - SCOPUS:85129645839

SN - 1469-2163

VL - 31

SP - 737

EP - 764

JO - Combinatorics, Probability and Computing

JF - Combinatorics, Probability and Computing

IS - 5

ER -

Distribution of tree parameters by martingale approach

Abstract

Keywords

Access to Document

Other files and links

Enhanced methods for approximating the structure of large networks

Hypergraph models for complex discrete systems

Cite this

Distribution of tree parameters by martingale approach

Abstract

Keywords

Access to Document

Other files and links

Projects

Enhanced methods for approximating the structure of large networks

Hypergraph models for complex discrete systems

Cite this