11.5: Teorema de Ramsey

Última actualización
Guardar como PDF

Page ID: 118388

Mitchel T. Keller & William T. Trotter
Georgia Tech & Morningside College

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

En este momento, probablemente no te sorprenda ver que hay una forma muy general del teorema de Ramsey. Tenemos un número limitado de contenedores o colores y estamos colocando los subconjuntos de un tamaño fijo en estas categorías. La conclusión es que existe un conjunto grande el cual se trata de manera uniforme.

Aquí está la declaración formal.

Teorema 11.6

Let\(r\) y\(s\) ser enteros positivos y let\(\textbf{h}=(h_1,h_2,…,h_r)\) ser una cadena de enteros con\(h_i \geq s\) para cada uno\(i=1,2,…,s\). Luego existe un número entero menos positivo\(R(s:h_1,h_2,…,h_r)\) para que si\(n \geq n_0\) y\(\phi:C([n],s] \rightarrow [r]\) es alguna función, entonces existe un entero\(\alpha \in [r]\) y un subconjunto\(H_{\alpha}⊆[n]\) con\(|H_{\alpha}|=h_{\alpha}\) para que \(\phi (S)= \alpha\)para cada\(S \in C(H_{\alpha},s)\).

Aquí no incluimos la prueba de esta declaración general, pero los estudiantes más ambiciosos pueden intentarla por su cuenta. Tenga en cuenta que el caso\(s=1\) es solo el Principio de Agujero Paloma, mientras que el caso\(s=r=2\) es solo el Teorema de Ramsey para Gráficas. Se requiere un argumento que utilice doble inducción para la prueba en el caso general. La primera inducción está encendida\(r\) y la segunda está encendida\(s\).