Which big-Omega meaning re Ramsey number r(4, t)?

82 Views Asked by At

In https://arxiv.org/pdf/2306.04007.pdf, Mattheus and Verstraete prove that the Ramsey number $r(4,t) = \Omega(t^3/\log^4 t)$ as $t \rightarrow \infty$.

Which of the two incompatible definitions of $\Omega$ is meant there? (See https://en.wikipedia.org/wiki/Big_O_notation for the two definitions.)

1

There are 1 best solutions below

0
On

Even without reading the paper, you can guess they're using the Knuth definition, as the older definition is almost entirely confined to the analytic number theory literature. Going to the paper itself, though, the last sentence in section 4.2 ("The proof of Theorem 1") reads:

...this shows that there exists an absolute constant $c_1 > 0$ such that $r(4, t) \ge c_1 t^3/ \log^4 t$ for all $t \ge 3$, proving Theorem $1$. $\;\square$

Which is, indeed, the Knuth definition of $\Omega$.