Um teorema do limite central para o número de emparelhamento de um grafo aleatório esparso

Em 1981, Karp e Sipser provaram uma lei dos grandes números para o número de emparelhamento de um grafo aleatório esparso de Erdos-R\'enyi, em um artigo influente que pioneirou o chamado método de equações diferenciais para análise de processos de grafos aleatórios. Fortalecendo este resultado clássico e respondendo a uma pergunta de Aronson, Frieze e Pittel, provamos um teorema do limite central no mesmo contexto: as flutuações no número de emparelhamento de um grafo aleatório esparso são assintoticamente gaussianas. Nossa nova contribuição é provar este teorema do limite central nos regimes subcrítico e crítico, de acordo com uma célebre transição de fase algorítmica inicialmente observada por Karp e Sipser. De fato, no regime supercrítico, um teorema do limite central foi recentemente provado na tese de doutorado de Kreaci\'c, utilizando uma generalização estocástica do método de equações diferenciais (comparando o chamado processo de Karp-Sipser a um sistema de equações diferenciais estocásticas). Nossa prova se baseia nesses métodos e introduz novas técnicas para lidar com certas degenerescências presentes nos casos subcríticos e críticos. Curiosamente, nossas novas técnicas levam a um resultado não construtivo: somos capazes de caracterizar as flutuações do número de emparelhamento ao redor de sua média, apesar de essas flutuações serem muito menores do que os termos de erro em nossas melhores estimativas da média. Também provamos um teorema do limite central para a classificação da matriz de adjacência de um grafo aleatório esparso.