I'm trying to wrap my head around a proof presented in Rosen's Discrete Mathematics and its Applications that relates to the lower bound for the Ramsey number $R(k,k)$. I'm comfortable with majority of the proof as it is presented (Rosen characterizes a Ramsey number $R(m,n)$ as the number of people attending the smallest party necessary to ensure that there are at least $m$ mutual friends or $n$ mutual enemies in attendance), but there is one step that I'm getting a little hung up on. Rosen writes:
Suppose there are $n$ people at the party. It follows that there are $\binom{n}{k}$ different sets of k people at this party, which we list as $S_1$, $S_2$, . . . , $S_\binom{n}{k}$. Let $E_i$ be the event that all $k$ people in $S_i$ are either mutual friends or mutual enemies. The probability that there are either $k$ mutual friends or $k$ mutual enemies among the $n$ people equal $p\left(\bigcup_{i=1}^\binom{n}{k}E_i\right)$.
My confusion stems from the final sentence of this passage. My initial instinct was that the probability that there are either $k$ mutual friends or $k$ mutual enemies among the $n$ people equals $\sum_{i=1}^\binom{n}{k}p\left(E_i\right)$. If the $E_i$ are pairwise independent, so that $$p\left(E_i\cap E_j\right)=p\left(E_i\right)+p\left(E_j\right)$$ for all pairs of integers $i$ and $j$ with $1≤i<j≤\binom{n}{k}$, then these two quantities are equal. My question can ultimately be split into two parts:
(1) Is it the case that $p\left(\bigcup_{i=1}^\binom{n}{k}E_i\right)\neq \sum_{i=1}^\binom{n}{k}p\left(E_i\right)$, and, if so, what combination of $n$, $k$, $E_i$ and $E_j$ would illustrate the corresponding pairwise dependence?
(2) If the above quantities are not equal, can somebody help explain why $p\left(\bigcup_{i=1}^\binom{n}{k}E_i\right)$ is equal to the probability that there are either $k$ mutual friends or $k$ mutual enemies among the $n$ people, and $\sum_{i=1}^\binom{n}{k}p\left(E_i\right)$ is not?
You’re confusing independence and disjointness. The prerequisite for the probability of the union of two events to be the sum of their probabilities is that they are disjoint (i.e. mutually exclusive), not that they are independent – to the contrary, except for the empty event that occurs with probability $0$, disjointness guarantees dependence, since independence requires the probability of the intersection to be the product of the individual probabilities, and this can’t be the case if the intersection is empty but the individual events have non-zero probabilities.
In the present case, the events are neither disjoint, not independent. They are not disjoint because it is entirely possible that more than one subset of size $k$ consists entirely of mutual friends or entirely of mutual enemies. And they are not independent because a subset being monochromatic makes it much more likely that similar subsets, e.g. that differ only in one element, are also monochromatic.
Thus there are no special relationships among these probabilities; you can only use the general inequalities. Here the relevant inequality is the fact that the probability of the union is at most the sum of the probabilities of the individual events (with equality obtaining if the events are mutually exclusive).