Teorema de Rado (teoría de Ramsey)

Resultado matemático en sistemas de ecuaciones lineales

El teorema de Rado es un teorema de la rama de las matemáticas conocida como teoría de Ramsey . Lleva el nombre del matemático alemán Richard Rado . Fue probado en su tesis, Studien zur Kombinatorik .

Declaración

Sea un sistema de ecuaciones lineales, donde es una matriz con entradas enteras. Se dice que este sistema es regular si, para cada coloración de los números naturales 1, 2, 3, ..., el sistema tiene una solución monocromática. Un sistema es regular si es r-regular para todo  r  ≥ 1.${\displaystyle A\mathbf {x} =\mathbf {0} }$${\displaystyle A}$${\displaystyle r}$${\displaystyle r}$

El teorema de Rado establece que un sistema es regular si y solo si la matriz A satisface la condición de las columnas . Deje c _i denota el i columna -ésimo de A . La matriz A satisface la condición de las columnas siempre que exista una partición C ₁ , C ₂ , ..., C _n de los índices de columna tal que si , entonces${\displaystyle A\mathbf {x} =\mathbf {0} }$${\displaystyle s_{i}=\Sigma _{j\in C_{i}}c_{j}}$

1. s ₁ = 0
2. para todos los i  ≥ 2, S _i se puede escribir como un racional ^[1] combinación lineal de la c _j ' s en todo el C _k con k  <  i . Esto significa que s _i está en el subespacio lineal de Q ^m generado por el conjunto de c _j .

Casos especiales

El teorema de Folkman , la afirmación de que existen conjuntos arbitrariamente grandes de enteros cuyas sumas no vacías son monocromáticas, puede verse como un caso especial del teorema de Rado sobre la regularidad del sistema de ecuaciones.

${\displaystyle x_{T}=\sum _{i\in T}x_{\{i\}},}$

donde T varía sobre cada subconjunto no vacío del conjunto {1, 2, ..., x }. ^[2]

Otros casos especiales de Rado del teorema son el teorema de Schur y Van der Waerden teorema . Para probar lo primero, aplique el teorema de Rado a la matriz . Para el teorema de Van der Waerden con m elegido para ser la longitud de la progresión aritmética monocromática, se puede considerar, por ejemplo, la siguiente matriz:${\displaystyle (1\ 1\ {-1})}$

${\displaystyle \left({\begin{matrix}1&1&-1&0&\cdots &0&0\\1&2&0&-1&\cdots &0&0\\\vdots &\vdots &\vdots &\vdots &\ddots &\vdots &\vdots \\1&m-1&0&0&\cdots &-1&0\\1&m&0&0&\cdots &0&-1\end{matrix}}\right)}$

Computabilidad

Dado un sistema de ecuaciones lineales, a priori no está claro cómo comprobar computacionalmente que es regular. Afortunadamente, el teorema de Rado proporciona un criterio que se puede comprobar en un tiempo finito. En lugar de considerar coloraciones (de un número infinito de números naturales), se debe verificar que la matriz dada satisfaga la condición de las columnas. Dado que la matriz consta solo de un número finito de columnas, esta propiedad se puede verificar en un tiempo finito.

Sin embargo, el problema de la suma del subconjunto se puede reducir al problema de calcular la partición requerida C ₁ , C ₂ , ..., C _n de columnas: Dado un conjunto de entrada S para el problema de la suma del subconjunto, podemos escribir los elementos de S en una matriz de forma 1 × | S |. Entonces los elementos de S correspondientes a los vectores en la partición C ₁ suman cero. El problema de la suma de subconjuntos es NP-completo . Por lo tanto, verificar que un sistema de ecuaciones lineales es regular también es un problema NP-completo.

Referencias

1. Teoría de grafos moderna de Béla Bollobás . 1ª ed. 1998. ISBN  978-0-387-98488-9 . Página 204
2. Graham, Ronald L .; Rothschild, Bruce L .; Spencer, Joel H. (1980), "3.4 Sumas finitas y uniones finitas (Teorema de Folkman)", Teoría de Ramsey , Wiley-Interscience, págs. 65–69.