Talk:Erdős–Hajnal conjecture

Latest comment: 10 years ago by Szsmr in topic Omega

Omega

edit

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   to  . All the sources I looked at have it without the  . (They also use   in place of   but that's just an unimportant change of notation.) The existence of   for which it's   is equivalent to the existence of a (possibly different)   for which it's  , 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   for which it's  . Leaving out the Omega gives the wrong value, because then the limit on   could well set by what happens for small   rather than only by what happens for large  . For instance, if you have a graph family that includes a two-vertex path, then in the   form that one graph forces   regardless of whether it might be bigger for large graphs; the   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)Reply

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)Reply