Asymptotiques de fonctionnelles d'arbres aléatoires et de graphes denses aléatoires

Abstract : The aim of this thesis is the study of approximations and rates of convergence for functionals of large dicsrete graphs towards their limits. We contemplate two cases of discrete graphs: trees (i.e. connected graphs without cycles) and dense simple finite graphs. In the first case, we consider additive functionals for two models of random trees: the Catalan model for binary trees (where a tree is chosen uniformly at random from the set of full binary trees with a given number of nodes) and the simply generated trees (and more particulary the Galton-Watson trees conditioned by their number of nodes).Asymptotic results are based on scaling limits of conditioned Galton-Watson trees. Indeed, when the offspring distribution is critical and with finite variance (that is the case of Catalan binary trees), the Galton-Watson trees conditioned to have a large number of nodes converge towards the Brownian continuum tree which is a real tree coded which can be coded by the normalized Brownian excursion. Furthermore, binary trees under the Catalan model can be built as sub-trees of the Brownian continuum tree. This embedding makes it possible to obtain almost sure convergences of functionals. More generally, when the offspring distribution is critical and belongs to the domain of attraction of a stable distribution, the Galton-Watson trees conditioned to have a large number of nodes converge to stable Levy trees giving the asymptotic behaviour of additive functionals for some simply generated trees. In the second case, we are interested in the convergence of the empirical cumulative distribution of degrees and the homomorphism densities of sequences of dense simple finite graphs. A sequence of dense simple finite graphs converges if the real sequence of associated homomorphism densities converges for all simple finite graph. The limit of such a sequence of dense graphs can be described as a symmetric measurable function called graphon.Given a graphon, we can construct by sampling, a sequence of graphs which converges towards this graphon. We have studied the asymptotic behaviour of the empirical cumulative distribution of degrees and random measures built from homomorphism densities associated to this special sequence of dense graphs
Document type :
Theses
Complete list of metadatas

Cited literature [205 references]  Display  Hide  Download

https://pastel.archives-ouvertes.fr/tel-02084023
Contributor : Abes Star <>
Submitted on : Friday, March 29, 2019 - 12:44:29 PM
Last modification on : Monday, April 8, 2019 - 6:07:24 PM
Long-term archiving on : Sunday, June 30, 2019 - 2:29:10 PM

File

TH2018PESC1127.pdf
Version validated by the jury (STAR)

Identifiers

  • HAL Id : tel-02084023, version 1

Collections

Citation

Marion Sciauveau. Asymptotiques de fonctionnelles d'arbres aléatoires et de graphes denses aléatoires. Algèbres d'opérateurs [math.OA]. Université Paris-Est, 2018. Français. ⟨NNT : 2018PESC1127⟩. ⟨tel-02084023⟩

Share

Metrics

Record views

174

Files downloads

88