Infinite partition regular matrices: solutions in central sets

Authors:
Neil Hindman, Imre Leader and Dona Strauss

Journal:
Trans. Amer. Math. Soc. **355** (2003), 1213-1235

MSC (2000):
Primary 05D10; Secondary 22A15, 54H13

DOI:
https://doi.org/10.1090/S0002-9947-02-03191-4

Published electronically:
November 7, 2002

MathSciNet review:
1938754

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: 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.

- Walter Deuber,
*Partitionen und lineare Gleichungssysteme*, Math. Z.**133**(1973), 109–123 (German). MR**325406**, DOI https://doi.org/10.1007/BF01237897 - Walter A. Deuber, Neil Hindman, Imre Leader, and Hanno Lefmann,
*Infinite partition regular matrices*, Combinatorica**15**(1995), no. 3, 333–355. MR**1357280**, DOI https://doi.org/10.1007/BF01299740 - H. Furstenberg,
*Recurrence in ergodic theory and combinatorial number theory*, Princeton University Press, Princeton, N.J., 1981. M. B. Porter Lectures. MR**603625** - 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. MR**1044995** - Neil Hindman and Imre Leader,
*Image partition regularity of matrices*, Combin. Probab. Comput.**2**(1993), no. 4, 437–463. MR**1264718**, DOI https://doi.org/10.1017/S0963548300000821 - 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. MR**1874760**, DOI https://doi.org/10.1016/S0012-365X%2801%2900276-X - 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. MR**1642231** - Keith R. Milliken,
*Ramsey’s theorem with sums or unions*, J. Combinatorial Theory Ser. A**18**(1975), 276–290. MR**373906**, DOI https://doi.org/10.1016/0097-3165%2875%2990039-4 - R. Rado,
*Studien zur Kombinatorik*, Math. Zeit.**36**(1933), 242-280. - I. Schur,
*Über die Kongruenz $x^m+y^m=z^m (\operatorname {mod} p)$*, Jahresbericht der Deutschen Math.-Verein.**25**(1916), 114-117. - Alan D. Taylor,
*A canonical partition relation for finite subsets of $\omega $*, J. Combinatorial Theory Ser. A**21**(1976), no. 2, 137–146. MR**424571**, DOI https://doi.org/10.1016/0097-3165%2876%2990058-3 - B. van der Waerden,
*Beweis einer Baudetschen Vermutung*, Nieuw Arch. Wiskunde**19**(1927), 212-216.

Retrieve articles in *Transactions of the American Mathematical Society*
with MSC (2000):
05D10,
22A15,
54H13

Retrieve articles in all journals with MSC (2000): 05D10, 22A15, 54H13

Additional Information

**Neil Hindman**

Affiliation:
Department of Mathematics, Howard University, Washington, DC 20059

MR Author ID:
86085

Email:
nhindman@aol.com

**Imre Leader**

Affiliation:
Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Cambridge CB2 1SB, United Kingdom

MR Author ID:
111480

Email:
I.Leader@dpmms.cam.ac.uk

**Dona Strauss**

Affiliation:
Department of Pure Mathematics, University of Hull, Hull HU6 7RX, United Kingdom

Email:
d.strauss@maths.hull.ac.uk

Received by editor(s):
May 10, 2001

Published electronically:
November 7, 2002

Additional Notes:
The first author acknowledges support received from the National Science Foundation (USA) via grant DMS-0070593.

Article copyright:
© Copyright 2002
American Mathematical Society