Теорема Милликена–Тейлора

В математике теорема Милликена–Тейлора в комбинаторике является обобщением теоремы Рамсея и теоремы Хиндмана . Она названа в честь Кита Милликена и Алана Д. Тейлора .

Пусть обозначает множество конечных подмножеств , и определяет частичный порядок на α<β тогда и только тогда, когда max α<min β. Дана последовательность целых чисел и k > 0 , пусть ${\mathcal {P}}_{f}(\mathbb {N} )$ $\mathbb {N}$ ${\mathcal {P}}_{f}(\mathbb {N} )$ $\langle a_{n}\rangle _{n=0}^{\infty }\subset \mathbb {N}$

[FS(\langle a_{n}\rangle _{n=0}^{\infty })]_{<}^{k}=\left\{\left\{\sum _{t\in \alpha _{1}}a_{t},\ldots ,\sum _{t\in \alpha _{k}}a_{t}\right\}:\alpha _{1},\cdots ,\alpha _{k}\in {\mathcal {P}}_{f}(\mathbb {N} ){\text{ и }}\alpha _{1}<\cdots <\alpha _{k}\right\}.

Пусть обозначают k -элементные подмножества множества S. Теорема Милликена–Тейлора утверждает, что для любого конечного разбиения существуют некоторые i ≤ r и последовательность такие, что . $[S]^{k}$ $[\mathbb {N} ]^{k}=C_{1}\cup C_{2}\cup \cdots \cup C_{r}$ $\langle a_{n}\rangle _{n=0}^{\infty }\subset \mathbb {N}$ $[FS(\langle a_{n}\rangle _{n=0}^{\infty})]_{<}^{k}\subset C_{i}$

Для каждого назовем набор MT ^k . Тогда, в качестве альтернативы, теорема Милликена–Тейлора утверждает, что совокупность наборов MT k ^{является} регулярной для каждого k . $\langle a_{n}\rangle _{n=0}^{\infty }\subset \mathbb {N}$ $[FS(\langle a_{n}\rangle _{n=0}^{\infty })]_{<}^{k}$

Ссылки

Милликен, Кит Р. (1975), «Теорема Рамсея с суммами или объединениями», Журнал комбинаторной теории , Серия A, 18 (3): 276–290, doi : 10.1016/0097-3165(75)90039-4 , MR 0373906.
Тейлор, Алан Д. (1976), «Каноническое отношение разбиения для конечных подмножеств ω», Журнал комбинаторной теории , Серия A, 21 (2): 137–146, doi :10.1016/0097-3165(76)90058-3, MR 0424571.