A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
Ramsey numbers R(s,t) are the minimum n such that every 2-coloring of K_n contains either a red K_s or a blue K_t. While many small values are known exactly, most Ramsey numbers are unknown. Probabilistic bounds, recurrence relations, and constructive lower bounds are essential tools.
Apply known Ramsey bounds to compute upper and lower bounds on unknown R(s,t) values. Use the probabilistic method to show existence of r-colorings avoiding monochromatic cliques.
From Ramsey theory foundations, you know the core existence theorem: R(s, t) always exists — for any s and t, there is some graph size beyond which every 2-coloring of edges must contain either a red K_s or a blue K_t. The Ramsey number R(s, t) is the *smallest* such threshold. Existence is guaranteed, but computing the actual value is a famously hard problem. For most pairs (s, t), we only know a range: a lower bound L and an upper bound U such that L ≤ R(s, t) ≤ U, with the true value hiding somewhere in between.
The standard upper bound comes from a recurrence. Since any vertex in K_n either has at least R(s-1, t) red neighbors or at least R(s, t-1) blue neighbors (by pigeonhole), we get R(s, t) ≤ R(s-1, t) + R(s, t-1). Combined with the boundary conditions R(s, 1) = 1 and R(1, t) = 1, this recurrence yields R(s, t) ≤ C(s+t-2, s-1), a binomial coefficient bound. For the diagonal case R(k, k), this gives R(k, k) ≤ 4k, meaning the Ramsey number grows at most exponentially.
Lower bounds — showing that R(s, t) is *large* — use the probabilistic method. Color each edge of K_n red or blue independently at random with probability 1/2 each. The probability that a specific set of s vertices forms a red clique is (1/2)^C(s,2). There are C(n, s) such sets, so by the union bound, the probability that *any* red K_s exists is at most C(n, s) · (1/2)^C(s,2). If this probability is less than 1/2, and similarly for blue K_t, then the total probability of a monochromatic clique is less than 1 — meaning a "good" coloring must exist. This gives R(k, k) > 2k/2, a lower bound matching the upper bound exponentially in k. The argument is non-constructive: it proves a good coloring exists without exhibiting one.
The gap between upper and lower bounds is striking for specific values. R(3, 3) = 6 is classical and exact. R(4, 4) = 18 is known. But R(5, 5) is only known to lie between 43 and 48, despite decades of effort. Erdős famously quipped that if an alien civilization threatened to destroy Earth unless humanity computed R(5, 5), we should focus all our computing power on it — but if they demanded R(6, 6), we should try to destroy the aliens first. The difficulty is inherent: the search space for edge colorings of K_n grows as 2n²/2, making exhaustive search infeasible even for modest n. Improving the probabilistic bounds requires genuinely new ideas, and closing them further is one of the major open problems in combinatorics.