Define the Ramsey number $ R(k,m)$ to be the minimum number $ n$ of vertices required of the complete graph $ K_n$ so that for any two-coloring (red, blue) of the edges of $ K_n$ one of two things will happen:
- There is a red $ k$-clique; that is, a complete subgraph of $ k$ vertices for which all edges are red.
- There is a blue $ m$-clique.
It is known that these numbers are always finite, but it is very difficult to compute them exactly.
Problem: Prove that the Ramsey number $ R(m,m) > n$ whenever $ n,m$ satisfy
$ \displaystyle \binom{n}{m}2^{1-\binom{m}{2}} < 1$
Solution: Color the edges of $ K_n$ uniformly at random (that is, each edge has probability 1/2 of being colored red). For any complete subgraph $ G = K_m$, define by event $ A_G$ the event that $ G$ is monochromatic (its edges are either all red or all blue).
Now the probability that $ A_G$ occurs (where $ G$ is fixed ahead of time) is easy to compute:
$ \displaystyle \textup{Pr}(A_G) = \left (\frac{1}{2} \right)^{\binom{m}{2} – 1} = 2^{1-\binom{m}{2}}$
Since there are $ \binom{n}{m}$ possible subgraphs with $ m$ vertices, The probability that for some $ G$ the event $ A_G$ occurs is at most
$ \displaystyle \binom{n}{m}2^{1-\binom{m}{2}}$
Whenever this quantity is strictly less than 1 (by assumption) then there is a positive probability that no event $ A_G$ will occur. That is, there is a positive probability that a random coloring will have no monochromatic subgraph $ K_m$. So there must exist such a coloring, and the Ramsey number $ R(m,m)$ must be larger than $ n$. $ \square$
Discussion: This proof (originally due to Erdős) is a classic example of the so-called probabilistic method. In particular, we create a probability space from the object we wish to study, and then we make claims about the probability of joint events.
While it seems quite simple in nature, the probabilistic method has been successfully applied to a wide variety of problems in mathematics. For instance, there is an elegant proof in complexity theory that $ \textup{BPP} \subset \textup{P/poly}$ which uses this same method. The probabilistic method has been applied to loads of problems in combinatorics, number theory, and graph theory, and it forms the foundation of the area of random graph theory (which is the setting in which one studies social networks). Perhaps unsurprisingly, there is also a proof of the fundamental theorem of algebra that uses the probabilistic method.
Great presentation! Strictly speaking, isn’t the chance that for some $G$ the event $A_G$ occurs actually less than the number given? It seems that for two graphs $G_1$ and $G_2$ sharing some edges, $A_{G_1}$ and $A_{G_2}$ are not independent, and this bound could be (and I’d guess has been?) improved by accounting for this.
Yes there should have been an “at most” before the number I gave, which I’ve just updated. I think part of the elegance of the probabilistic method is in its simple bounds. So yes, there are better bounds achievable by inspecting the dependence of two randomly chosen subgraphs. For this gallery at least, I think it would muddle the point. However, I’d like to keep an eye out for an example where it’s necessary to deal with dependence.
Hello,
First, I have to thank you for your great blog, it is fantastic.
Also, I have an inquiry about random graphs programming.
Can you please help me with the following question:
Phase 1: I need to generate a random graph, then calculate its chromatic number.
Phase 2: I need to add a vertex to the mentioned graph and then calculate its chromatic number again to see if the chromatic number increases by adding the new vertex or not.
I will be so delighted if you can help me. I am studying statistics and not perfect in programming.
Sincerely,