Dos teoremas de tipo Erdos-Hajnal para pares de tamaño de orden prohibido

La célebre conjetura de Erdos-Hajnal dice que cualquier grafo sin un subgrafo inducido H fijo contiene un conjunto homogéneo muy grande. Un análogo directo de esta conjetura no es cierto para hipergrafos. En este artículo presentamos dos variantes naturales de este problema que sí se sostienen para hipergrafos. Mostramos que para cada r ≥ 3, m = m₀(r) y 0 ≤ f ≤ m, si un r-grafo G no contiene m vértices que abarcan exactamente f aristas, entonces G contiene conjuntos homogéneos mucho más grandes de lo que se garantiza que existan en los r-grafos en general. También demostramos que si un 3-grafo G no contiene conjuntos homogéneos de tamaño polinómico, entonces para cada m ≥ 3 hay (m³) valores de f tales que G contiene m vértices que abarcan exactamente f aristas. Esto avanza en una conjetura de Axenovich, Bradac, Gishboliner, Mubayi y Weber.