8
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

The answer to your question is yes. It is a result of Erdős and Szemerédi from 1972. 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 and references therein.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Alternative link: 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. $\endgroup$
    – András Salamon
    May 16, 2013 at 14:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.