Conjuntos independentes em hipergrafos

Muitos teoremas e conjecturas importantes em combinatória, como o teorema de Szemerédi sobre progressões aritméticas e o Teorema de Erdős–Stone na teoria dos grafos extremais, podem ser formulados como afirmações sobre famílias de conjuntos independentes em certos hipergrafos uniformes. Nos últimos anos, uma tendência importante na área tem sido estender tais resultados clássicos para o chamado ‘contexto aleatório esparso’. Essa linha de pesquisa culminou recentemente nas inovações de Conlon e Gowers e de Schacht, que desenvolveram ferramentas gerais para resolver problemas desse tipo. Embora esses dois artigos tenham resolvido conjuntos de problemas abertos de longa data muito semelhantes, os métodos utilizados são muito diferentes entre si e têm forças e fraquezas diferentes. Neste artigo, fornecemos uma terceira abordagem, completamente diferente, para provar resultados extremos e estruturais em conjuntos aleatórios esparsos que também gera suas contrapartes naturais de ‘contagem’. Damos uma caracterização estrutural dos conjuntos independentes em uma grande classe de hipergrafos uniformes, mostrando que cada conjunto independente é quase contido em um pequeno número de conjuntos relativamente esparsos. A partir disso, derivamos muitos resultados interessantes como consequências bastante diretas desse teorema abstrato. Em particular, provamos a bem conhecida conjectura de Kohayakawa, Łuczak e Rödl, um lema de incorporação probabilística para grafos esparsos. Também fornecemos provas alternativas de muitos dos resultados de Conlon e Gowers e de Schacht, como versões aleatórias esparsas do teorema de Szemerédi, do Teorema de Erdős–Stone e do Teorema de Estabilidade de Erdős–Simonovits, e obtemos suas versões naturais de ‘contagem’, que em alguns casos são consideravelmente mais fortes. Por exemplo, mostramos que, para cada β positivo e inteiro k, há no máximo (β n m) nm conjuntos de tamanho m que não contêm uma progressão aritmética de k termos, desde que m ⩾ C n^(1 - 1 / (k - 1)), onde C é uma constante que depende apenas de β e k. Também obtemos novos resultados, como uma versão esparsa do Teorema de Erdős–Frankl–Rödl sobre o número de grafos livres de H e, como consequência da conjectura KŁR, estendemos um resultado de Rödl e Ruciński sobre propriedades de Ramsey em grafos aleatórios esparsos para o contexto geral e não simétrico.