Percolation through isoperimetry

Nous donnons une condition suffisante sur les propriétés isopérimétriques d’un graphe régulier G de degré croissant d, sous laquelle le sous-graphe aléatoire Gp subit typiquement une transition de phase autour de p=1d, qui ressemble à l’apparition d’une composante géante dans le modèle de graphe aléatoire binomial G(n,p). Nous montrons également que cette condition est optimale. Plus précisément, soit d=ω(1), soit ϵ>0 une constante suffisamment petite, et soit p·d=1+ϵ. Nous montrons que, si C est suffisamment grand et que G est un graphe d-régulier à n sommets dans lequel chaque sous-ensemble S⊆V(G) de taille au plus n2 a un bord d’arêtes de longueur au moins C|S|, alors Gp possède typiquement une unique composante de taille linéaire, dont l’ordre est asymptotiquement y(ϵ)n, où y(ϵ) est la probabilité de survie d’un arbre de Galton–Watson avec une loi de reproduction Po(1+ϵ). Nous donnons également des exemples montrant que ce résultat est optimal à la fois en termes de dépendance en C, et par rapport à l’ordre de la deuxième plus grande composante. Nous considérons également un cadre plus général, où nous ne contrôlons que l’expansion des ensembles de taille maximale k. Dans ce cas, nous montrons que si G est tel que chaque sous-ensemble S⊆V(G) de taille au plus k a un bord d’arêtes d’au moins d|S|, et que p est tel que p·d≥1+ϵ, alors Gp contient typiquement une composante d’ordre Ω(k).