Ramsey bounds

How large must a graph be before every coloring of its edges contains a prescribed monochromatic pattern? Ramsey numbers measure when a pattern becomes unavoidable.

Ramsey theory studies the patterns that become unavoidable in sufficiently large structures. For R(s,t), every red/blue edge coloring of the complete graph on that many vertices must contain a red clique of size s or a blue clique of size t. General Ramsey problems can instead ask for other graphs, such as books of triangles sharing an edge.

Lower and upper bounds answer different questions. One coloring avoiding the forbidden patterns proves a lower bound. An upper bound needs an argument covering every possible coloring. A search that fails to find a coloring supplies neither a proof of impossibility nor an exact value.