Cotas superiores e inferiores.
El número de Ramsey $R(r, s)$ es el entero más chico $n$ tal que cualquier coloración de las aristas del grafo completo $K_n$ con dos colores (digamos, rojo y azul) tiene una clique roja monocromática de tamaño $r$ ($K_r$) o una clique azul monocromática de tamaño $s$ ($K_s$). Aunque el Teorema de Ramsey garantiza que estos números existen, sacar sus valores exactos es muy difícil. Por ejemplo, aunque $R(3,3)=6$ y $R(4,4)=18$, el valor de $R(5,5)$ sigue siendo un misterio, y ahorita solo sabemos que está entre 43 y 48. Como el cálculo exacto casi siempre es imposible para $r, s \ge 5$, los matemáticos se apoyan en encontrar límites superiores e inferiores rigurosos.
Normalmente encuentras los límites superiores usando argumentos de inducción basados en la desigualdad $R(r, s) \le R(r-1, s) + R(r, s-1)$. Esta estructura recursiva te deja acotar los números de Ramsey usando coeficientes binomiales. Estos límites garantizan que una estructura lo suficientemente grande siempre va a tener la subestructura que buscas. Este es un concepto fundamental del "orden inevitable" en la combinatoria: si un sistema es lo suficientemente grande, el desorden total es imposible.
Por el contrario, los límites inferiores normalmente los