×

Infinite partition regular matrices: Solutions in central sets. (English) Zbl 1006.05058

Summary: A finite or infinite matrix \(A\) is image partition regular provided that whenever \(\mathbb{N}\) is finitely colored, there must be some \(\vec{x}\) with entries from \(\mathbb{N}\) such that all entries of \(A\vec{x}\) are in the same color class. In contrast to the finite case, infinite image partition regular matrices seem very hard to analyze: they do not enjoy the closure and consistency properties of the finite case, and it is difficult to construct new ones from old. In this paper we introduce the stronger notion of central image partition regularity, meaning that \(A\) must have images in every central subset of \(\mathbb{N}\). We describe some classes of centrally image partition regular matrices and investigate the extent to which they are better behaved than ordinary image partition regular matrices. It turns out that the centrally image partition regular matrices are closed under some natural operations, and this allows us to give new examples of image partition regular matrices. In particular, we are able to solve a vexing open problem by showing that whenever \(\mathbb{N}\) is finitely colored, there must exist injective sequences \(\langle x_n\rangle_{n=0}^\infty\) and \(\langle z_n\rangle_{n=0}^\infty\) in \(\mathbb{N}\) with all sums of the forms \(x_n+x_m\) and \(z_n+2z_m\) with \(n<m\) in the same color class. This is the first example of an image partition regular system whose regularity is not guaranteed by the Milliken-Taylor theorem, or variants thereof.

MSC:

05D10 Ramsey theory
22A15 Structure of topological semigroups
54H13 Topological fields, rings, etc. (topological aspects)
Full Text: DOI

References:

[1] Walter Deuber, Partitionen und lineare Gleichungssysteme, Math. Z. 133 (1973), 109 – 123 (German). · Zbl 0254.05011 · doi:10.1007/BF01237897
[2] Walter A. Deuber, Neil Hindman, Imre Leader, and Hanno Lefmann, Infinite partition regular matrices, Combinatorica 15 (1995), no. 3, 333 – 355. · Zbl 0831.05060 · doi:10.1007/BF01299740
[3] H. Furstenberg, Recurrence in ergodic theory and combinatorial number theory, Princeton University Press, Princeton, N.J., 1981. M. B. Porter Lectures. · Zbl 0459.28023
[4] Ronald L. Graham, Bruce L. Rothschild, and Joel H. Spencer, Ramsey theory, 2nd ed., Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., New York, 1990. A Wiley-Interscience Publication. · Zbl 0705.05061
[5] Neil Hindman and Imre Leader, Image partition regularity of matrices, Combin. Probab. Comput. 2 (1993), no. 4, 437 – 463. · Zbl 0793.05139 · doi:10.1017/S0963548300000821
[6] Neil Hindman, Imre Leader, and Dona Strauss, Image partition regular matrices — bounded solutions and preservation of largeness, Discrete Math. 242 (2002), no. 1-3, 115 – 144. · Zbl 1007.05095 · doi:10.1016/S0012-365X(01)00276-X
[7] Neil Hindman and Dona Strauss, Algebra in the Stone-Čech compactification, De Gruyter Expositions in Mathematics, vol. 27, Walter de Gruyter & Co., Berlin, 1998. Theory and applications. · Zbl 0918.22001
[8] Keith R. Milliken, Ramsey’s theorem with sums or unions, J. Combinatorial Theory Ser. A 18 (1975), 276 – 290. · Zbl 0323.05001
[9] R. Rado, Studien zur Kombinatorik, Math. Zeit. 36 (1933), 242-280. · Zbl 0006.14603
[10] I. Schur, Über die Kongruenz \(x^m+y^m=z^m ({\textup{mod}}p)\), Jahresbericht der Deutschen Math.-Verein. 25 (1916), 114-117. · JFM 46.0193.02
[11] Alan D. Taylor, A canonical partition relation for finite subsets of \?, J. Combinatorial Theory Ser. A 21 (1976), no. 2, 137 – 146. · Zbl 0341.05010
[12] B. van der Waerden, Beweis einer Baudetschen Vermutung, Nieuw Arch. Wiskunde 19 (1927), 212-216. · JFM 53.0073.12
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.