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

Percolación Catalana

Información Básica

  • ID del Artículo: 2404.19583
  • Título: Catalan percolation
  • Autores: Eleanor Archer, Ivailo Hartarsky, Brett Kolesnik, Sam Olesker-Taylor, Bruno Schapira, Daniel Valesin
  • Clasificación: math.PR (Teoría de Probabilidades), math.CO (Matemática Combinatoria)
  • Fecha de Publicación: Abril de 2024 (arXiv v2: 24 de abril de 2025)
  • Enlace del Artículo: https://arxiv.org/abs/2404.19583

Resumen

La percolación Catalana es un modelo de percolación único: en el conjunto de enteros Z\mathbb{Z}, todos los bordes de vecinos más cercanos {i,i+1}\{i,i+1\} se ocupan inicialmente, mientras que otros bordes se abren con probabilidad pp de forma independiente. Un borde abierto {i,j}\{i,j\} se ocupa si y solo si existe algún par de bordes {i,k}\{i,k\} y {k,j}\{k,j\} (con i<k<ji<k<j) que estén ambos ocupados. Este artículo demuestra que el valor crítico pcp_c se encuentra estrictamente entre el valor crítico de la percolación de red orientada pcop_c^o y la tasa de crecimiento Catalana 1/41/4. Los resultados principales muestran que los parámetros críticos de modelos de percolación orientada mejorados con dependencias de rango infinito no decrecientes son estrictamente menores que los del modelo clásico. El método de prueba evita el refuerzo de Aizenman-Grimmett tradicional y las desigualdades diferenciales, utilizando en su lugar la teoría de redes estiradas y los resultados de Russo-Seymour-Welsh para percolación orientada.

Antecedentes de Investigación y Motivación

Definición del Problema

El problema central de la investigación en percolación Catalana es: determinar el rango exacto de la probabilidad crítica pcp_c que produce conectividad de largo alcance. Este modelo fue introducido por Gravner y Kolesnik en el contexto de percolación bootstrap en grafos contaminados, combinando:

  • Percolación Bootstrap: autómata celular monótono que simula la propagación de "infección" en redes
  • Percolación Orientada: proceso de percolación con dirección temporal
  • Conteo Combinatorio: estrechamente relacionado con números de Catalan y estructuras de árboles binarios

Importancia

  1. Significado Teórico: Este modelo exhibe el comportamiento de transición de fase en sistemas de percolación con fuertes dependencias de largo alcance, llenando el vacío teórico entre percolación clásica independiente y sistemas completamente dependientes
  2. Aplicaciones en Redes Sociales: El cierre triádico juega un papel importante en redes sociales; la percolación Catalana puede modelar la interacción entre "fuerza de relación" y "censura"
  3. Complejidad Computacional: Desde una perspectiva combinatoria, pcp_c es el umbral de probabilidad crítica al calcular aleatoriamente productos con paréntesis

Limitaciones de Métodos Existentes

Los límites conocidos son: 14≤pc≤pco\frac{1}{4} \leq p_c \leq p_c^o donde pco∈[0.6967,0.7491]p_c^o \in [0.6967, 0.7491] es el valor crítico de percolación de red orientada en Z2\mathbb{Z}^2.

Origen del límite inferior: unión simple de números de Catalan, utilizando Cn≤4nC_n \leq 4^nOrigen del límite superior: restricción de la dinámica a procesos de "nucleación", correspondiente a percolación de red orientada

Sin embargo, ambos límites son poco ajustados, con una brecha enorme.

Motivación de la Investigación

  1. Prueba de Desigualdades Estrictas: Probar desigualdades estrictas de parámetros críticos en modelos con dependencias de largo alcance no decrecientes es un problema extremadamente desafiante
  2. Innovación Metodológica: Los métodos tradicionales de refuerzo esencial de Aizenman-Grimmett fallan en configuraciones orientadas, requiriendo el desarrollo de nuevas herramientas
  3. Comprensión del Rol de la Dependencia: Cuantificar cómo la dinámica Catalana adicional (relativa a percolación orientada) reduce el umbral crítico

Contribuciones Principales

  1. Teorema Principal (Teorema 1): Prueba la desigualdad estricta 14<pc<pco\frac{1}{4} < p_c < p_c^o
  2. Límites Refinados (Teorema 2):
    • Mejora del límite inferior: pc−>0.254>1/4p_c^- > 0.254 > 1/4
    • Mejora del límite superior: pc+≤pcop_c^+ \leq p_c^o (mejorado desde 1−2−321-2^{-32})
    • Desigualdad estricta: pc<pcop_c < p_c^o
  3. Innovación Metodológica:
    • Propone un método de prueba de desigualdades estrictas que no utiliza desigualdades diferenciales de Aizenman-Grimmett
    • Introduce un modelo de percolación orientada mejorado (con bordes de longitud 2), estableciendo relaciones de dominación con percolación Catalana
    • Aplica redes estiradas y teoría reciente de percolación orientada en ambientes aleatorios
  4. Herramientas Teóricas: Combina la teoría de defectos geométricos de percolación orientada de Hilário et al. con la teoría crítica de Russo-Seymour-Welsh de Duminil-Copin et al.

Explicación Detallada de Métodos

Definición de la Tarea

Entrada: Parámetro p∈[0,1]p \in [0,1], bordes {i,j}⊂Z\{i,j\} \subset \mathbb{Z} se abren independientemente con probabilidad pp (con j≥i+2j \geq i+2)

Reglas de Dinámica:

  • Inicial: todos los {i,i+1}\{i,i+1\} se ocupan
  • Recursivo: un borde abierto {i,j}\{i,j\} se ocupa si y solo si ∃k∈(i,j)\exists k \in (i,j) tal que {i,k}\{i,k\} y {k,j}\{k,j\} estén ambos ocupados

Objetivo: Determinar el valor crítico pc=inf⁡{p:lim inf⁡n→∞ϕn(p)>0}p_c = \inf\{p : \liminf_{n\to\infty} \phi_n(p) > 0\} donde ϕn(p)=Pp({0,n} estaˊ ocupado∣{0,n} estaˊ abierto)\phi_n(p) = \mathbb{P}_p(\{0,n\}\text{ está ocupado}|\{0,n\}\text{ está abierto})

Representación Gráfica y Conexión con Árboles Binarios

Observación Clave: Mapear cada borde {i,j}\{i,j\} a un nodo plano v(i,j)=((i+j)/2,j−i−1)v(i,j) = ((i+j)/2, j-i-1)

El borde {0,n}\{0,n\} se ocupa si y solo si existe un árbol binario enraizado en v(0,n)v(0,n) con hojas en v(0,1),…,v(n−1,n)v(0,1),\ldots,v(n-1,n). Esto establece la conexión con números de Catalan Cn=1n+1(2nn)C_n = \frac{1}{n+1}\binom{2n}{n}.

Método de Límite Inferior: Análisis de Funciones Generatrices (Sección 3)

Estrategia Básica

Utilizar la relación de recurrencia: θ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) donde θn(p)=pϕn(p)\theta_n(p) = p\phi_n(p) es la probabilidad de que el borde {0,n}\{0,n\} esté ocupado.

Mejora Iterativa

Definir la secuencia de límites superiores {an(n0)(p)}\{a_n^{(n_0)}(p)\}:

undefined