Clarification on a step in Erdős's probabilistic proof for the lower bound of Ramsey Numbers?

58 Views Asked by At

Generally I understand this argument, but I would like a more complete proof that the "best chance" you'll get at finding a complete monochromatic subgraph is if we treat each complete subgraph independently.

This intuitively makes sense, since these subgraphs may "interfere" with each other by sharing edges in the larger graph. However, I have not seen a hard proof that this interference will necessarily lower the probability of finding a complete monochromatic subgraph.

1

There are 1 best solutions below

0
On

The simple probability theorem that I was searching for was the Union Bound.