Dois teoremas do tipo Erdos-Hajnal para pares de ordens proibidas

A célebre conjectura de Erdos-Hajnal afirma que qualquer grafo sem um subgrafo induzido fixo H contém um conjunto homogêneo muito grande. Um análogo direto dessa conjectura não é verdadeiro para hipergrafos. Neste artigo, apresentamos duas variantes naturais desse problema que são válidas para hipergrafos. Mostramos que para todo r ≥ 3, m = m₀(r) e 0 < f ≤ m, se um r-grafo G não contém m vértices abrangendo exatamente f arestas, então G contém conjuntos homogêneos muito maiores do que o que é garantido existir em grafos r gerais. Também provamos que se um 3-grafo G não contém conjuntos homogêneos de tamanho polinomial, então para todo m ≥ 3 existem (m³) valores de f tais que G contém m vértices abrangendo exatamente f arestas. Isso avança uma conjectura de Axenovich, Bradac, Gishboliner, Mubayi e Weber.