Rotating random trees with Skorokhod's $M_1$ topology

Este artigo estende a codificação clássica de árvores $\mathbb R$-medidas para funções excursivas cádlág utilizando a topologia de Skorokhod $M_1$, demonstrando que, ao contrário do caso gaussiano, a rotação de árvores de Bienaymé críticas cujos descendentes pertencem ao domínio de atração de uma lei estável $\alpha$ ($1 < \alpha < 2$) converge para uma árvore$\mathbb R$-específica codificada por um processo de Lévy$\alpha$-estável.

O essencial

Imagine que você tem um grande jardim de árvores. Algumas são árvores "normais" (como as que vemos na natureza), e outras são árvores "binárias" (como as usadas em computadores, onde cada galho se divide em exatamente dois).

Este artigo é sobre uma mágica matemática chamada "Rotação" que transforma uma árvore normal em uma árvore binária, e o que acontece com essas árvores quando elas ficam gigantescas (infinitamente grandes).

Aqui está a explicação simplificada, usando analogias do dia a dia:

1. O Problema: Como medir árvores gigantes?

Os matemáticos adoram transformar árvores em linhas desenhadas em um papel (chamadas de "funções de contorno"). Se você andar ao redor de uma árvore e anotar a altura de cada passo, você cria um mapa que representa a árvore inteira.

• O Desafio: Quando as árvores são pequenas, essas linhas são suaves e contínuas. Mas, quando as árvores são muito grandes e têm uma estrutura caótica (com galhos muito longos e saltos bruscos), as linhas começam a ter "quebras" ou "pulos" (como um gráfico de ações que cai de repente).
• A Solução do Autor: O autor, Antoine Aurillard, criou uma nova maneira de medir essas linhas quebradas. Ele usou uma "régua flexível" chamada Topologia M1 de Skorokhod.
  • Analogia: Imagine que você tem um fio elástico com nós. Se você puxar o fio, os nós se movem. A topologia M1 permite que você estique o tempo para "preencher" os buracos das quebras, transformando uma linha quebrada em uma linha contínua para poder compará-la com outras. Isso é crucial porque as ferramentas antigas (que exigiam linhas perfeitamente lisas) não funcionavam aqui.

2. A Grande Descoberta: O Efeito da Rotação

O autor estuda o que acontece quando aplicamos a "Rotação" em árvores gigantes. A Rotação é uma regra específica que pega uma árvore normal e a reorganiza em uma árvore binária.

O resultado depende de como as árvores crescem (seus "pais" têm muitos filhos ou poucos):

Cenário A: O Crescimento "Normal" (Gaussiano)

Imagine uma árvore onde a maioria dos pais tem cerca de 2 filhos, com pouca variação. É um crescimento estável.

• O que acontece: Quando você aplica a Rotação, a árvore resultante é basicamente a mesma árvore, apenas esticada (como um elástico puxado).
• Analogia: É como pegar uma foto de uma árvore e esticá-la verticalmente. A forma é a mesma, só ficou mais alta. A estrutura fundamental não mudou.

Cenário B: O Crescimento "Caótico" (Estável com $\alpha$ entre 1 e 2)

Agora imagine uma árvore onde alguns pais têm centenas de filhos, enquanto a maioria tem apenas um. É um crescimento explosivo e irregular.

• O que acontece: Aqui, a Rotação faz algo mágico e diferente. A árvore resultante não é apenas uma versão esticada da original. Ela se transforma em uma nova espécie de árvore completamente diferente!
• A Nova Espécie: Essa nova árvore (chamada $T_x$) tem uma geometria estranha. Ela é "binária" (sempre se divide em dois), mas é cheia de "buracos" e saltos.
• A Conexão Secreta: O autor descobriu que essa nova árvore é, na verdade, uma "espinha dorsal" (uma estrutura de suporte) de outra forma geométrica chamada Looptree (uma árvore feita de círculos conectados).
  • Analogia: Pense no Looptree como um colar de contas (círculos). A nova árvore resultante da rotação é como um fio que passa por dentro de todas as contas, conectando-as de uma maneira específica.

3. Por que isso importa?

O autor mostrou que, dependendo da "genética" da árvore (se ela cresce de forma estável ou explosiva), a Rotação pode:

1. Apenas mudar o tamanho (Cenário A).
2. Criar uma nova geometria fundamental (Cenário B).

Isso é importante porque ajuda a entender como estruturas complexas (como redes de internet, estruturas de proteínas ou até o universo em grande escala) se comportam quando mudam de forma.

Resumo da Ópera

• A Ferramenta: O autor inventou uma maneira inteligente de medir árvores com "quebras" usando uma régua flexível (Topologia M1).
• O Experimento: Ele girou árvores gigantes.
• O Resultado: Se a árvore for "calma", a rotação só a estica. Se a árvore for "explosiva", a rotação a transforma em uma nova forma geométrica fascinante, que é a espinha de um colar de círculos.

É como descobrir que, ao girar um cubo de gelo, ele derrete e vira água (normal), mas se girar um cubo de gelo feito de fumaça, ele vira uma nuvem com uma forma totalmente nova e imprevisível.

Resumo técnico

Resumo Técnico: Rotação de Árvores Aleatórias com a Topologia M1 de Skorokhod

1. Problema e Motivação

O artigo aborda a codificação e o estudo das propriedades geométricas de árvores aleatórias (especificamente árvores de Bienaymé-Galton-Watson condicionadas a ter $n$ vértices) através de funções reais.

• Contexto Clássico: Tradicionalmente, árvores são codificadas por funções contínuas (como o processo de contorno ou a caminhada de Łukasiewicz). A convergência dessas funções, sob a topologia uniforme ou a topologia $J1$ de Skorokhod, implica a convergência das árvores na topologia Gromov-Hausdorff-Prokhorov (GHP).
• O Desafio: O autor investiga o efeito da correspondência de rotação (uma bijeção entre árvores planas e árvores binárias planas) em árvores críticas de grande escala.
  • No caso Gaussiano (variação finita), sabe-se que a rotação atua essencialmente como uma dilatação.
  • No caso de leis estáveis com índice $\alpha \in (1, 2)$ (variação infinita), a rotação produz um limite de escala qualitativamente diferente, gerando uma nova família de árvores aleatórias.
• A Dificuldade Técnica: Os processos de codificação das árvores rotacionadas no regime $\alpha < 2$ tornam-se funções cádlàg (contínuas à direita com limites à esquerda) com descontinuidades macroscópicas. A topologia $J1$ de Skorokhod é inadequada para lidar com a convergência desses processos quando há "saltos não coincidentes" entre os processos discretos e seus limites. É necessária uma topologia mais fraca, a topologia $M1$ de Skorokhod, que permite a convergência de funções com saltos através de representações paramétricas.

2. Metodologia

O trabalho desenvolve uma extensão teórica e aplica-a a um problema combinatório específico:

A. Extensão Teórica: Codificação via Topologia M1

• Representações Paramétricas: O autor utiliza o conceito de representações paramétricas (introduzido por Skorokhod) para definir árvores R (R-trees) a partir de funções de excitação cádlàg ($x \in D([0,1], \mathbb{R}_+)$).
  • Uma representação paramétrica preenche as descontinuidades da função com segmentos verticais, criando uma curva contínua no gráfico completado.
• Continuidade: O autor prova que o mapeamento de uma função cádlàg $x$ para a árvore R codificada $T_x$ (e sua medida associada $\mu_x$) é contínuo em relação à topologia $M1$ no espaço de funções e à topologia Gromov-Hausdorff-Prokhorov (GHP) no espaço de árvores.
  • Proposição 1.1: $d_{GH}(T_x, T_y) \leq 2 d_{M1}(x, y)$.
  • Proposição 1.2: O mapeamento para árvores medidas é contínuo.
• Implicação: Isso permite obter limites de escala para árvores estudando a convergência fraca de seus processos de codificação na topologia $M1$, mesmo quando os limites são descontínuos.

B. Análise Combinatória da Rotação

• Definição de Rotação (Rot): Uma bijeção recursiva que transforma uma árvore plana em uma árvore binária.
• Subárvore Interna: O autor define uma subárvore interna $(Rot\ T)^\circ$ que captura a estrutura espinhal da árvore rotacionada.
• Relações Combinatórias: Estabelece-se uma ligação entre a altura dos vértices rotacionados e os processos de codificação da árvore original ($T_n$) e sua versão espelhada ($T_n^\div$).
  • Utiliza-se a transformação de espelho para trocar "esquerda" e "direita", permitindo expressar a altura da árvore rotacionada em termos da caminhada de Łukasiewicz da árvore original.
• Lemas de Controle M1: O autor prova que, embora os processos discretos (como a caminhada de Łukasiewicz da árvore rotacionada) tenham saltos de tamanho 1, seus limites escalados convergem para funções descontínuas na topologia $M1$. Isso é feito construindo representações paramétricas específicas que alinham os saltos macroscópicos.

3. Principais Contribuições e Resultados

A. Teorema de Convergência Conjunta (Teorema 1.3 e 5.4)
O resultado central descreve o limite de escala conjunto de uma árvore crítica $T_n$ e sua versão rotacionada $Rot\ T_n$:

1. Caso Gaussiano ($\alpha = 2$, variância $\sigma^2 < \infty$):

   • A rotação atua como uma dilatação.
   • $(\frac{1}{\sqrt{n}}T_n, \frac{1}{\sqrt{n}}Rot\ T_n) \xrightarrow{d} (\frac{2}{\sigma}T_e, \frac{2+\sigma^2}{\sigma}T_e)$, onde $T_e$ é a Árvore Aleatória Contínua Browniana (Brownian CRT).
   • A estrutura geométrica é preservada, apenas a escala muda.

2. Caso Estável ($\alpha \in (1, 2)$, variância infinita):

   • A rotação altera a geometria da árvore, não apenas a escala.
   • O limite de $T_n$ é a Árvore Estável $T_h$ (codificada por uma excitação contínua $h$).
   • O limite de $Rot\ T_n$ é uma nova árvore $T_x$ (codificada por uma excitação cádlàg $x$ de um processo de Lévy $\alpha$-estável espectralmente positivo).
   • A convergência ocorre na topologia GHP:
     $$\left( \frac{\ell(n)}{n^{1-1/\alpha}} T_n, \frac{1}{\ell(n)n^{1/\alpha}} Rot\ T_n \right) \xrightarrow{d} (T_h, T_x)$$
   • Aqui, $T_x$ e $T_h$ são não isométricos.

B. Propriedades Geométricas de $T_x$

• Dimensão de Hausdorff: O autor prova que $\dim_H(T_x) = \alpha$, enquanto para a árvore estável clássica $T_h$, $\dim_H(T_h) = \alpha/(\alpha-1)$. Isso confirma que a rotação altera a dimensão fractal no caso $\alpha < 2$.
• Estrutura Binária: $T_x$ é quase certamente uma árvore binária (grau dos vértices $\in \{1, 2, 3\}$), diferentemente de $T_h$ que possui vértices de grau infinito.
• Relação com Looptrees: $T_x$ pode ser vista como uma "árvore R de suporte" (spanning R-tree) do looptree estável $L_x$ (introduzido por Curien & Kortchemski). Existe uma projeção Lipschitziana $p: T_x \to L_x$ que é injetiva exceto nos pontos de descontinuidade da função codificadora.

C. Co-rotação (Tor)

• O autor introduz a "co-rotação" ($Tor$), uma transformação simétrica à rotação.
• Curiosamente, enquanto $Rot\ T_n$ e $Tor\ T_n$ têm o mesmo limite de distribuição de árvores, seus processos de caminhada de Łukasiewicz comportam-se de forma oposta:
  • Para $Rot\ T_n$, a caminhada converge para uma função contínua ($h$).
  • Para $Tor\ T_n$, a caminhada converge para a mesma função descontínua que a árvore original ($x$).
  • Isso ilustra que a topologia $M1$ é essencial para distinguir comportamentos que a topologia uniforme ou $J1$ não capturariam adequadamente.

4. Significado e Impacto

• Generalização da Codificação de Árvores: O trabalho amplia significativamente o escopo da teoria de limites de escala de árvores, permitindo o uso de funções descontínuas (cádlàg) como codificadores válidos, desde que se utilize a topologia $M1$.
• Resolução de um Problema Aberto: Resolve a questão do comportamento assintótico da rotação em árvores com variância infinita, mostrando que a dilatação observada no caso Gaussiano não se generaliza para o caso estável.
• Conexão entre Estruturas Discretas e Contínuas: Estabelece uma ponte rigorosa entre a rotação de árvores discretas e a geometria de looptrees e árvores R descontínuas, fornecendo uma nova perspectiva sobre a estrutura fractal desses objetos.
• Ferramentas Analíticas: A demonstração de que a topologia $M1$ é suficiente para garantir a convergência de árvores medidas (Proposição 1.2) é uma ferramenta poderosa para futuros estudos em probabilidade e física estatística envolvendo estruturas aleatórias descontínuas.

Em suma, o artigo demonstra que a rotação de árvores aleatórias críticas com lei de cauda pesada ($\alpha < 2$) não é apenas uma mudança de escala, mas uma transformação geométrica profunda que gera uma nova classe de objetos contínuos, acessíveis apenas através da análise cuidadosa das representações paramétricas na topologia de Skorokhod.