Force structure in every coloring

Try

Among six people, model each pair as either acquainted or unacquainted. The claim is that three are mutually acquainted or three are mutually unacquainted. This is a statement about every two-coloring of the complete graph on six vertices. No randomness or equal balance between the two relations is assumed. Ramsey theory asks how large a structure must be before some ordered pattern is unavoidable.

Predict

Predict why looking at one person is enough to begin. Among their five connections, at least three have the same type. If any pair among those three has that same connection type, they and the original person form the desired triple. If none does, all three pairwise connections among them have the other type, again forming the desired triple. The proof exhausts cases rather than estimating a probability.

Experiment

Compare upper and lower certificates.

Size	Evidence	Conclusion
6	Three same-color neighbors argument	Every coloring has a monochromatic triangle
5	Red five-cycle, blue complement	Some coloring avoids both triangles

Together these establish R(3, 3)=6. An upper-bound proof alone would not show minimality; a construction at size five supplies the missing half.

Understand

Define R(s, t) as the least N such that every red-blue edge coloring of K_N has a red K_s or a blue K_t. Boundary values R(1, t)=R(s, 1)=1 start an induction. Put N=R(s−1, t)+R(s, t−1) and choose a vertex v. If it has at least R(s−1, t) red neighbors, the induced graph contains either a red K_(s−1), extended by v, or a blue K_t. Otherwise it has at least R(s, t−1) blue neighbors, giving the symmetric conclusion. The count works because the two neighbor classes total N−1. This proves finiteness and the recurrence bound R(s, t)≤R(s−1, t)+R(s, t−1).

Apply

Combining the recurrence with Pascal’s identity yields R(s, t)≤C(s+t−2, s−1). The bound is often far from exact; it proves existence without giving the optimal threshold. For lower bounds, construct a coloring with no forbidden clique, or use the probabilistic method. If edges of K_n are independently red or blue with equal probability, a specified k-set is monochromatic with probability 2·2^(−C(k, 2)). The expected number of monochromatic k-cliques is C(n, k) times that probability. If it is below one, some coloring has none. This is an existence argument from an average, developed more fully in the next lesson.

Continue

Distinguish Ramsey structure from density-based structure. Turán assumes many edges in one graph and forces a clique; Ramsey considers a complete graph whose edges are split among colors and forces a monochromatic pattern in some color. A bound computed from the recurrence should be labeled as an upper bound, not silently reported as an exact Ramsey number. In a proof report, list the quantifiers explicitly: every coloring above a bound versus at least one avoiding coloring below it. Those directions determine what kind of certificate is required.

Return to the combinatorics and graph theory unit for prerequisite choices and targeted retries. Continue with prove existence by averaging and alteration.