Ramsey theorem for trees with successor operation

Autor:	Balko, Martin, Chodounský, David, Dobrinen, Natasha, Hubička, Jan, Konečný, Matěj, Nešetřil, Jaroslav, Zucker, Andy
Rok vydání:	2023
Předmět:	Mathematics - Combinatorics Computer Science - Discrete Mathematics Mathematics - Logic 05D10 05C05 05C65 05C55 G.2.2 F.4.1
Druh dokumentu:	Working Paper
Popis:	We prove a general Ramsey theorem for trees with a successor operation. This theorem is a common generalization of the Carlson-Simpson Theorem and the Milliken Tree Theorem for regularly branching trees. Our theorem has a number of applications both in finite and infinite combinatorics. For example, we give a short proof of the unrestricted Ne\v{s}et\v{r}il-R\"odl theorem, and we recover the Graham-Rothschild theorem. Our original motivation came from the study of big Ramsey degrees - various trees used in the study can be viewed as trees with a successor operation. To illustrate this, we give a non-forcing proof of a theorem of Zucker on big Ramsey degrees. Comment: 37 pages, 9 figures
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2311.06872 Zobrazit plný text záznamu View this record from Arxiv