Регулярность разбиения

В комбинаторике , разделе математики , регулярность разбиения является одним из понятий размера набора множеств .

Учитывая набор $X$, набор подмножеств $\mathbb {S} \subset {\mathcal {P}}(X)$ называется регулярным разбиением, если каждое множество A в коллекции обладает свойством, что независимо от того, как A разбито на конечное число подмножеств, по крайней мере одно из подмножеств также будет принадлежать коллекции. То есть,для любого $A\in \mathbb {S}$и любое конечное разбиение $A=C_{1}\cup C_{2}\cup \cdots \cup C_{n}$, существует i ⩽ n такое, что $C_{i}$ принадлежит $\mathbb {S}$. Теорию Рамсея иногда характеризуют как исследование того, какие коллекции $\mathbb {S}$ являются регулярными разделами.

Примеры

• Коллекция всех бесконечных подмножеств бесконечного множества X является типичным примером. В этом случае регулярность разбиения утверждает, что каждое конечное разбиение бесконечного множества имеет бесконечную ячейку (т.е. принцип бесконечной ячейки ).
• Множества с положительной верхней плотностью в $\mathbb {N}$: верхняя плотность ${\overline {d}}(A)$ из $A\subset \mathbb {N}$ определяется как ${\overline {d}}(A)=\limsup _{n\rightarrow \infty }{\frac {|\{1,2,\ldots ,n\}\cap A|}{n}}.$ ( теорема Семереди )
• Для любого ультрафильтра $\mathbb {U}$ на съемочной площадке $X$, $\mathbb {U}$ является ли раздел регулярным: для любого $A\in \mathbb {U}$, если $A=C_{1}\sqcup \cdots \sqcup C_{n}$, то ровно один $C_{i}\in \mathbb {U}$.
• Наборы рекуррентности: набор R целых чисел называется набором рекуррентности, если для любого преобразования, сохраняющего меру, $T$ вероятностного пространства (Ω, β , µ ) и $A\in \beta$ положительной меры существует ненулевое $n\in R$ так что $\mu (A\cap T^{n}A)>0$.
• Подмножество натуральных чисел назовем ап-богатым , если оно содержит арифметические прогрессии произвольной длины . Тогда совокупность ар-богатых подмножеств является регулярной по разделам ( Ван дер Варден , 1927).
• Позволять $[A]^{n}$ быть множеством всех n -подмножеств $A\subset \mathbb {N}$. Позволять $\mathbb {S} ^{n}=\bigcup _{A\subset \mathbb {N} }^{}[A]^{n}$. Для n каждого $\mathbb {S} ^{n}$ является ли раздел регулярным. ( Рэмзи , 1930).
• Для каждого бесконечного кардинала $\kappa$, коллекция стационарных наборов $\kappa$ является ли раздел регулярным. Более верно: если $S$ является стационарным и $S=\bigcup _{\alpha <\lambda }S_{\alpha }$ для некоторых $\lambda <\kappa$, затем немного $S_{\alpha }$ является стационарным.
• Коллекция $\Delta$-наборы: $A\subset \mathbb {N}$ это $\Delta$-установить, если $A$ содержит набор различий $\{s_{m}-s_{n}:m,n\in \mathbb {N} ,\,n<m\}$ для некоторой последовательности $\langle s_{n}\rangle _{n=1}^{\infty }$.
• Набор барьеров на $\mathbb {N}$: вызвать сбор $\mathbb {B}$ конечных подмножеств $\mathbb {N}$ барьер , если:
  • $\forall X,Y\in \mathbb {B} ,X\not \subset Y$ и
  • для всех бесконечных $I\subset \cup \mathbb {B}$, есть некоторые $X\in \mathbb {B}$ такие, что элементы X являются наименьшими элементами I; т.е. $X\subset I$ и $\forall i\in I\setminus X,\forall x\in X,x<i$.

Это обобщает теорему Рамсея , поскольку каждый $[A]^{n}$ является барьером. ( Нэш-Уильямс , 1965)

• Конечные произведения бесконечных деревьев ( Хальперн-Ляухли , 1966)
• Кусочно-синдетические множества (Браун, 1968)
• Подмножество натуральных чисел называется ip-богатым , если оно содержит сколь угодно большие конечные множества вместе со всеми их конечными суммами. Тогда совокупность подмножеств, богатых ip, является регулярной по разделам ( Джон Фолкман , Ричард Радо и Дж. Сандерс, 1968).
• ( m , p , c )-множества
• IP-наборы
• МТ ^к наборы для каждого k , т.е. k -кортежи конечных сумм (Милликен – Тейлор, 1975)
• Центральные наборы; т.е. члены любого минимального идемпотента в $\beta \mathbb {N}$, компактификация Стоуна – Чеха целых чисел. (Фюрстенберг, 1981, см. также Хиндман, Штраус, 1998).

Диофантовы уравнения

Диофантово уравнение $P(\mathbf {x} )=0$ называется регулярным разбиением, если совокупность всех бесконечных подмножеств $\mathbb {N}$ содержащая решение, является регулярным по разбиению. Теорема Радо какие именно системы линейных характеризует , диофантовых уравнений $\mathbf {A} \mathbf {x} =\mathbf {0}$ являются регулярными разделами. В последнее время был достигнут большой прогресс в классификации нелинейных диофантовых уравнений.

Дальнейшее чтение

• Виталий Бергельсон , Н. Хиндман. Регулярные структуры разбиения, содержащиеся в больших множествах, широко распространены Дж. Комб. Теория А 93 (2001), 18–36.