Dense and nondense limits for uniform random intersection graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913229634011136 |
|---|---|
| author | Bassino, Frédérique Bouvel, Mathilde Féray, Valentin Gerin, Lucas Pierrot, Adeline |
| author_facet | Bassino, Frédérique Bouvel, Mathilde Féray, Valentin Gerin, Lucas Pierrot, Adeline |
| contents | We obtain the scaling limits of random graphs drawn uniformly in three families of intersection graphs: permutation graphs, circle graphs, and unit interval graphs. The two first families typically generate dense graphs, in these cases we prove a.s. convergence to an explicit deterministic graphon. Uniform unit interval graphs are nondense and we prove convergence in the sense of Gromov-Prokhorov after normalization of the distances: the limiting object is the interval $[0,1]$ endowed with a random metric defined through a Brownian excursion. Asymptotic results for the number of cliques of size $k$ ($k$ fixed) in a uniform random graph in each of these three families are also given.
In all three cases, an important ingredient of the proof is that, for indecomposable graphs in each class (where the notion of indecomposability depends on the class), the combinatorial object defining the graph (permutation, matching, or intervals) is essentially unique. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_06394 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Dense and nondense limits for uniform random intersection graphs Bassino, Frédérique Bouvel, Mathilde Féray, Valentin Gerin, Lucas Pierrot, Adeline Probability Combinatorics 05C62, 05C80 We obtain the scaling limits of random graphs drawn uniformly in three families of intersection graphs: permutation graphs, circle graphs, and unit interval graphs. The two first families typically generate dense graphs, in these cases we prove a.s. convergence to an explicit deterministic graphon. Uniform unit interval graphs are nondense and we prove convergence in the sense of Gromov-Prokhorov after normalization of the distances: the limiting object is the interval $[0,1]$ endowed with a random metric defined through a Brownian excursion. Asymptotic results for the number of cliques of size $k$ ($k$ fixed) in a uniform random graph in each of these three families are also given. In all three cases, an important ingredient of the proof is that, for indecomposable graphs in each class (where the notion of indecomposability depends on the class), the combinatorial object defining the graph (permutation, matching, or intervals) is essentially unique. |
| title | Dense and nondense limits for uniform random intersection graphs |
| topic | Probability Combinatorics 05C62, 05C80 |
| url | https://arxiv.org/abs/2402.06394 |