Graph classes with few $P_4$'s: Universality and Brownian graphon limits - Institut Polytechnique de Paris Accéder directement au contenu
Pré-Publication, Document De Travail (Preprint/Prepublication) Année : 2023

Graph classes with few $P_4$'s: Universality and Brownian graphon limits

Résumé

We consider large uniform labeled random graphs in different classes with few induced $P_4$ ($P_4$ is the graph consisting of a single line of $4$ vertices), which generalize the case of cographs. Our main result is the convergence to a Brownian limit object in the space of graphons. We also obtain an equivalent of the number of graphs of size $n$ in the different classes. Finally we estimate the expected number of induced graphs isomorphic to a fixed graph $H$ for a large variety of graphs $H$. Our proofs rely on tree encoding of graphs. We then use mainly combinatorial arguments, including the symbolic method and singularity analysis.
Fichier principal
Vignette du fichier
main.pdf (974.77 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03956705 , version 1 (26-01-2023)
hal-03956705 , version 2 (17-02-2023)

Identifiants

  • HAL Id : hal-03956705 , version 1

Citer

Théo Lenoir. Graph classes with few $P_4$'s: Universality and Brownian graphon limits. 2023. ⟨hal-03956705v1⟩
27 Consultations
26 Téléchargements

Partager

Gmail Facebook X LinkedIn More