The lower tail of triangle counts in sparse random graphs

L’article « The lower tail of triangle counts in sparse random graphs », de Dong Huang et Shuangping Li, étudie la probabilité qu’un graphe aléatoire contienne beaucoup moins de triangles que prévu, ainsi que sa structure typique sous cette contrainte. Ce résumé s’appuie uniquement sur le titre, les informations bibliographiques et le résumé de l’article, déposé sur arXiv le 23 octobre 2026. Le texte intégral n’étant pas accessible en raison des restrictions de licence indiquées, les démonstrations et les formulations techniques précises des résultats ne peuvent pas être détaillées. Les auteurs considèrent le modèle d’Erdős-Rényi \(G(n,p)\), dans lequel chaque arête possible entre \(n\) sommets est présente indépendamment avec une probabilité \(p\). Ils se placent dans un régime clairsemé où \(p\) tend vers zéro tout en restant asymptotiquement beaucoup plus grand que \(n^{-1/2}\). La variable \(T_n\) désigne le nombre de triangles du graphe. Pour une proportion fixée \(\eta \in (0,1)\), l’objectif est d’étudier l’événement \(T_n \leq \eta\,\mathbb{E}[T_n]\). L’étude comporte deux volets : déterminer le taux de grande déviation de cet événement rare, qui décrit sa probabilité à l’échelle exponentielle pertinente, et caractériser la structure typique du graphe conditionné par cet événement. Elle s’inscrit dans un cadre variationnel établi par des travaux antérieurs. Selon le résumé, le taux de grande déviation et la structure conditionnelle sont gouvernés par un problème d’optimisation portant sur des graphons. Ces objets représentent de manière continue les probabilités de connexion et permettent notamment de décrire des structures homogènes ou organisées en blocs. L’apport central annoncé est la résolution de ce problème variationnel pour toutes les valeurs de \(\eta\) comprises entre 0 et 1. Le résultat principal établit que tout minimiseur est soit un graphon constant, soit un graphon en escalier composé de deux blocs de même taille. Dans le premier cas, le graphe conditionné est proche d’un graphe d’Erdős-Rényi, c’est-à-dire d’un modèle homogène. Dans le second, il est proche d’un modèle à blocs stochastiques symétrique à deux groupes. Le déficit de triangles peut donc résulter de deux organisations distinctes : une modification homogène des connexions ou l’apparition d’une structure à deux blocs. Le résumé ne précise toutefois ni les paramètres de connexion, ni le sens mathématique de cette proximité, ni les arguments permettant d’identifier les minimiseurs. Ces deux régimes sont séparés par une transition de phase du premier ordre au seuil \(\eta_* \approx 0{,}009217\). Cette valeur correspond à un nombre de triangles représentant environ \(0{,}9217\,\%\) de l’espérance initiale. Le caractère de premier ordre traduit un changement discontinu entre les structures optimales, plutôt qu’une évolution progressive. Le comportement exact au seuil et les éventuelles modalités de coexistence des minimiseurs ne sont pas précisés dans le résumé. Les auteurs annoncent ainsi résoudre une conjecture de Zhao et un problème ouvert de Janson et Warnke concernant les triangles. Ils proposent une description complète de la queue inférieure du nombre de triangles dans le régime de probabilités considéré. La portée de ces résultats reste limitée à ce cadre asymptotique et à ce motif particulier : le résumé ne permet pas d’en déduire des conclusions pour d’autres densités, d’autres sous-graphes ou des graphes de taille finie.

Quand les triangles se font rares : deux visages des graphes aléatoires

Comment un réseau aléatoire peut-il contenir beaucoup moins de triangles que prévu ? La question semble simple, mais elle cache un choix fondamental : le réseau réduit-il uniformément ses connexions, ou adopte-t-il une organisation différente ? Dans « The lower tail of triangle counts in sparse random graphs », Dong Huang et Shuangping Li étudient ces deux possibilités et annoncent une description complète de leur compétition dans un régime précis de graphes clairsemés.

Déposé sur arXiv le 23 octobre 2026, leur article porte sur un événement rare et sur la structure qui l’accompagne. Cette présentation repose uniquement sur le titre, les informations bibliographiques et le résumé disponibles. Le texte intégral n’étant pas accessible en raison des restrictions de licence indiquées, elle ne détaille ni les démonstrations ni les formulations techniques exactes des résultats.

Un modèle simple, une question difficile

Les auteurs travaillent avec le modèle de graphe aléatoire G(n,p). On considère n sommets, puis chaque paire de sommets est reliée indépendamment avec une probabilité p. Un triangle apparaît lorsque trois sommets sont tous reliés deux à deux. Son existence exige donc la présence de trois arêtes.

Le nombre moyen de triangles est facile à exprimer : il correspond au nombre de groupes de trois sommets, multiplié par p au cube. Pourtant, connaître cette moyenne ne suffit pas à comprendre les fluctuations extrêmes. Les triangles ne sont pas indépendants les uns des autres : plusieurs peuvent partager une même arête. Réduire certaines connexions peut ainsi faire disparaître simultanément de nombreux triangles.

L’étude considère une probabilité p qui tend vers zéro, tout en restant asymptotiquement beaucoup plus grande que l’inverse de la racine carrée de n. Le graphe devient donc clairsemé, mais pas arbitrairement peu connecté. Les conclusions annoncées concernent précisément ce cadre asymptotique.

Mesurer un déficit exceptionnel

Les chercheurs fixent une proportion eta comprise entre zéro et un. Ils s’intéressent à la probabilité que le nombre de triangles soit inférieur ou égal à eta fois sa moyenne. Par exemple, une valeur de 0,1 correspond à un graphe ne contenant pas plus de 10 % du nombre moyen de triangles.

Leur démarche comporte deux volets complémentaires :

• Déterminer le taux de grande déviation, qui décrit la probabilité de cet événement rare à l’échelle exponentielle pertinente.
• Caractériser l’organisation typique du graphe lorsqu’on impose ce déficit de triangles.

La seconde question donne une interprétation concrète à la première. Il ne s’agit pas seulement de savoir à quel point un déficit est improbable, mais de comprendre comment un graphe aléatoire tend à le réaliser.

Les graphons : représenter les organisations possibles

Pour aborder ces questions, les auteurs s’inscrivent dans un cadre variationnel établi par des travaux antérieurs. L’outil central est le graphon : une représentation continue des probabilités de connexion. Cet objet permet de décrire aussi bien une organisation homogène qu’une organisation où plusieurs groupes de sommets possèdent des comportements de connexion distincts.

Le problème consiste à rechercher les organisations optimales sous la contrainte portant sur les triangles. Selon le résumé, ces solutions gouvernent à la fois le taux de grande déviation et la structure du graphe conditionné. L’apport principal annoncé est la résolution de ce problème d’optimisation pour toutes les valeurs de eta entre zéro et un.

Deux structures optimales, et seulement deux types

La solution homogène

Le premier type de minimiseur est un graphon constant. Il décrit une probabilité de connexion uniforme, sans distinction entre groupes de sommets. Dans ce cas, le graphe soumis au déficit de triangles reste proche d’un modèle d’Erdős-Rényi : son organisation conserve un caractère homogène.

La solution à deux blocs

Le second type est un graphon en escalier composé de deux blocs de même taille. Le graphe conditionné est alors proche d’un modèle à blocs stochastiques symétrique à deux groupes. Une organisation collective apparaît : la description des connexions distingue désormais deux ensembles de sommets.

Le résultat annoncé est particulièrement fort : tout minimiseur appartient à l’une de ces deux catégories. Le résumé ne fournit toutefois ni les probabilités de connexion correspondantes ni le sens mathématique exact du mot « proche ». Il ne permet donc pas de reconstruire précisément les modèles conditionnés.

Une transition de phase à un seuil très bas

Les deux régimes sont séparés par une transition de phase du premier ordre, située autour de eta = 0,009217. Ce seuil correspond à environ 0,9217 % du nombre moyen de triangles. L’expression « premier ordre » indique un changement discontinu entre les structures optimales, plutôt qu’une transformation progressive de l’une vers l’autre.

Cette rupture souligne que diminuer le nombre de triangles peut engager des mécanismes structurels distincts. Le résumé ne précise cependant pas le comportement exact au seuil, ni les éventuelles modalités de coexistence des minimiseurs.

Une avancée majeure dans un cadre délimité

Dong Huang et Shuangping Li annoncent ainsi résoudre une conjecture et un problème ouvert concernant les triangles. Leur contribution relie une probabilité extrêmement faible à une classification simple des organisations optimales. Sa portée reste néanmoins délimitée : elle concerne les triangles, le régime asymptotique indiqué et le modèle étudié. Rien dans le résumé ne justifie une extension automatique à d’autres motifs ou à des réseaux de taille finie.