Large random graphs and random trees: asymptotic behaviour analysis

Abstract : This thesis is dedicated to the study of the asymptotic behavior of some large random graphs and trees. First is studied a random graph model introduced by Bo Söderberg in 2002. One chapter of this manuscript is devoted to the study of the asymptotic behavior of the size of the connected components near the critical window, linking it to the lengths of excursion of a Brownian motion with parabolic drift. The next chapter talks about a random graph process suggested by Itai Benjamini, defined as follows: edges are independently added at a fixe rate. Whenever a vertex reaches degree k, all adjacent edges are removed. This process is non-increasing, preventing the use of some commonly used methods. By using local limits, in the spirit of the PWIT, we were able to prove the presence (resp. absence) of a giant component at some stages of the process when k>=5 (resp. k<=3). In the case k=4, these results allows to link the presence (resp. absence) of a giant component to the supercriticality (resp. criticality or subcriticality) of an associated branching process. In the last chapter, the height of random Lyndon tree is studied, and is proven to be approximately c ln n, in which c=5.092... the solution of an optimization problem. To obtain this result, we couple the Lyndon tree with a Yule tree, then studied with the help of branching walks and large deviations
Document type :
Theses
Complete list of metadatas

Cited literature [60 references]  Display  Hide  Download

https://hal.univ-lorraine.fr/tel-01752205
Contributor : Thèses Ul <>
Submitted on : Thursday, March 29, 2018 - 1:38:16 PM
Last modification on : Thursday, September 27, 2018 - 3:41:32 PM

File

DDOC_T_2016_0028_MERCIER.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : tel-01752205, version 1

Collections

Citation

Lucas Mercier. Large random graphs and random trees: asymptotic behaviour analysis. General Mathematics [math.GM]. Université de Lorraine, 2016. English. ⟨NNT : 2016LORR0028⟩. ⟨tel-01752205⟩

Share

Metrics

Record views

72

Files downloads

56