A researcher wants to prove there exists a 2-coloring of K₁₀₀ with no monochromatic K₈. No explicit such coloring is known. Which approach proves this?
AExhaustively check all possible 2-colorings of K₁₀₀ until one without a monochromatic K₈ is found
BVerify that R(8,8) equals exactly 100, confirming K₁₀₀ is on the threshold
CUse the probabilistic method: show the expected number of monochromatic K₈ subgraphs in a random 2-coloring is less than 1
DApply the pigeonhole principle to show that K₁₀₀ must contain an edge-coloring avoiding K₈
The probabilistic method is used precisely when an explicit construction is unavailable. Randomly 2-color each edge of K₁₀₀ independently with probability 1/2. If the expected number of monochromatic K₈ subgraphs is less than 1, then by linearity of expectation, there must exist at least one coloring with zero such subgraphs — even though we cannot point to it. This non-constructive existence proof was revolutionary. Option B is the wrong direction: if R(8,8) = 100, that means every 2-coloring of K₁₀₀ contains a monochromatic K₈ (the claim would be false). Option A is computationally intractable — K₁₀₀ has 4,950 edges, yielding 2^4950 possible colorings.
Question 2 Multiple Choice
Why is R(3,3) = 6 and not 5?
AK₆ has too many edges to 2-color without forming a triangle, but K₅ has few enough edges to avoid all triangles
BThe formula R(r,b) ≥ r + b − 1 gives 3 + 3 − 1 = 5, so R(3,3) must be at least 6
CK₅ has a valid 2-coloring with no monochromatic triangle (showing 5 is insufficient), and the pigeonhole principle forces a monochromatic triangle in any 2-coloring of K₆
DR(3,3) equals R(2,2)² = 4, and we add 2 for the diagonal case, giving 6
The proof has two parts. (1) Lower bound: exhibit a 2-coloring of K₅ with no monochromatic triangle. (The five-cycle with edges alternating red/blue, with non-adjacent edges the other color, works.) This proves R(3,3) > 5. (2) Upper bound: in any 2-coloring of K₆, pick any vertex v — it has 5 edges. By pigeonhole, at least 3 share a color, say red. Look at the 3 vertices at the other ends: if any edge between them is red, it with two red edges from v forms a red triangle. If all edges among them are blue, they form a blue triangle. Either way, a monochromatic triangle exists. This proves R(3,3) ≤ 6. Options B and D give incorrect formulas.
Question 3 True / False
R(5,5) is known exactly and can be computed by modern computers in a reasonable amount of time.
TTrue
FFalse
Answer: False
R(5,5) remains unknown despite decades of effort. It is known only to lie somewhere between 43 and 48. The difficulty is not merely computational power but combinatorial explosion: to verify a lower bound for R(5,5) > n, one must exhibit a 2-coloring of K_n with no monochromatic K₅, among 2^(n(n-1)/2) possible colorings. For K₄₂, this is approximately 2^861 — a number with about 260 digits. Even verifying that a single coloring contains no monochromatic K₅ requires checking all C(42,5) = 850,668 five-vertex subsets. The problem is intractable at current scales, which is why Ramsey number computation is one of combinatorics' most notorious open problems.
Question 4 True / False
The probabilistic lower bound proof for Ramsey numbers establishes that good colorings exist without constructing any of them explicitly.
TTrue
FFalse
Answer: True
This is Erdős's probabilistic method applied to Ramsey numbers. Randomly 2-color each edge of K_n independently; compute the expected number of monochromatic K_k subgraphs. If this expectation is less than 1, the probability of the 'good event' (no monochromatic K_k) is positive, so such colorings must exist — even though the argument gives no procedure for finding them. This non-constructive existence proof was considered revolutionary when introduced. The gap between these probabilistic lower bounds and the binomial coefficient upper bounds for R(k,k) remains one of the central open problems: we know good colorings exist for large n but cannot find them.
Question 5 Short Answer
What makes the probabilistic lower bound proof for Ramsey numbers remarkable, and why does it not help us find an explicit good coloring?
Think about your answer, then reveal below.
Model answer: The proof is remarkable because it establishes existence through expectation: if the expected number of 'bad' events (monochromatic cliques) in a random coloring is less than 1, then colorings with no bad events must exist. This proves R(k,k) > n without constructing the witness. It is non-constructive — the existence follows from the impossibility of the average exceeding zero, not from any explicit object. It does not help find explicit colorings because the argument works over the entire space of all 2^(n(n-1)/2) colorings simultaneously; it proves the space is non-empty but gives no method to navigate to a good element. Derandomizing such arguments to produce explicit constructions is an active research area with only partial results.
The non-constructive nature of the probabilistic method is philosophically striking: we can be certain that good colorings exist (and even that most random colorings are good, for small enough n relative to k) while having no algorithmic path to exhibit one. This gap between existence and constructibility is one of the deep tensions in combinatorics and theoretical computer science.