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

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

Учитывая набор ${\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} }$ являются регулярными разделами.

Примеры

• совокупность всех бесконечных подмножеств бесконечного множества Икс это типичный пример. В этом случае регулярность разбиения утверждает, что каждое конечное разбиение бесконечного множества имеет бесконечную ячейку (т.е. принцип голубятни.)
• множества с положительной верхней плотностью в ${\displaystyle \mathbb {N} }$: the верхняя плотность ${\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}}.}$ (Теорема Семереди )
• Для любого ультрафильтр ${\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} }$.
• множеств повторения: множество R целых чисел называется набор повторений если по какой-либо мере сохраняющее преобразование ${\displaystyle T}$ вероятностного пространства (Ω, β, μ) и ${\displaystyle A\in \ \beta }$ положительной меры существует ненулевое ${\displaystyle n\in R}$ так что ${\displaystyle \mu (A\cap T^{n}A)>0}$.
• Назовите подмножество натуральных чисел богатый на п.п. если он содержит сколь угодно длинные арифметические прогрессии. Тогда набор п.п.-богатых подмножеств является регулярным по разбиению (Ван дер Варден, 1927).
• Позволять ${\displaystyle [A]^{n}}$ быть набором всех п-подмножества ${\displaystyle A\subset \mathbb {N} }$. Позволять ${\displaystyle \mathbb {S} ^{n}=\bigcup _{A\subset \mathbb {N} }^{}[A]^{n}}$. Для каждого n, ${\displaystyle \mathbb {S} ^{n}}$ раздел регулярный. (Рэмси, 1930).
• Для каждого бесконечного кардинала ${\displaystyle \kappa }$, собрание стационарные наборы из ${\displaystyle \kappa }$ раздел регулярный. Верно больше: если ${\displaystyle S}$ стационарный и ${\displaystyle S=\bigcup _{\alpha <\lambda }S_{\alpha }}$ для некоторых ${\displaystyle \lambda <\kappa }$, то некоторые ${\displaystyle S_{\alpha }}$ стационарный.
• сборник ${\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}^{\omega }}$.
• комплекс барьеров на ${\displaystyle \mathbb {N} }$: вызвать коллекцию ${\displaystyle \mathbb {B} }$ конечных подмножеств ${\displaystyle \mathbb {N} }$ а барьер если:
  • ${\displaystyle \forall X,Y\in \mathbb {B} ,X\not \subset Y}$ и
  • для всего бесконечного ${\displaystyle I\subset \cup \mathbb {B} }$, существует некоторое ${\displaystyle X\in \mathbb {B} }$ такие, что элементы X являются наименьшими элементами I; т.е. ${\displaystyle X\subset I}$ и ${\displaystyle \forall i\in I\setminus X,\forall x\in X,x<i}$.

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

• конечные произведения бесконечных деревьев (Halpern – Läuchli, 1966)
• кусочно-синдетические множества (Браун, 1968)
• Назовите подмножество натуральных чисел i.p. богатый если он содержит сколь угодно большие конечные множества вместе со всеми их конечными суммами. Тогда набор i.p.-богатых подмножеств является регулярным по разбиению (Folkman –Rado –Сандерс, 1968).
• (м, п, c) -наборы (Deuber, 1973)
• Наборы IP (Hindman, 1974, см. Также Hindman, Strauss, 1998)
• MT^k наборы для каждого k, т.е. k-наборы конечных сумм (Милликен – Тейлор, 1975)
• центральные наборы; т.е. члены любого минимального идемпотента в ${\displaystyle \beta \mathbb {N} }$, то Каменно-чешская компактификация целых чисел. (Furstenberg, 1981, см. Также Hindman, Strauss, 1998)

Рекомендации

1. Виталий Бергельсон, Н. Хиндман Регулярные структуры разбиения, содержащиеся в больших наборах, многочисленны J. Comb. Теория А 93 (2001), 18–36.
2. Т. Браун, Интересный комбинаторный метод теории локально конечных полугрупп, Pacific J. Math. 36, нет. 2 (1971), 285–289.
3. В. Дойбер, Mathematische Zeitschrift 133, (1973) 109–123
4. Н. Хиндман, Конечные суммы из последовательностей внутри ячеек раздела N, J. Comb. Теория А 17 (1974) 1–11.
5. C.St.J.A. Нэш-Вильямс, О хорошо квазиупорядоченных трансфинитных последовательностях, Proc. Camb. Фил. Soc. 61 (1965), 33–39.
6. Н. Хиндман, Д. Штраус, Алгебра в компактификации Стоуна – Чеха, De Gruyter, 1998
7. Дж. Сандерс, Обобщение теоремы Шура, докторская диссертация, Йельский университет, 1968.