Connectivity in bridge-addable graph classes: the mcdiarmid-steger-welsh conjecture
Notice bibliographique
Résumé
The study of typical properties of random graphs is of particular importance for the theoretical analysis of complex networks. In this field, many models of randomness (such as Erdoos-Renyi or random planar graphs, preferential attachment models) have been successfully analysed thanks to the fact that their underlying structure enables one to perform explicit computations of some observables. Another approach, pioneered by McDiarmid, Steger and Welsh (2005) is to consider graphs taken uniformly from an abstract graph class, assuming only some global property of the class but without fully specifying it. Despite the fact that exact computations are no longer possible, results obtained in this setup are arguably very robust, since they apply universally for many different models of random graphs.The foundational and most studied problem in this topic is a conjecture of these authors on bridge-addable classes that we prove in this paper. A class of graphs is bridge-addable if any graph obtained by adding an edge between two connected components of a graph in the class, is also in the class. Examples of bridge-addable classes include forests, planar graphs, graphs with bounded tree-width, or graphs excluding any 2-connected minor. We prove that a random graph from a bridge-addable class is connected with probability at least e-1/2 +o(1), when its number of vertices tends to infinity.This lower bound is tight since it is reached for forests. The best previously known constants where e-1, e-0.7983 and e-2/3 proved respectively by McDiarmid, Steger and Welsh, by Balister, Bollobas and Gerke, and by Norin.
Récupéré en direct depuis OpenAlex et désinversé. Les résumés ne sont pas conservés dans cette base de données : les index inversés représentent 8,6 Go des 9,3 Go de texte de la base, et le serveur dispose de 13 Go libres.
Comment cette classification a été obtenuedéplier
Prédiction machine sur la base complète
Imitation des enseignantsNi prévalence calibrée, ni vérité terrain. Validation humaine à venir. Le volet Gemma est une étiquette directe du modèle pour chaque travail de la base, lue sur la notice réduite au titre. Le volet Codex est un classifieur appris des 10 348 étiquettes directes de Codex et calibré sur les taux pondérés de l'échantillon; les champs sans appui suffisant ne portent aucun appel Codex. Le mode candidate est l'union des deux volets; le consensus est leur intersection. Ces sorties portent le statut machine_predicted_unvalidated et ne sont pas des étiquettes humaines.
Scores du classifieur distillé par catégorie (deux têtes)
| Catégorie | Codex | Gemma |
|---|---|---|
| Métarecherche | 0,002 | 0,019 |
| Méta-épidémiologie (sens strict) | 0,001 | 0,001 |
| Méta-épidémiologie (sens large) | 0,001 | 0,001 |
| Bibliométrie | 0,002 | 0,002 |
| Études des sciences et des technologies | 0,002 | 0,004 |
| Communication savante | 0,003 | 0,007 |
| Science ouverte | 0,002 | 0,003 |
| Intégrité de la recherche | 0,002 | 0,004 |
| Charge utile insuffisante (le modèle a refusé de juger) | 0,007 | 0,001 |
Scores machine (provisoires)
Les deux têtes enseignantes du modèle étudiant, lues sur ce travail. Un score ordonne la base pour la relecture; il n'affirme jamais une catégorie, et le statut de validation accompagne chaque rangée tel quel.
Scores de référence d'un modèle non mature (critères de maturité non atteints, 7 itérations). Un score ordonne; il n'affirme jamais une catégorie.
score_only:v0-immature-baseline · tel quel depuis la passe de notation : score_only signifie que le nombre peut ordonner les travaux, et qu'aucune étiquette de catégorie n'en découleClassification
machine, non validéePrédiction automatique; un appel candidat d’une seule source (Gemma direct ou Codex distillé), pas un consensus.
Le détail, modèle par modèle et score par score, se trouve en fin de page sous « Comment cette classification a été obtenue ».