Graph classes with few $P_4$'s: Universality and Brownian graphon limits - Institut Polytechnique de Paris Access content directly
Preprints, Working Papers, ... (Preprint) Year : 2023

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

Abstract

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
Origin : Files produced by the author(s)

Dates and versions

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

Identifiers

  • HAL Id : hal-03956705 , version 1

Cite

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

Share

Gmail Facebook X LinkedIn More