My question is based on the Erdos probabilistic method. I am trying to read from the paper here. The proof of Theorem 1 contains the statement
Since a block sequence is monochromatic with probability $2^{1−k}$, it follows from the linearity of expectation that the expected number of monochromatic k-term quasi-progressions under a random coloring is at most $2N^2(c/2)^k/(k − 1)$.
Essentially as I understand the probablistic argument should run as follows: The probability of a particular event $A$ is $2^{1−k}$. We then conclude that the probability of the occuurence of any such event is bounded above by $2^{1−k}\times$ the number of such possible events. The number of possible events is bounded above as per the previous arguments (according to my understanding) in the paper by $N(N-k+1)c^k/(k − 1)$, and forcing $2N(N-k+1)(c/2)^k/(k − 1)$ to be less then $1$ will give us a bound for $N$ within which if $N$ is chosen the desired event is not guaranteed and hence we have a lower bound.
What I am unclear is about the following:
- The reference to the expected number ?
- Why is $2N(N-k+1)(c/2)^k/(k − 1)$ not used instead of $2N^2(c/2)^k/(k − 1)$ ?
If there is some further clarification needed I will be glad to supply it.
Thanks.