Densidad de gráficos de Ramsey

8

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?solnorte3Iniciar sesión(norte)3Iniciar sesión(norte)sol(norte,0,5)solnorte2/ /100

En términos más generales, me gustaría saber si tales gráficos tienen algún tipo de propiedades pseudoaleatorias.

Igor Shinkar
fuente

Respuestas:

3

La respuesta a tu pregunta es sí. Es el resultado de Erdős y Szemerédi de 1972 . Sabemos un poco, pero no cero, sobre las propiedades pseudoaleatorias de los gráficos de Ramsey. Por ejemplo, sabemos que en este gráfico aparecen muchos tipos diferentes de subgrafías inducidas. Ver, por ejemplo, un artículo de Alon – Balogh – Kostochka – Samotij y referencias en él.

Boris Bukh
fuente
1
Iniciar sesiónnorte