Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Recurso digital |
| Lingua: | |
| Pubblicazione: |
Zenodo
2025
|
| Accesso online: | https://doi.org/10.5281/zenodo.17805741 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
Sommario:
- This paper investigates the fascinating phenomenon of emergent extremality in random graphs, specifically focusing on the existence and characterization of sharp thresholds for optimal expansion properties. Random graphs, particularly those constructed under the ErdH{o}s-Rényi model, exhibit phase transitions where fundamental structural properties emerge abruptly as a critical parameter, such as edge probability, crosses a specific threshold. Here, we delve into how optimal expansion--a highly desirable characteristic in network design, computer science, and statistical physics--manifests within these random structures. Optimal expansion implies that every sufficiently small subset of vertices has a large number of neighbors outside the set, ensuring efficient information flow and robust connectivity. We present theoretical arguments and leverage probabilistic methods to demonstrate that optimal expansion does not gradually improve but rather emerges sharply at a precisely defined threshold. Below this threshold, graphs are almost surely poor expanders; above it, they almost surely possess near-optimal expansion. This research elucidates the critical parameter regimes where highly efficient network structures spontaneously arise in a random setting, offering profound insights into the fundamental limits and capabilities of randomly generated networks.