A combinatorial approach to phase transitions in random graph isomorphism problems
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916808085209088 |
|---|---|
| author | Diamantidis, Dimitris Konstantopoulos, Takis Yuan, Linglong |
| author_facet | Diamantidis, Dimitris Konstantopoulos, Takis Yuan, Linglong |
| contents | We consider two independent Erdős-Rényi random graphs, with possibly different parameters, and study two isomorphism problems, a graph embedding problem and a common subgraph problem. Under certain conditions on the graph parameters we show a sharp asymptotic phase transition as the graph sizes tend to infinity. This extends known results for the case of uniform Erdős-Rényi random graphs. Our approach is primarily combinatorial, naturally leading to several related problems for further exploration. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_00214 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A combinatorial approach to phase transitions in random graph isomorphism problems Diamantidis, Dimitris Konstantopoulos, Takis Yuan, Linglong Combinatorics Probability 60C05, 05C60, 60F99, 05A19 We consider two independent Erdős-Rényi random graphs, with possibly different parameters, and study two isomorphism problems, a graph embedding problem and a common subgraph problem. Under certain conditions on the graph parameters we show a sharp asymptotic phase transition as the graph sizes tend to infinity. This extends known results for the case of uniform Erdős-Rényi random graphs. Our approach is primarily combinatorial, naturally leading to several related problems for further exploration. |
| title | A combinatorial approach to phase transitions in random graph isomorphism problems |
| topic | Combinatorics Probability 60C05, 05C60, 60F99, 05A19 |
| url | https://arxiv.org/abs/2410.00214 |