What is $\Omega(n)$ ? I've only ever seen it represent the number of prime factors of $n$, counting multiplicity.

ocha wrote: What is $\Omega(n)$ ? I've only ever seen it represent the number of prime factors of $n$, counting multiplicity. Well, I really don't know, because I'm not attending the classes anymore. But I think it wants us to prove a lower bound for the Van der Waerden numbers.

Big Omega notation, where $W(k,2)$ is bounded below by a function of growth rate equivalent to $2^\dfrac{k}{2}$.

Let fix $n$. Consider a random coloring of $\{1,2,\ldots,n\}$ with two colors. The probability to exists a monochromatic arithmetic progression with step 1 and of length $k$ is less than $2n2^{-k}$. In the same way the probability to have an arithmetic progression with step $i$, ($ 1 \leq i \leq n$) and of length $k$ is less than $2n2^{-k}$. This means that the probability to exists a monochromatic arithmetic progression of lenght $k$ is less than $2n^2 2^{-k}$. Now, if $2n^2 2^{-k} < 1$, it means that there exists coloring of $\{1,2,\ldots,n\}$ without monochromatic progression of length $k$. $2n^2 2^{-k} < 1$ yeilds $n < 2^{-\frac{1}{2}} 2^{\frac{k}{2}}$, which means $ W(k,2)=\Omega (2^{\frac{k}{2}}) $

There is a neat proof of that bound via the probabilistic method. Here are the steps: Colour the set $\{1, 2, \ldots, n\}$ uniformly at random, using two colours. Consider an arbitrary $k$-arithmetic progression inside $\{1, 2, \ldots, n\}.$ The probability that it is monochromatic is $2 \times \underbrace{\frac 12 \times \cdots \times \frac 12}_{k \text{ times }} = \frac 1{2^{k-1}}.$ If $P(k,n)$ denotes the number of $k$-arithmetic progressions inside $\{1, 2, \ldots, n\},$ prove that $P(k,n) \sim \frac {n^2}{2(k-1)}.$ Hence the probability that we get a monochromatic $k$-arithmetic progression is $\le P(k, n) \times \frac 1{2^{k-1}} \sim \frac {n^2}{(k-1)2^k}.$ Note that if this probability is less than $1,$ then we get the lower bound $W(k, 2) > n.$ To get the result, simply check that with $n = 2^{\frac k2},$ the above probability is indeed eventually less than $1.$ Two remarks: 1) An extensive survey on lower bounds on the van der Waerden number $W(k,2)$ is Lower Bounds on van der Waerden Numbers: Randomized- and Deterministic-Constructive by W. Gasarch and B. Haeupler. In particular, the above approach is essentially the one originally used by Erdős and Rado. 2) It can be used, mutatis mutandis, to get a similar lower bound on $W(k,r)$ (that is, for an $r$-colouring of the set $\{1, 2, \ldots, n \}$). EDIT: beaten by a somewhat long shot by dgrozev, oh well.

@mathmanman: Ok, perhaps you don't know the exact meaning of the English idiom "Long shot". I just gave a straitforward answer to the OP. I knew, it was the Erdos approach, and there was a lot of history behind it. But, the fact I didn't make an historic retrospection didn't make it a long shot! Btw, do you know the expression "To beat around the bush"?