The Binomial Upper Bound by Pascal Induction

From the Neighborhood Recurrence to a Binomial Bound

Ramsey numbers ask how large a graph must be before every red-blue coloring of its edges contains a monochromatic clique of a specified size. The neighborhood recurrence reduces a pair of clique parameters to two smaller pairs. Pascal’s identity has exactly the same two-term structure, which lets us turn that recurrence into a closed binomial upper bound.

All graphs in this tutorial are finite and simple. An edge-coloring is a coloring of every edge of a complete graph with one of two colors, red or blue. A red \(K_s\) is a set of \(s\) vertices for which every pair is joined by a red edge; a blue \(K_t\) is defined in the same way.

The case of a clique parameter equal to \(1\) is immediate: any one vertex is already a monochromatic \(K_1\), regardless of the edge-coloring. Thus \(R(1,t)=R(s,1)=1\) for all positive \(s,t\). These boundary values will start the induction.

Here \(\binom{n}{k}\) is the number of \(k\)-element subsets of an \(n\)-element set, for integers \(0\le k\le n\). The proof uses the neighborhood recurrence for \(s,t\ge2\), together with the boundary values above. We state and justify the recurrence before carrying out the induction.

The Recurrence and Pascal’s Identity

Proof. Set \(A=R(s-1,t)\), \(B=R(s,t-1)\), and \(n=A+B\). Consider any red-blue coloring of the edges of \(K_n\), and choose a vertex \(v\). Its \(n-1=A+B-1\) incident edges are red or blue. If fewer than \(A\) are red and fewer than \(B\) are blue, then there are at most \((A-1)+(B-1)=A+B-2\) incident edges, a contradiction. Therefore \(v\) has at least \(A\) red neighbors or at least \(B\) blue neighbors.

If \(v\) has at least \(A\) red neighbors, choose \(A\) of them. The coloring on those vertices contains either a red \(K_{s-1}\) or a blue \(K_t\), by the definition of \(A\). In the first case, adjoining \(v\) gives a red \(K_s\), since all its edges to the chosen neighbors are red. In the second case there is already a blue \(K_t\). If instead \(v\) has at least \(B\) blue neighbors, the definition of \(B\) gives either a red \(K_s\) or a blue \(K_{t-1}\) among \(B\) of those neighbors. In the latter case, adjoining \(v\) gives a blue \(K_t\). Thus every coloring of \(K_n\) has one of the required cliques, proving the recurrence. \(\square\)

The numerical step that follows is Pascal’s identity: $$ \binom{N}{k}=\binom{N-1}{k-1}+\binom{N-1}{k} \qquad (1\le k\le N-1). $$ To verify it, count the \(k\)-element subsets of an \(N\)-element set according to whether they contain one fixed element. Those that contain it are formed by choosing \(k-1\) of the other \(N-1\) elements; those that do not contain it are formed by choosing \(k\) of them. The two classes are disjoint and include every \(k\)-element subset, so their counts add to \(\binom{N}{k}\).

Proof by Strong Induction

Proof of the binomial upper bound. We use induction on \(s+t\), proving the statement for all positive pairs with a given sum after proving it for smaller sums. If \(s=1\), then \(R(s,t)=1\) and \(\binom{s+t-2}{s-1}=\binom{t-1}{0}=1\). If \(t=1\), then \(R(s,t)=1\) and \(\binom{s+t-2}{s-1}=\binom{s-1}{s-1}=1\). This proves all boundary cases, including \((s,t)=(1,1)\).

Now suppose \(s,t\ge2\), and assume the bound holds for all positive pairs whose parameter sum is smaller than \(s+t\). Both \((s-1,t)\) and \((s,t-1)\) have sum \(s+t-1\), so the induction hypothesis applies to them. The neighborhood recurrence gives $$ \begin{aligned} R(s,t) &\le R(s-1,t)+R(s,t-1)\\ &\le \binom{s+t-3}{s-2}+\binom{s+t-3}{s-1}\\ &=\binom{s+t-2}{s-1}. \end{aligned} $$ For the last equality, Pascal’s identity applies with \(N=s+t-2\) and \(k=s-1\). Since \(s,t\ge2\), these indices satisfy \(1\le s-1\le s+t-3\). This completes the induction and proves the bound for every positive pair. \(\square\)

The induction concerns an upper bound, not necessarily the exact value of \(R(s,t)\). At each step it bounds the two smaller Ramsey numbers and adds those bounds. Pascal’s identity then combines the two binomial coefficients into one. This matching of indices is the central calculation.

Why the Indexing Matters

The binomial coefficient is not guessed from the recurrence: its two lower-parameter choices come directly from reducing one clique target at a time. In the term for \(R(s-1,t)\), the coefficient is \(\binom{s+t-3}{s-2}\); in the term for \(R(s,t-1)\), it is \(\binom{s+t-3}{s-1}\). These are the two terms whose sum is \(\binom{s+t-2}{s-1}\).

Common mistake: shifting one lower index. For \(R(3,4)\), a mistaken substitution might use \(\binom{4}{2}\) for both recurrence terms, producing \(6+6=12\). But the parameter pairs are \((2,4)\) and \((3,3)\), whose bounds are \(\binom{4}{1}=4\) and \(\binom{4}{2}=6\), respectively. The correct sum is \(4+6=10=\binom{5}{2}\). The check is to substitute each smaller pair into \(\binom{a+b-2}{a-1}\) separately before applying Pascal’s identity.

A second error is to start the recurrence with only \(A+B-1\) vertices. After selecting a vertex, that leaves \(A+B-2\) incident edges to count, which does not force at least \(A\) red or \(B\) blue edges: the two color counts could be \(A-1\) and \(B-1\). The recurrence uses \(A+B\) vertices, leaving \(A+B-1\) incident edges, enough for the required conclusion.

The result supplies a convenient general upper bound using only a recurrence and a binomial coefficient. Its value is that it converts a two-parameter recursive estimate into a single explicit expression. The bound need not be exact: the argument guarantees that every coloring has a required clique by the stated number of vertices, but it does not show that fewer vertices can fail. Distinguishing an upper bound from an exact Ramsey number is essential when interpreting the calculation.