Dichte von Ramsey-Graphen

Angenommen, wir haben einen Graphen mit n Eckpunkten, der weder eine Clique der Größe 3 log ( n ) noch einen unabhängigen Satz der Größe 3 log ( n ) enthält (zum Beispielerfüllt G ( n , 0,5 ) diese Eigenschaft mit hoher Wahrscheinlichkeit). Stimmt esdass die Anzahl der Kanten von G wenigstens n 2 / 100 ,heißt, es kann nicht zu dünn sein?$G$$n$$3 \log(n)$$3 \log(n)$$G(n,0.5)$$G$$n^2/100$

Ganz allgemein möchte ich wissen, ob solche Graphen irgendeine Art von pseudozufälligen Eigenschaften haben.

Die Antwort auf Ihre Frage lautet ja. Es ist ein Ergebnis von Erdős und Szemerédi aus dem Jahr 1972 . Wir wissen ein wenig, aber nicht Null über pseudozufällige Eigenschaften von Ramsey-Graphen. Zum Beispiel wissen wir, dass in einem solchen Diagramm viele verschiedene Arten von induzierten Untergraphen auftreten. Siehe zum Beispiel ein Papier von Alon-Balogh-Kostochka-Samotij und Referenzen darin.