El teorema de Folkman es un teorema en matemáticas, y más particularmente en combinatoria aritmética y teoría de Ramsey . De acuerdo con este teorema, siempre que los números naturales se dividen en un número finito de subconjuntos, existen conjuntos de números arbitrariamente grandes, todas cuyas sumas pertenecen al mismo subconjunto de la partición. [1] El teorema había sido descubierto y probado de forma independiente por varios matemáticos, [2] [3] antes de que fuera nombrado "teorema de Folkman", como un monumento a Jon Folkman , por Graham , Rothschild y Spencer .[1]
Declaración del teorema
Sea N el conjunto {1, 2, 3, ...} de enteros positivos, y suponga que N se divide en k subconjuntos diferentes N 1 , N 2 , ... N k , donde k es cualquier entero positivo. Entonces el teorema de Folkman establece que, para cada entero positivo m , existe un conjunto S m y un índice i m tal que S m tiene m elementos y tal que toda suma de un subconjunto no vacío de S m pertenece a N i m . [1]
Relación con el teorema de Rado y el teorema de Schur
El teorema de Schur en la teoría de Ramsey establece que, para cualquier partición finita de enteros positivos, existen tres números x , y y x + y que pertenecen todos al mismo conjunto de particiones. Es decir, es el caso especial m = 2 del teorema de Folkman.
El teorema de Rado en la teoría de Ramsey se refiere a un enunciado de problema similar en el que los números enteros se dividen en un número finito de subconjuntos; el teorema caracteriza las matrices enteras A con la propiedad de que se puede garantizar que el sistema de ecuaciones lineales A x = 0 tiene 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 siempre que satisface las condiciones del teorema de Rado; El teorema de Folkman es equivalente a la regularidad del sistema de ecuaciones
donde T varía sobre cada subconjunto no vacío del conjunto {1, 2, ..., m }. [1]
Multiplicación versus suma
Es posible reemplazar la suma por la multiplicación en el teorema de Folkman: si los números naturales están divididos finitamente, existen conjuntos S arbitrariamente grandes, de modo que todos los productos de subconjuntos no vacíos de S pertenecen a un solo conjunto de particiones. De hecho, si uno restringe S para que consista solo en potencias de dos , entonces este resultado se sigue inmediatamente de la versión aditiva del teorema de Folkman. Sin embargo, está abierto si existen conjuntos arbitrariamente grandes de modo que todas las sumas y todos los productos de subconjuntos no vacíos pertenezcan a un único conjunto de particiones. 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 2 }, resultado que fue mejorado 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 debe existir necesariamente un conjunto de la forma { x , y , x + y , xy } para los que los cuatro elementos pertenecen al mismo conjunto de particiones. [1]
Teorema canónico del folkman
Dejar denotar el conjunto de todas las sumas finitas de elementos de . Dejar sea una coloración (posiblemente infinita) de los enteros positivos, y deje ser un entero positivo arbitrario. Existe de modo que se cumpla al menos una de las siguientes 3 condiciones.
1) es un conjunto monocromático.
2) es un conjunto de arcoíris.
3) Para cualquier , el color de está determinada únicamente por .
Resultados anteriores
Richard Rado y J. H. Sanders habían probado variantes del teorema de Folkman . [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]
Referencias
- ↑ a b c d e f g 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.
- ^ a b Rado, R. (1970), "Algunos teoremas de partición", Teoría combinatoria y sus aplicaciones, III: Proc. Colloq., Balatonfüred, 1969 , Amsterdam: North-Holland, págs. 929–936, MR 0297585 CS1 maint: parámetro desalentado ( enlace ).
- ^ a b Sanders, Jon Henry (1968), Una generalización del teorema de Schur , Ph.D. tesis, Universidad de Yale, MR 2617864.
- ^ Moreira, J. (2017), "Sumas y productos monocromáticos en N ", Anales de Matemáticas, SEGUNDA SERIE, Vol. 185, No. 3 , Evanston: Departamento de Matemáticas, Universidad de Princeton, págs. 1069–1090, MR 3664819 CS1 maint: parámetro desalentado ( enlace ).