Regularidad de particiones

En combinatoria , una rama de las matemáticas , la regularidad de partición es una noción de tamaño para una colección de conjuntos.

Dado un conjunto , una colección de subconjuntos se denomina regular a la partición si cada conjunto A en la colección tiene la propiedad de que, sin importar cómo se divida A en un número finito de subconjuntos, al menos uno de los subconjuntos también pertenecerá a la colección. Es decir, para cualquier , y cualquier partición finita , existe un i  ≤  n tal que pertenece a . La teoría de Ramsey a veces se caracteriza como el estudio de qué colecciones son regulares a la partición. ${\displaystyle X}$ ${\displaystyle \mathbb {S} \subset {\mathcal {P}}(X)}$ ${\displaystyle A\in \mathbb {S} }$ ${\displaystyle A=C_{1}\cup C_{2}\cup \cdots \cup C_{n}}$ ${\displaystyle C_{i}}$ ${\displaystyle \mathbb {S} }$ ${\displaystyle \mathbb {S} }$

Ejemplos

• La colección de todos los subconjuntos infinitos de un conjunto infinito X es un ejemplo prototípico. En este caso, la regularidad de partición afirma que cada partición finita de un conjunto infinito tiene una celda infinita (es decir, el principio del casillero infinito ).
• Conjuntos con densidad superior positiva en : la densidad superior de se define como ( teorema de Szemerédi ) ${\displaystyle \mathbb {N} }$ ${\displaystyle {\overline {d}}(A)}$ ${\displaystyle A\subset \mathbb {N} }$ ${\displaystyle {\overline {d}}(A)=\limsup _{n\rightarrow \infty }{\frac {|\{1,2,\ldots ,n\}\cap A|}{n}}.}$
• Para cualquier ultrafiltro en un conjunto , la partición es regular: para cualquier , si , entonces exactamente uno . ${\displaystyle \mathbb {U} }$ ${\displaystyle X}$ ${\displaystyle \mathbb {U} }$ ${\displaystyle A\in \mathbb {U} }$ ${\displaystyle A=C_{1}\sqcup \cdots \sqcup C_{n}}$ ${\displaystyle C_{i}\in \mathbb {U} }$
• Conjuntos de recurrencia: un conjunto R de números enteros se denomina conjunto de recurrencia si para cualquier transformación que preserve la medida del espacio de probabilidad (Ω, β , μ ) y de medida positiva existe un valor distinto de cero tal que . ${\displaystyle T}$ ${\displaystyle A\in \beta }$ ${\displaystyle n\in R}$ ${\displaystyle \mu (A\cap T^{n}A)>0}$
• Llamemos a un subconjunto de números naturales rico en p si contiene progresiones aritméticas arbitrariamente largas . En ese caso, la colección de subconjuntos ricos en p es regular en cuanto a particiones ( Van der Waerden , 1927).
• Sea el conjunto de todos los n -subconjuntos de . Sea . Para cada n , es partición regular. ( Ramsey , 1930). ${\displaystyle [A]^{n}}$ ${\displaystyle A\subset \mathbb {N} }$ ${\displaystyle \mathbb {S} ^{n}=\bigcup _{A\subset \mathbb {N} }^{}[A]^{n}}$ ${\displaystyle \mathbb {S} ^{n}}$
• Para cada cardinal infinito , la colección de conjuntos estacionarios de es regular de partición. Más es cierto: si es estacionario y para algún , entonces algún es estacionario. ${\displaystyle \kappa }$ ${\displaystyle \kappa }$ ${\displaystyle S}$ ${\displaystyle S=\bigcup _{\alpha <\lambda }S_{\alpha }}$ ${\displaystyle \lambda <\kappa }$ ${\displaystyle S_{\alpha }}$
• La colección de -conjuntos: es un -conjunto si contiene el conjunto de diferencias para alguna secuencia . ${\displaystyle \Delta }$ ${\displaystyle A\subset \mathbb {N} }$ ${\displaystyle \Delta }$ ${\displaystyle A}$ ${\displaystyle \{s_{m}-s_{n}:m,n\in \mathbb {N} ,\,n<m\}}$ ${\displaystyle \langle s_{n}\rangle _{n=1}^{\infty }}$
• El conjunto de barreras en : llama a una colección de subconjuntos finitos de una barrera si: ${\displaystyle \mathbb {N} }$ ${\displaystyle \mathbb {B} }$ ${\displaystyle \mathbb {N} }$
  • ${\displaystyle \forall X,Y\in \mathbb {B} ,X\not \subset Y}$y
  • para todo infinito , hay alguno tal que los elementos de X son los elementos más pequeños de I; es decir , y . ${\displaystyle I\subset \cup \mathbb {B} }$ ${\displaystyle X\in \mathbb {B} }$ ${\displaystyle X\subset I}$ ${\displaystyle \forall i\in I\setminus X,\forall x\in X,x<i}$

Esto generaliza el teorema de Ramsey , ya que cada uno es una barrera. ( Nash-Williams , 1965) ^[1] ${\displaystyle [A]^{n}}$

• Productos finitos de árboles infinitos ( Halpern–Läuchli , 1966)
• Conjuntos sindéticos por partes (Brown, 1968) ^[2]
• Se denomina rico en ip a un subconjunto de números naturales si contiene conjuntos finitos arbitrariamente grandes junto con todas sus sumas finitas. En ese caso, la colección de subconjuntos ricos en ip es regular en cuanto a particiones ( Jon Folkman , Richard Rado y J. Sanders, 1968). ^[3]
• ( m , p , c )-conjuntos ^{[ aclaración necesaria ] [4]}
• Conjuntos de IP ^{[5] [6]}
• MT ^k conjuntos para cada k , es decir , k -tuplas de sumas finitas (Milliken–Taylor, 1975)
• Conjuntos centrales, es decir , los miembros de cualquier idempotente mínimo en , la compactificación de Stone-Čech de los números enteros. (Furstenberg, 1981, véase también Hindman, Strauss, 1998) ${\displaystyle \beta \mathbb {N} }$

Ecuaciones diofánticas

Una ecuación diofántica se denomina regular de partición si la colección de todos los subconjuntos infinitos que contienen una solución es regular de partición. El teorema de Rado caracteriza exactamente qué sistemas de ecuaciones diofánticas lineales son regulares de partición. Recientemente se ha avanzado mucho en la clasificación de ecuaciones diofánticas no lineales. ^{[7] [8]} ${\displaystyle P(\mathbf {x} )=0}$ ${\displaystyle \mathbb {N} }$ ${\displaystyle \mathbf {A} \mathbf {x} =\mathbf {0} }$

Referencias

1. C.St.JA Nash-Williams , Sobre secuencias transfinitas bien ordenadas, Proc. Camb. Phil. Soc. 61 (1965), 33–39.
2. T. Brown, Un método combinatorio interesante en la teoría de semigrupos localmente finitos, Pacific J. Math. 36 , no. 2 (1971), 285–289.
3. J. Sanders, Una generalización del teorema de Schur, tesis doctoral, Universidad de Yale, 1968.
4. W. Deuber, Mathematische Zeitschrift 133 , (1973) 109-123
5. N. Hindman, Sumas finitas de secuencias dentro de celdas de una partición de N , J. Comb. Theory A 17 (1974) 1–11.
6. N. Hindman, D. Strauss, Álgebra en la compactificación de Stone-Čech, De Gruyter, 1998
7. Di Nasso, Mauro; Luperi Baglini, Lorenzo (enero 2018). "Propiedades de Ramsey de ecuaciones diofánticas no lineales". Avances en Matemáticas . 324 : 84-117. arXiv : 1606.02056 . doi : 10.1016/j.aim.2017.11.003. ISSN  0001-8708.
8. Barrett, Jordania Mitchell; Lupini, Martín; Moreira, Joel (mayo de 2021). "Sobre las condiciones de Rado para ecuaciones diofánticas no lineales". Revista europea de combinatoria . 94 : 103277. arXiv : 1907.06163 . doi :10.1016/j.ejc.2020.103277. ISSN  0195-6698.

Lectura adicional

• Vitaly Bergelson , N. Hindman Las estructuras regulares de partición contenidas en conjuntos grandes son abundantes J. Comb. Theory A 93 (2001), 18–36.