Isomorphisms between dense random graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909700239392768 |
|---|---|
| author | Surya, Erlang Warnke, Lutz Zhu, Emily |
| author_facet | Surya, Erlang Warnke, Lutz Zhu, Emily |
| contents | We consider two variants of the induced subgraph isomorphism problem for two independent binomial random graphs with constant edge-probabilities p_1,p_2. In particular, (i) we prove a sharp threshold result for the appearance of G_{n,p_1} as an induced subgraph of G_{N,p_2}, (ii) we show two-point concentration of the size of the maximum common induced subgraph of G_{N, p_1} and G_{N,p_2}, and (iii) we show that the number of induced copies of G_{n,p_1} in G_{N,p_2} has an unusual limiting distribution.
These results confirm simulation-based predictions of McCreesh, Prosser, Solnon and Trimble, and resolve several open problems of Chatterjee and Diaconis. The proofs are based on careful refinements of the first and second moment method, using extra twists to (a) take some non-standard behaviors into account, and (b) work around the large variance issues that prevent standard applications of these methods. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2305_04850 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Isomorphisms between dense random graphs Surya, Erlang Warnke, Lutz Zhu, Emily Combinatorics Discrete Mathematics Probability 05C80, 05C60, 60C05 We consider two variants of the induced subgraph isomorphism problem for two independent binomial random graphs with constant edge-probabilities p_1,p_2. In particular, (i) we prove a sharp threshold result for the appearance of G_{n,p_1} as an induced subgraph of G_{N,p_2}, (ii) we show two-point concentration of the size of the maximum common induced subgraph of G_{N, p_1} and G_{N,p_2}, and (iii) we show that the number of induced copies of G_{n,p_1} in G_{N,p_2} has an unusual limiting distribution. These results confirm simulation-based predictions of McCreesh, Prosser, Solnon and Trimble, and resolve several open problems of Chatterjee and Diaconis. The proofs are based on careful refinements of the first and second moment method, using extra twists to (a) take some non-standard behaviors into account, and (b) work around the large variance issues that prevent standard applications of these methods. |
| title | Isomorphisms between dense random graphs |
| topic | Combinatorics Discrete Mathematics Probability 05C80, 05C60, 60C05 |
| url | https://arxiv.org/abs/2305.04850 |