A finite or infinite matrix $A$ with rational entries is called partition regular if whenever the natural numbers are finitely coloured there is a monochromatic vector $x$ with $Ax=0$. Many of the classical theorems of Ramsey Theory may naturally be interpreted as assertions that particular matrices are partition regular. In the finite case, Rado proved that a matrix is partition regular if and only it satisfies a computable condition known as the columns property. The first requirement of the columns property is that some set of columns sums to zero.
In the infinite case, much less is known. There are many examples of matrices with the columns property that are not partition regular, but until now all known examples of partition regular matrices did have the columns property. Our main aim in this paper is to show that, perhaps surprisingly, there are infinite partition regular matrices without the columns property — in fact, having no set of columns summing to zero.
We also make a conjecture that if a partition regular matrix (say with integer coefficients) has bounded row sums then it must have the columns property, and prove a first step towards this.
- L. N. Argabright and C. O. Wilde, Semigroups satisfying a strong Følner condition, Proc. Amer. Math. Soc. 18 (1967), 587–591. MR 210797, DOI 10.1090/S0002-9939-1967-0210797-2
- Ben Barber, Neil Hindman, and Imre Leader, Partition regularity in the rationals, J. Combin. Theory Ser. A 120 (2013), no. 7, 1590–1599. MR 3092686, DOI 10.1016/j.jcta.2013.05.011
- H. G. Dales, A. T.-M. Lau, and D. Strauss, Banach algebras on semigroups and on their compactifications, Mem. Amer. Math. Soc. 205 (2010), no. 966, vi+165. MR 2650729, DOI 10.1090/S0065-9266-10-00595-8
- H. Furstenberg, Recurrence in ergodic theory and combinatorial number theory, Princeton University Press, Princeton, N.J., 1981. M. B. Porter Lectures. MR 603625
- Neil Hindman, Finite sums from sequences within cells of a partition of $N$, J. Combinatorial Theory Ser. A 17 (1974), 1–11. MR 349574, DOI 10.1016/0097-3165(74)90023-5
- Neil Hindman, Imre Leader, and Dona Strauss, Infinite partition regular matrices: solutions in central sets, Trans. Amer. Math. Soc. 355 (2003), no. 3, 1213–1235. MR 1938754, DOI 10.1090/S0002-9947-02-03191-4
- Neil Hindman, Imre Leader, and Dona Strauss, Open problems in partition regularity, Combin. Probab. Comput. 12 (2003), no. 5-6, 571–583. Special issue on Ramsey theory. MR 2037071, DOI 10.1017/S0963548303005716
- Neil Hindman and Dona Strauss, Density in arbitrary semigroups, Semigroup Forum 73 (2006), no. 2, 273–300. MR 2280825, DOI 10.1007/s00233-006-0622-5
- Neil Hindman and Dona Strauss, Sets satisfying the central sets theorem, Semigroup Forum 79 (2009), no. 3, 480–506. MR 2564059, DOI 10.1007/s00233-009-9179-4
- Neil Hindman and Dona Strauss, Density and invariant means in left amenable semigroups, Topology Appl. 156 (2009), no. 16, 2614–2628. MR 2561213, DOI 10.1016/j.topol.2009.04.016
- Neil Hindman and Dona Strauss, Algebra in the Stone-Čech compactification, De Gruyter Textbook, Walter de Gruyter & Co., Berlin, 2012. Theory and applications; Second revised and extended edition [of MR1642231]. MR 2893605
- Keith R. Milliken, Ramsey’s theorem with sums or unions, J. Combinatorial Theory Ser. A 18 (1975), 276–290. MR 373906, DOI 10.1016/0097-3165(75)90039-4
- Richard Rado, Studien zur Kombinatorik, Math. Z. 36 (1933), no. 1, 424–470 (German). MR 1545354, DOI 10.1007/BF01188632
- I. Schur, Über die Kongruenz $x^m+y^m=z^m\ \pmod 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 10.1016/0097-3165(76)90058-3
- B. van der Waerden, Beweis einer Baudetschen Vermutung, Nieuw Arch. Wiskunde 19 (1927), 212–216.
- Ben Barber
- Affiliation: School of Mathematics, University of Birmingham, Edgbaston, Birmingham, B15 2TT, United Kingdom
- Email: firstname.lastname@example.org
- Neil Hindman
- Affiliation: Department of Mathematics, Howard University, Washington, DC 20059
- MR Author ID: 86085
- Email: email@example.com
- Imre Leader
- Affiliation: Department of Pure Mathematics and Mathematical Statistics, Centre for Mathematical Sciences, Wilberforce Road, Cambridge, CB3 0WB, United Kingdom
- MR Author ID: 111480
- Email: firstname.lastname@example.org
- Dona Strauss
- Affiliation: Department of Pure Mathematics, University of Leeds, Leeds LS2 9J2, United Kingdom
- Email: email@example.com
- Received by editor(s): January 6, 2014
- Received by editor(s) in revised form: April 4, 2014
- Published electronically: February 20, 2015
- Additional Notes: The second author acknowledges support received from the National Science Foundation (USA) via Grant DMS-1160566.
- Communicated by: Patricia L. Hersh
- © Copyright 2015 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 143 (2015), 3387-3399
- MSC (2010): Primary 05D10
- DOI: https://doi.org/10.1090/S0002-9939-2015-12519-1
- MathSciNet review: 3348781