Ramsey numbers and recursive bounds

Define $R(s,t)$ as the smallest N such that every red–blue coloring of the edges of $K_N$ contains a red $K_s$ or a blue $K_t$. For s and t at least two, inspect one vertex v in a graph whose order is the sum of the two smaller Ramsey numbers. Among the other vertices, either sufficiently many are joined to v in red or sufficiently many are joined in blue. Otherwise their two neighborhood sizes would sum to at most N minus two.

In the red neighborhood, a red clique of size s minus one extends with v to the desired red clique, while a blue clique of size t already wins without v. The blue-neighborhood case is symmetric. This proves the recurrence. The boundary values R(1,t)=R(s,1)=1 permit induction, and Pascal's identity gives the familiar binomial upper bound. These bounds establish finiteness but need not be sharp; a recurrence upper bound should never be reported as an exact value without a matching coloring construction.

For six vertices, choose one vertex and three incident edges of the same color, which exist by the pigeonhole principle. Assume these are red. If any edge among their three other endpoints is red, it completes a red triangle through the chosen vertex. If no such edge is red, all three are blue and give a blue triangle. Interchanging the color names covers the other case. Thus six always suffices for a monochromatic triangle.

To show five does not suffice, color the edges of a five-cycle red and all its remaining pairs blue. The red graph has no triangle. Its complement is another five-cycle, so the blue graph also has no triangle. This supplies a concrete avoidance coloring and proves R(3,3)=6. The two directions have different logical jobs: a universal argument gives the upper bound, and a single counterexample below it supplies the lower bound.

Fix an integer k at least two, and color each edge independently red or blue with equal probability. For a fixed set of k vertices, the probability that all its edges have one color is twice two raised to minus the number of its pairs. Summing indicators over all k-subsets gives the expected number X of monochromatic k-cliques. Independence between different k-subsets is unnecessary for this expectation calculation; linearity of expectation handles their overlapping edges. Only independence of the individual edge colors was used for a fixed set.

If the expectation is below one, some coloring has X=0 because X is a nonnegative integer. Therefore that N is strictly below R(k,k). This is an existence argument, not a promise that a typical coloring works with high probability or an efficient algorithm for finding one. For small k the criterion can be weak: failure to push the expectation below one merely means this particular proof fails. It does not establish that every coloring contains the pattern.