2025-11-18T12:01:13.585604

Catalan percolation

Archer, Hartarsky, Kolesnik et al.
In Catalan percolation, all nearest-neighbor edges $\{i,i+1\}$ along $\mathbb Z$ are initially occupied, and all other edges are open independently with probability $p$. Open edges $\{i,j\}$ are occupied if some pair of edges $\{i,k\}$ and $\{k,j\}$, with $i<k<j$, become occupied. This model was introduced by Gravner and the third author, in the context of polluted graph bootstrap percolation. We prove that the critical $p_{\mathrm c}$ is strictly between that of oriented site percolation on $\mathbb Z^2$ and the Catalan growth rate $1/4$. Our main result shows that an enhanced oriented percolation model, with non-decaying infinite-range dependency, has a strictly smaller critical parameter than the classical model. This is reminiscent of the work of Duminil-Copin, Hilário, Kozma and Sidoravicius on brochette percolation. Our proof differs, however, in that we do not use Aizenman--Grimmett enhancements or differential inequalities. Two key ingredients are the work of Hilário, Sá, Sanchis and Teixeira on stretched lattices, and the Russo--Seymour--Welsh result for oriented percolation by Duminil-Copin, Tassion and Teixeira.
academic

Percolation catalane

Informations de base

  • ID de l'article : 2404.19583
  • Titre : Catalan percolation
  • Auteurs : Eleanor Archer, Ivailo Hartarsky, Brett Kolesnik, Sam Olesker-Taylor, Bruno Schapira, Daniel Valesin
  • Classification : math.PR (Théorie des probabilités), math.CO (Mathématiques combinatoires)
  • Date de publication : Avril 2024 (arXiv v2 : 24 avril 2025)
  • Lien de l'article : https://arxiv.org/abs/2404.19583

Résumé

La percolation catalane est un modèle de percolation unique : sur l'ensemble des entiers Z\mathbb{Z}, tous les arêtes de plus proches voisins {i,i+1}\{i,i+1\} sont initialement occupées, tandis que les autres arêtes s'ouvrent indépendamment avec probabilité pp. Une arête ouverte {i,j}\{i,j\} devient occupée si et seulement s'il existe une paire d'arêtes {i,k}\{i,k\} et {k,j}\{k,j\} (avec i<k<ji<k<j) qui sont toutes deux occupées. Cet article démontre que la valeur critique pcp_c se situe strictement entre la valeur critique de la percolation orientée sur réseau pcop_c^o et le taux de croissance catalane 1/41/4. Les résultats principaux montrent que le paramètre critique des modèles de percolation orientée améliorée avec dépendances à longue portée non décroissantes est strictement inférieur au modèle classique. La méthode de preuve évite l'amélioration classique d'Aizenman-Grimmett et les inégalités différentielles, en utilisant plutôt la théorie des treillis étirés et les résultats de Russo-Seymour-Welsh pour la percolation orientée.

Contexte et motivation de la recherche

Définition du problème

La question centrale de la recherche en percolation catalane est : déterminer la plage exacte de la probabilité critique pcp_c qui provoque l'apparition de la connectivité à longue portée. Ce modèle a été introduit par Gravner et Kolesnik dans le contexte de la percolation bootstrap sur graphes pollués, combinant :

  • Percolation bootstrap : automate cellulaire monotone simulant la propagation d'une « infection » dans un réseau
  • Percolation orientée : processus de percolation avec une direction temporelle
  • Énumération combinatoire : étroitement liée aux nombres de Catalan et aux structures d'arbres binaires

Importance

  1. Signification théorique : Ce modèle démontre le comportement de transition de phase dans les systèmes de percolation avec fortes dépendances à longue portée, comblant le vide théorique entre la percolation classique indépendante et les systèmes complètement dépendants
  2. Applications aux réseaux sociaux : La fermeture triadique joue un rôle important dans les réseaux sociaux. La percolation catalane peut modéliser l'interaction entre « force des relations » et « censure »
  3. Complexité computationnelle : D'un point de vue combinatoire, pcp_c est le seuil de probabilité critique pour le calcul aléatoire de produits entre parenthèses

Limitations des méthodes existantes

Les bornes connues sont : 14≤pc≤pco\frac{1}{4} \leq p_c \leq p_c^o où pco∈[0.6967,0.7491]p_c^o \in [0.6967, 0.7491] est la valeur critique de la percolation orientée sur réseau sur Z2\mathbb{Z}^2.

Source de la borne inférieure : Union bound simple des nombres de Catalan, utilisant Cn≤4nC_n \leq 4^nSource de la borne supérieure : Limitation de la dynamique à un processus de « nucléation », correspondant à la percolation orientée sur réseau

Cependant, ces deux bornes ne sont pas serrées, avec un écart énorme.

Motivation de la recherche

  1. Preuve d'inégalités strictes : Prouver des inégalités strictes pour les paramètres critiques dans les modèles avec dépendances à longue portée non décroissantes est un problème extrêmement difficile
  2. Innovation méthodologique : Les méthodes classiques d'amélioration essentielle d'Aizenman-Grimmett échouent dans le cadre orienté, nécessitant le développement de nouveaux outils
  3. Compréhension du rôle de la dépendance : Quantifier comment la dynamique catalane supplémentaire (par rapport à la percolation orientée) réduit le seuil critique

Contributions principales

  1. Théorème principal (Théorème 1) : Preuve de l'inégalité stricte 14<pc<pco\frac{1}{4} < p_c < p_c^o
  2. Bornes raffinées (Théorème 2) :
    • Amélioration de la borne inférieure : pc−>0.254>1/4p_c^- > 0.254 > 1/4
    • Amélioration de la borne supérieure : pc+≤pcop_c^+ \leq p_c^o (amélioré à partir de 1−2−321-2^{-32})
    • Inégalité stricte : pc<pcop_c < p_c^o
  3. Innovation méthodologique :
    • Proposition d'une méthode de preuve d'inégalités strictes sans utiliser les inégalités différentielles d'Aizenman-Grimmett
    • Introduction d'un modèle de percolation orientée amélioré (avec arêtes de longueur 2), établissant une relation de domination avec la percolation catalane
    • Application de la théorie des treillis étirés et des résultats récents de la percolation orientée en environnement aléatoire
  4. Outils théoriques : Combinaison de la théorie de la percolation orientée avec défauts géométriques de Hilário et al. avec la théorie critique de Russo-Seymour-Welsh de Duminil-Copin et al.

Explication détaillée de la méthode

Définition de la tâche

Entrée : Paramètre p∈[0,1]p \in [0,1], arêtes {i,j}⊂Z\{i,j\} \subset \mathbb{Z} s'ouvrent indépendamment avec probabilité pp (avec j≥i+2j \geq i+2)

Règles de dynamique :

  • Initial : Toutes les arêtes {i,i+1}\{i,i+1\} sont occupées
  • Récursif : Une arête ouverte {i,j}\{i,j\} devient occupée si et seulement si ∃k∈(i,j)\exists k \in (i,j) tel que {i,k}\{i,k\} et {k,j}\{k,j\} soient toutes deux occupées

Objectif : Déterminer la valeur critique pc=inf⁡{p:lim inf⁡n→∞ϕn(p)>0}p_c = \inf\{p : \liminf_{n\to\infty} \phi_n(p) > 0\} où ϕn(p)=Pp({0,n} occupeˊe∣{0,n} ouverte)\phi_n(p) = \mathbb{P}_p(\{0,n\}\text{ occupée}|\{0,n\}\text{ ouverte})

Représentation graphique et connexion aux arbres binaires

Observation clé : Mapper chaque arête {i,j}\{i,j\} à un nœud plan v(i,j)=((i+j)/2,j−i−1)v(i,j) = ((i+j)/2, j-i-1)

L'arête {0,n}\{0,n\} est occupée si et seulement s'il existe un arbre binaire enraciné en v(0,n)v(0,n) avec des feuilles en v(0,1),…,v(n−1,n)v(0,1),\ldots,v(n-1,n). Cela établit une connexion avec le nombre de Catalan Cn=1n+1(2nn)C_n = \frac{1}{n+1}\binom{2n}{n}.

Méthode de borne inférieure : Analyse des fonctions génératrices (Section 3)

Stratégie de base

Utilisation de la relation de récurrence : θn(p)≤p∑k=1n−1θk(p)θn−k(p)\theta_n(p) \leq p\sum_{k=1}^{n-1}\theta_k(p)\theta_{n-k}(p) où θn(p)=pϕn(p)\theta_n(p) = p\phi_n(p) est la probabilité que l'arête {0,n}\{0,n\} soit occupée.

Amélioration itérative

Définition de la séquence de bornes supérieures {an(n0)(p)}\{a_n^{(n_0)}(p)\} :

undefined