Duality in inhomogeneous random graphs, and the cut metric
The classical random graph model $G(n,\lambda/n)$ satisfies a `duality principle', in that removing the giant component from a supercritical instance of the model leaves (essentially) a subcritical instance. Such principles have been proved for various models; they are useful since it is often...
| Main Authors: | , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
2009
|
| _version_ | 1826266226570035200 |
|---|---|
| author | Janson, S Riordan, O |
| author_facet | Janson, S Riordan, O |
| author_sort | Janson, S |
| collection | OXFORD |
| description | The classical random graph model $G(n,\lambda/n)$ satisfies a `duality principle', in that removing the giant component from a supercritical instance of the model leaves (essentially) a subcritical instance. Such principles have been proved for various models; they are useful since it is often much easier to study the subcritical model than to directly study small components in the supercritical model. Here we prove a duality principle of this type for a very general class of random graphs with independence between the edges, defined by convergence of the matrices of edge probabilities in the cut metric. |
| first_indexed | 2024-03-06T20:35:42Z |
| format | Journal article |
| id | oxford-uuid:328b9362-70b6-4e3f-a68b-f046e559a10f |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T20:35:42Z |
| publishDate | 2009 |
| record_format | dspace |
| spelling | oxford-uuid:328b9362-70b6-4e3f-a68b-f046e559a10f2022-03-26T13:14:47ZDuality in inhomogeneous random graphs, and the cut metricJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:328b9362-70b6-4e3f-a68b-f046e559a10fEnglishSymplectic Elements at Oxford2009Janson, SRiordan, OThe classical random graph model $G(n,\lambda/n)$ satisfies a `duality principle', in that removing the giant component from a supercritical instance of the model leaves (essentially) a subcritical instance. Such principles have been proved for various models; they are useful since it is often much easier to study the subcritical model than to directly study small components in the supercritical model. Here we prove a duality principle of this type for a very general class of random graphs with independence between the edges, defined by convergence of the matrices of edge probabilities in the cut metric. |
| spellingShingle | Janson, S Riordan, O Duality in inhomogeneous random graphs, and the cut metric |
| title | Duality in inhomogeneous random graphs, and the cut metric |
| title_full | Duality in inhomogeneous random graphs, and the cut metric |
| title_fullStr | Duality in inhomogeneous random graphs, and the cut metric |
| title_full_unstemmed | Duality in inhomogeneous random graphs, and the cut metric |
| title_short | Duality in inhomogeneous random graphs, and the cut metric |
| title_sort | duality in inhomogeneous random graphs and the cut metric |
| work_keys_str_mv | AT jansons dualityininhomogeneousrandomgraphsandthecutmetric AT riordano dualityininhomogeneousrandomgraphsandthecutmetric |