<p>The answer to your question is yes. It is a <a href="http://www.ams.org/mathscinet-getitem?mr=325446" rel="nofollow">result of Erdős and Szemerédi from 1972</a>. We know a little, but non-zero about pseudo-random properties of Ramsey graphs. For example, we know that many different kinds of induced subgraphs appear in such a graph. See, for example, a paper by <a href="http://www.ams.org/mathscinet-getitem?mr=2507733" rel="nofollow">Alon–Balogh–Kostochka–Samotij</a> and references therein.</p>

CC BY-SA 3.0
2013-05-16T14:29:44.093Z
Alternative link: http://bolyai.hu/~p_erdos/1972-08.pdf  Also, are you sure this result is strong enough?  Theorem 2 seems to be of the right form but the guarantee is only for some constant multiple of $\log n$, not 3.
András Salamon
CC BY-SA 3.0
2013-05-16T14:16:23.447Z
2013-05-16T14:16:23.447Z
Boris Bukh
<p>Suppose we have a graph $G$ with $n$ vertices that contains neither a clique of size $3 \log(n)$ nor an independent set of size $3 \log(n)$ (for example $G(n,0.5)$ satisfies this property with with high probability). Is it true that the number of edges of $G$ is at least $n^2/100$, i.e., it cannot be too sparse?</p>

<p>More generally, I would like to know whether such graphs have some kind of pseudo-random properties.</p>

<graph-theory><ramsey-theory>
Density of Ramsey Graphs
Igor Shinkar
# Density of Ramsey Graphs

(Asked by: username_0 on 2013-05-15)

Suppose we have a graph $G$ with $n$ vertices that contains neither a clique of size $3 \log(n)$ nor an independent set of size $3 \log(n)$ (for example $G(n,0.5)$ satisfies this property with with high probability). Is it true that the number of edges of $G$ is at least $n^2/100$, i.e., it cannot be too sparse?

More generally, I would like to know whether such graphs have some kind of pseudo-random properties.

**Tags:** graph-theory, ramsey-theory

---

## 1 answers

### Answer by username_1 on 2013-05-16. Score: 3 | Accepted answer

The answer to your question is yes. It is a [result of Erdős and Szemerédi from 1972](http://www.ams.org/mathscinet-getitem?mr=325446). We know a little, but non-zero about pseudo-random properties of Ramsey graphs. For example, we know that many different kinds of induced subgraphs appear in such a graph. See, for example, a paper by [Alon–Balogh–Kostochka–Samotij](http://www.ams.org/mathscinet-getitem?mr=2507733) and references therein.

> **Comments:**
> **username_2**: Alternative link: http://bolyai.hu/~p_erdos/1972-08.pdf  Also, are you sure this result is strong enough?  Theorem 2 seems to be of the right form but the guarantee is only for some constant multiple of $\log n$, not 3.  

---

