Talk:Erdős–Hajnal conjecture

Omega

I probably committed a minor amount of original research, or at least editorialization, in changing the statement of how the size of the clique or independent set grows from $n^{\delta }$ to $\Omega (n^{\delta })$. All the sources I looked at have it without the $\Omega$. (They also use $|V|$ in place of $n$ but that's just an unimportant change of notation.) The existence of $\delta$ for which it's ${}\geq n^{\delta }$ is equivalent to the existence of a (possibly different) $\delta$ for which it's $\Omega (n^{\delta })$, so there is no problem with correctness either way. And usually if you can write something with or without using O- or Omega-notation, it's more precise and therefore preferable to do it without. But in this particular case I feel strongly that the form with the Omega is the correct way to express it. The reason is that, in this problem, we're interested in asymptotic growth rates, so what we really want to know is the largest $\delta$ for which it's $\Omega (n^{\delta })$. Leaving out the Omega gives the wrong value, because then the limit on $\delta$ could well set by what happens for small $n$ rather than only by what happens for large $n$. For instance, if you have a graph family that includes a two-vertex path, then in the $n^{\delta }$ form that one graph forces $\delta \leq \log _{3}2\approx 0.631$ regardless of whether it might be bigger for large graphs; the $\Omega (n^{\delta })$ form is more robust and depends only on the large graphs. Anyway, I'm leaving this note here because I thought it would be helpful to explain, in case someone else sees the discrepancy between the sources and our article and wonders why. —David Eppstein (talk) 07:07, 27 April 2014 (UTC)

Thank you for the help. I was curious about the changes and had not enough time to check, but I appreciate the concise summary. The only comment I could make is possibly a small write-up about their (Erdős and Hajnal) original statement of the problem and why it differs from the source materal other than in this talk section. Szsmr (talk) 08:35, 27 April 2014 (UTC)