Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2504.21244 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909597585899520 |
|---|---|
| author | Díaz, Josep Hartle, Harrison Moore, Cristopher |
| author_facet | Díaz, Josep Hartle, Harrison Moore, Cristopher |
| contents | In 2013, Bollobás, Mitsche, and Pralat at gave upper and lower bounds for the likely metric dimension of random Erdős-Rényi graphs $G(n,p)$ for a large range of expected degrees $d=pn$. However, their results only apply when $d \ge \log^5 n$, leaving open sparser random graphs with $d < \log^5 n$. Here we provide upper and lower bounds on the likely metric dimension of $G(n,p)$ from just above the connectivity transition, i.e., where $d=pn=c \log n$ for some $c > 1$, up to $d=\log^5 n$. Our lower bound technique is based on an entropic argument which is more general than the use of Suen's inequality by Bollobás, Mitsche, and Pralat, whereas our upper bound is similar to theirs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_21244 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Metric Dimension of Sparse Random Graphs Díaz, Josep Hartle, Harrison Moore, Cristopher Combinatorics Data Structures and Algorithms Social and Information Networks Probability In 2013, Bollobás, Mitsche, and Pralat at gave upper and lower bounds for the likely metric dimension of random Erdős-Rényi graphs $G(n,p)$ for a large range of expected degrees $d=pn$. However, their results only apply when $d \ge \log^5 n$, leaving open sparser random graphs with $d < \log^5 n$. Here we provide upper and lower bounds on the likely metric dimension of $G(n,p)$ from just above the connectivity transition, i.e., where $d=pn=c \log n$ for some $c > 1$, up to $d=\log^5 n$. Our lower bound technique is based on an entropic argument which is more general than the use of Suen's inequality by Bollobás, Mitsche, and Pralat, whereas our upper bound is similar to theirs. |
| title | The Metric Dimension of Sparse Random Graphs |
| topic | Combinatorics Data Structures and Algorithms Social and Information Networks Probability |
| url | https://arxiv.org/abs/2504.21244 |