Regularidad de partición

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

Dado un conjunto${\displaystyle X}$, una colección de subconjuntos${\displaystyle \mathbb {S} \subset {\mathcal {P}}(X)}$Se denomina partición regular si cada conjunto A en la colección tiene la propiedad de que, sin importar cómo se particione 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${\displaystyle A\in \mathbb {S} }$y cualquier partición finita${\displaystyle A=C_{1}\cup C_{2}\cup \cdots \cup C_{n}}$, existe un i  ≤ n tal que ${\displaystyle C_{i}}$pertenece a${\displaystyle \mathbb {S} }$. La teoría de Ramsey se caracteriza a veces como el estudio de qué colecciones${\displaystyle \mathbb {S} }$son particiones regulares.

• El conjunto 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 toda partición finita de un conjunto infinito tiene una celda infinita (es decir, el principio del palomar infinito ).
• Conjuntos con densidad superior positiva en${\displaystyle \mathbb {N} }$: la densidad superior${\displaystyle {\overline {d}}(A)}$de${\displaystyle A\subset \mathbb {N} }$se define como${\displaystyle {\overline {d}}(A)=\limsup _{n\rightarrow \infty }{\frac {|\{1,2,\ldots ,n\}\cap A|}{n}}.}$( Teorema de Szemerédi )
• Para cualquier ultrafiltro${\displaystyle \mathbb {U} }$en un plató${\displaystyle X}$,${\displaystyle \mathbb {U} }$es partición regular: para cualquier${\displaystyle A\in \mathbb {U} }$, si${\displaystyle A=C_{1}\sqcup \cdots \sqcup C_{n}}$, entonces exactamente uno${\displaystyle C_{i}\in \mathbb {U} }$.
• Conjuntos de recurrencia: un conjunto R de enteros se denomina conjunto de recurrencia si para cualquier transformación que preserve la medida${\displaystyle T}$del espacio de probabilidad ( Ω , β , μ ) y${\displaystyle A\in \beta }$de medida positiva hay un valor distinto de cero${\displaystyle n\in R}$de modo que${\displaystyle \mu (A\cap T^{n}A)>0}$.
• Se denomina subconjunto de números naturales ap-rico si contiene progresiones aritméticas de longitud arbitraria . Entonces, la colección de subconjuntos ap-ricos es particionable regular ( Van der Waerden , 1927).
• Dejar${\displaystyle [A]^{n}}$sea ​​el conjunto de todos los n- subconjuntos de${\displaystyle A\subset \mathbb {N} }$. Dejar${\displaystyle \mathbb {S} ^{n}=\bigcup _{A\subset \mathbb {N} }^{}[A]^{n}}$. Para cada n ,${\displaystyle \mathbb {S} ^{n}}$es una partición regular. ( Ramsey , 1930).
• Para cada cardinal infinito${\displaystyle \kappa }$, la colección de juegos de papelería de${\displaystyle \kappa }$es una partición regular. Más es cierto: si${\displaystyle S}$es estacionario y${\displaystyle S=\bigcup _{\alpha <\lambda }S_{\alpha }}$para algunos${\displaystyle \lambda <\kappa}$, luego algunos${\displaystyle S_{\alpha }}$está estacionario.
• La colección de${\displaystyle \Delta }$-conjuntos:${\displaystyle A\subset \mathbb {N} }$es un${\displaystyle \Delta }$-establecer si${\displaystyle A}$contiene el conjunto de diferencias${\displaystyle \{s_{m}-s_{n}:m,n\in \mathbb {N} ,\,n<m\}}$para alguna secuencia${\displaystyle \langle s_ {n}\rangle _ {n=1}^{\infty }}$.
• El conjunto de barreras en${\displaystyle \mathbb {N} }$: llamar a una colecta${\displaystyle \mathbb {B} }$de subconjuntos finitos de${\displaystyle \mathbb {N} }$una barrera si:
  • ${\displaystyle \forall X,Y\in \mathbb {B} ,X\not \subset Y}$y
  • para todos los infinitos${\displaystyle I\subset \cup \mathbb {B} }$, hay algunos${\displaystyle X\in \mathbb {B} }$de tal manera que los elementos de X sean los elementos más pequeños de I; es decir,${\displaystyle X\subset I}$y${\displaystyle \forall i\in I\setminus X,\forall x\in X,x<i}$.

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

• Productos finitos de árboles infinitos ( Halpern–Läuchli , 1966)
• Conjuntos sindéticos por partes (Brown, 1968) ^{[ 2 ]}
• Se denomina ip-rico a un subconjunto de números naturales si contiene conjuntos finitos arbitrariamente grandes junto con todas sus sumas finitas. Entonces, la colección de subconjuntos ip-ricos es particionada regular ( Jon Folkman , Richard Rado y J. Sanders, 1968). ^{[ 3 ]}
• conjuntos ( m , p , c ) ^{[ 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${\displaystyle \beta \mathbb {N} }$, la compactificación de Stone-Čech de los números enteros. (Furstenberg, 1981, véase también Hindman, Strauss, 1998)

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

• Bergelson, Vitaly ; Hindman, Neil (2001). "Las estructuras regulares de partición contenidas en conjuntos grandes son abundantes" . Journal of Combinatorial Theory . Serie A. 93 (1): 18–36 . doi : 10.1006/jcta.2000.3061 .