Doubt about probabilistic argument on Wikipedia

Question

In this wikipedia page, a claimed proof of the following statement is sketched out: Given positive integers $g$ and $k$, there exists a graph $G$ containing only cycles of length at least $g$, such that the chromatic number of $G$ is at least $k$.

The proof proceeds as follows. First they construct a random graph $G$ on $n$ vertices, with each edge of $K_n$ included with probability $p = n^{1/g-1}$. Long story short, they show that, if $X$ denotes the number of cycles with length less than $g$, $$\mathrm{Pr}(X \leq \frac{n}{2}) \geq 1 - o(1) \geq 1/2$$ and that if $Y$ is the size of the largest independent set in $G$, $$\mathrm{Pr}(Y < \lceil{\frac{n}{2k}}\rceil) \geq 1 - o(1) \geq 1/2$$ for all large $n$. Then, they claim that the probability that $G$ has both of these properties is also positive, as the events for these properties cannot be disjoint (if they were, their probabilities would sum up to more than 1). I really fail to understand this point. First of all, $\mathrm{Pr}(X \leq \frac{n}{2}) + \mathrm{Pr}(Y < \lceil{\frac{n}{2k}}\rceil)$ is clearly greater than $1$ for large $n$. Second, how can they claim that the events are not disjoint simply because their probabilities sum up to less than $1$?

Answer 1

We exactly need to use the fact that $\Pr[X \le \frac n2] + \Pr[Y < \frac n{2k}]$ does sum to more than $1$ for large $n$.

If the two events were disjoint, then we'd have $\Pr[X \le \frac n2] + \Pr[Y < \frac n{2k}] = \Pr[X \le \frac n2 \text{ or } Y < \frac n{2k}]$: if two events are disjoint, then their probabilities add.

But if $\Pr[X \le \frac n2] + \Pr[Y < \frac n{2k}] > 1$, then this tells us that $\Pr[X \le \frac n2 \text{ or } Y < \frac n{2k}] > 1$, which is a contradiction: nothing can have probability bigger than $1$.

Since assuming that the two events are disjoint leads to a contradiction, they cannot be disjoint.

There is a way to quantify this. For any $A$ and $B$, $\Pr[A \text{ or } B] = \Pr[A] + \Pr[B] - \Pr[A \text { and }B]$, so $\Pr[A] + \Pr[B] - \Pr[A \text{ and }B]$ must in particular be at most $1$. Rearranging, we get $$ \Pr[A \text{ and } B] \ge \Pr[A] + \Pr[B] - 1 $$ which is a lower bound on the probability that two events with a high probability overlap.

Answer 2

Let $A$ and $B$ denote the complement of the two events for simplicity. Suppose that $P(A) < 1/2$ and $P(B) < 1/2$, which is true for all large $n$. Then by the union bound, $P(A \cup B) \leq P(A) + P(B) < 1$ (in fact, it is $o(1)$). Thus the complement $A^c \cap B^c$ occurs with positive probability (in fact, arbitrarily close to 1).