Densidade de Ramsey Graphs

8

Suponha que tenhamos um gráfico com vértices que não contém nem um clique do tamanho nem um conjunto independente de tamanho (por exemplo, satisfaz essa propriedade com alta probabilidade ) É verdade que o número de arestas de é pelo menos , ou seja, não pode ser muito escasso?Gn3registro(n)3registro(n)G(n,0,5)Gn2/100

De um modo mais geral, gostaria de saber se esses gráficos têm algum tipo de propriedades pseudo-aleatórias.

Igor Shinkar
fonte

Respostas:

3

A resposta para sua pergunta é sim. É o resultado de Erdős e Szemerédi de 1972 . Sabemos um pouco, mas não zero, das propriedades pseudo-aleatórias dos gráficos de Ramsey. Por exemplo, sabemos que muitos tipos diferentes de subgráficos induzidos aparecem nesse gráfico. Veja, por exemplo, um artigo de Alon-Balogh-Kostochka-Samotij e referências nele.

Boris Bukh
fonte
1
registron