Teorema de Folkman

El teorema de Folkman es un teorema matemático , y más particularmente de combinatoria aritmética y teoría de Ramsey . Según este teorema, siempre que los números naturales se dividen en un número finito de subconjuntos, existen conjuntos arbitrariamente grandes de números cuyas sumas pertenecen al mismo subconjunto de la partición. ^{[ 1 ]} El teorema fue descubierto y demostrado independientemente por varios matemáticos, ^{[ 2 ] [ 3 ]} antes de que Graham , Rothschild y Spencer lo denominaran "teorema de Folkman" en memoria de Jon Folkman . ^{[ 1 ]}

Sea N el conjunto {1, 2, 3, ...} de enteros positivos, y supongamos que N se divide en k subconjuntos distintos N₁ , N₂ _, ... _, Nᵏ , donde k es cualquier entero positivo. Entonces _, el teorema de Folkman establece que, para cada entero positivo m , existe un conjunto _Sᵐ y un índice _iᵐ tales que Sᵐ tiene _m elementos y tal que toda suma de un subconjunto no ^vacío _de Sᵐ pertenece _a Nᵐ _. ^{[ 1} ]

El teorema de Schur en la teoría de Ramsey establece que, para cada entero positivo k , existe un entero positivo S , tal que para cada partición de los enteros${\displaystyle \{1,\ldots ,S\}}$en k partes, una de las partes contiene enteros x , y y z con${\displaystyle x+y=z}$. Es decir, es el caso especial m = 2 del teorema de Folkman.

El teorema de Rado en la teoría de Ramsey trata un problema similar en el que los enteros se dividen en un número finito de subconjuntos; el teorema caracteriza las matrices enteras A con la propiedad de que el sistema de ecuaciones lineales A x = 0 tiene garantizada una solución en la que cada coordenada del vector solución x pertenece al mismo subconjunto de la partición. Se dice que un sistema de ecuaciones es regular cuando satisface las condiciones del teorema de Rado; el teorema de Folkman es equivalente a la regularidad del sistema de ecuaciones.

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

donde T recorre cada subconjunto no vacío del conjunto {1, 2, ..., m }. ^{[ 1 ]}

En el teorema de Folkman, es posible sustituir la suma por la multiplicación: si los números naturales se dividen de forma finita, existen conjuntos S arbitrariamente grandes tales que todos los productos de subconjuntos no vacíos de S pertenecen a un único conjunto de partición. De hecho, si se restringe S a que conste únicamente de potencias de dos , este resultado se deduce inmediatamente de la versión aditiva del teorema de Folkman. Sin embargo, queda por dilucidar si existen conjuntos arbitrariamente grandes tales que todas las sumas y todos los productos de subconjuntos no vacíos pertenecen a un único conjunto de partición. El primer ejemplo de no linealidad en la Teoría de Ramsey que no consiste en monomios fue dado, independientemente, por Furstenberg y Sarkozy en 1977, con la familia { x , x + y ² }, resultado que fue mejorado posteriormente por Bergelson en 1987. En 2016, J. Moreira demostró que existe un conjunto de la forma { x , x + y , xy } contenido en un elemento de la partición ^{[ 4 ].} Sin embargo, ni siquiera se sabe si necesariamente debe existir un conjunto de la forma { x , y , x + y , xy } para el cual los cuatro elementos pertenezcan al mismo conjunto de partición. ^{[ 1 ]}

Dejar${\displaystyle FS(\{x_{i}\}_{i=1}^{n})}$denotamos el conjunto de todas las sumas finitas de elementos de${\displaystyle \{x_{i}\}_{i=1}^{n}}$. Dejar${\displaystyle C}$Sea una coloración (posiblemente infinita) de los enteros positivos, y sea${\displaystyle n}$Sea un entero positivo arbitrario. Existe${\displaystyle \{x_{i}\}_{i=1}^{n}}$de modo que se cumpla al menos una de las siguientes 3 condiciones.

1)${\displaystyle FS(\{x_{i}\}_{i=1}^{n})}$es un conjunto monocromático.

2)${\displaystyle FS(\{x_{i}\}_{i=1}^{n})}$es un conjunto arcoíris.

3) Para cualquier${\displaystyle B\subseteq [1,n]}$, el color de${\displaystyle \sum _{i\in B}x_{i}}$está determinado únicamente por${\displaystyle \min(B)}$.

Variantes del teorema de Folkman fueron demostradas por Richard Rado y por J.  H.  Sanders. ^{[ 2 ] [ 3 ] [ 1 ]} El teorema de Folkman fue nombrado en memoria de Jon Folkman por Ronald Graham , Bruce Lee Rothschild y Joel Spencer , en su libro sobre la teoría de Ramsey . ^{[ 1 ]}