Subgrafos ótimos em grafos aleatórios geométricos sem escala

Grafos aleatórios geométricos sem escala são modelos populares para redes que exibem distribuições de graus com caudas pesadas, pequenas características de mundo e alta agregação. Nesses modelos, os vértices têm pesos que causam os graus de cauda pesada e estão inseridos em um espaço métrico de forma que grupos próximos de vértices tendem a se aglomerar. A interação entre os pesos e as posições dos vértices afeta fortemente a estrutura local do grafo aleatório, em particular a ocorrência de padrões de subgrafos, mas as dependências nessas estruturas e pesos tornam a análise difícil. Neste artigo, investigamos contagens de subgrafos usando uma estratégia de divide et impera: primeiro contando o número de subgrafos em classes específicas de vértices; em seguida, computando qual classe fornece a contribuição máxima. Curiosamente, o comportamento de escala de subgrafos induzidos e gerais nesses grafos aleatórios geométricos de cauda pesada está intimamente relacionado à solução de um programa linear misto que também mostra que subgrafos aparecem predominantemente em vértices com alguns graus e interdistâncias prescritos. Finalmente, derivamos assintóticas precisas para árvores e subgrafos Hamiltonianos.