Random cographs: Brownian graphon limit and asymptotic degree distribution
| العنوان: | Random cographs: Brownian graphon limit and asymptotic degree distribution |
|---|---|
| المؤلفون: | Frédérique Bassino, Lucas Gerin, Valentin Féray, Adeline Pierrot, Mathilde Bouvel, Mickaël Maazoun |
| المساهمون: | University of Zurich, Féray, Valentin, Laboratoire d'Informatique de Paris-Nord (LIPN), Université Sorbonne Paris Cité (USPC)-Institut Galilée-Université Paris 13 (UP13)-Centre National de la Recherche Scientifique (CNRS), Institut für Mathematik [Zürich], Universität Zürich [Zürich] = University of Zurich (UZH), Designing the Future of Computational Models (MOCQUA), Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL), Institut Élie Cartan de Lorraine (IECL), Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Centre de Mathématiques Appliquées - Ecole Polytechnique (CMAP), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), Unité de Mathématiques Pures et Appliquées (UMPA-ENSL), Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon), Bioinformatique (LRI) (BioInfo - LRI), Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Swiss National Science Foundation, undergrant number 200021-17253, ANR-14-CE25-0014,GRAAL,GRaphes et Arbres ALéatoires(2014), Centre National de la Recherche Scientifique (CNRS)-Université Sorbonne Paris Nord, Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), École normale supérieure de Lyon (ENS de Lyon)-Centre National de la Recherche Scientifique (CNRS), Laboratoire Interdisciplinaire des Sciences du Numérique (LISN), Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS) |
| المصدر: | Random Structures and Algorithms Random Structures and Algorithms, Wiley, In press, ⟨10.1002/rsa.21033⟩ Random Structures and Algorithms, 2022, 60 (2), pp.166-200. ⟨10.1002/rsa.21033⟩ |
| سنة النشر: | 2022 |
| مصطلحات موضوعية: | General Mathematics, Computer Graphics and Computer, Asymptotic distribution, 340 Law, 610 Medicine & health, 0102 computer and information sciences, 01 natural sciences, 1704 Computer Graphics and Computer-Aided Design, Combinatorics, 510 Mathematics, 2604 Applied Mathematics, Computer Science::Discrete Mathematics, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], FOS: Mathematics, Mathematics - Combinatorics, Cograph, Aided Design, 0101 mathematics, Brownian motion, Mathematics, 2600 General Mathematics, Lebesgue measure, Degree (graph theory), Applied Mathematics, Probability (math.PR), 010102 general mathematics, Brownian excursion, Degree distribution, Computer Graphics and Computer-Aided Design, Vertex (geometry), [MATH.MATH-PR]Mathematics [math]/Probability [math.PR], 1712 Software, 10123 Institute of Mathematics, 010201 computation theory & mathematics, Combinatorics (math.CO), Mathematics - Probability, Software |
| الوصف: | We consider uniform random cographs (either labeled or unlabeled) of large size. Our first main result is the convergence towards a Brownian limiting object in the space of graphons. We then show that the degree of a uniform random vertex in a uniform cograph is of order $n$, and converges after normalization to the Lebesgue measure on $[0,1]$. We finally analyze the vertex connectivity (i.e. the minimal number of vertices whose removal disconnects the graph) of random connected cographs, and show that this statistics converges in distribution without renormalization. Unlike for the graphon limit and for the degree of a random vertex, the limiting distribution is different in the labeled and unlabeled settings. Our proofs rely on the classical encoding of cographs via cotrees. We then use mainly combinatorial arguments, including the symbolic method and singularity analysis. 36 pages, 6 figures; v3 includes a new reference to Diaconis-Holmes-Janson (arXiv:0908.2448) for the continuity of the degree distribution for graphons |
| وصف الملف: | Bouvel_RandomCographs2021.pdf - application/pdf |
| اللغة: | English |
| تدمد: | 1042-9832 1098-2418 |
| URL الوصول: | https://explore.openaire.eu/search/publication?articleId=doi_dedup___::59b81b8f873e6fe19ab3113b9afe6aa7 https://www.zora.uzh.ch/id/eprint/205396/ |
| حقوق: | OPEN |
| رقم الأكسشن: | edsair.doi.dedup.....59b81b8f873e6fe19ab3113b9afe6aa7 |
| قاعدة البيانات: | OpenAIRE |
| تدمد: | 10429832 10982418 |
|---|