Supongamos que tenemos un gráfico con vértices que no contiene una camarilla de tamaño ni un conjunto independiente de tamaño (por ejemplo, satisface esta propiedad con alta probabilidad ) ¿Es cierto que el número de aristas de es al menos , es decir, no puede ser demasiado escaso?
En términos más generales, me gustaría saber si tales gráficos tienen algún tipo de propiedades pseudoaleatorias.
fuente