Partition regularity without the columns property. (English) Zbl 1314.05207
Summary: 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.
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.
MSC:
| 05D10 | Ramsey theory |
References:
| [1] | Argabright, L. N.; Wilde, C. O., Semigroups satisfying a strong F\o lner condition, Proc. Amer. Math. Soc., 18, 587-591 (1967) · Zbl 0152.33302 |
| [2] | Barber, Ben; Hindman, Neil; Leader, Imre, Partition regularity in the rationals, J. Combin. Theory Ser. A, 120, 7, 1590-1599 (2013) · Zbl 1314.05017 · doi:10.1016/j.jcta.2013.05.011 |
| [3] | Dales, H. G.; Lau, A. T.-M.; Strauss, D., Banach algebras on semigroups and on their compactifications, Mem. Amer. Math. Soc., 205, 966, vi+165 pp. (2010) · Zbl 1192.43001 · doi:10.1090/S0065-9266-10-00595-8 |
| [4] | Furstenberg, H., Recurrence in ergodic theory and combinatorial number theory, xi+203 pp. (1981), Princeton University Press, Princeton, N.J. · Zbl 0459.28023 |
| [5] | Hindman, Neil, Finite sums from sequences within cells of a partition of \(N\), J. Combinatorial Theory Ser. A, 17, 1-11 (1974) · Zbl 0285.05012 |
| [6] | Hindman, Neil; Leader, Imre; Strauss, Dona, Infinite partition regular matrices: solutions in central sets, Trans. Amer. Math. Soc., 355, 3, 1213-1235 (2003) · Zbl 1006.05058 · doi:10.1090/S0002-9947-02-03191-4 |
| [7] | Hindman, Neil; Leader, Imre; Strauss, Dona, Open problems in partition regularity, Combin. Probab. Comput., 12, 5-6, 571-583 (2003) · Zbl 1061.05095 · doi:10.1017/S0963548303005716 |
| [8] | Hindman, Neil; Strauss, Dona, Density in arbitrary semigroups, Semigroup Forum, 73, 2, 273-300 (2006) · Zbl 1111.22004 · doi:10.1007/s00233-006-0622-5 |
| [9] | Hindman, Neil; Strauss, Dona, Sets satisfying the central sets theorem, Semigroup Forum, 79, 3, 480-506 (2009) · Zbl 1192.43004 · doi:10.1007/s00233-009-9179-4 |
| [10] | Hindman, Neil; Strauss, Dona, Density and invariant means in left amenable semigroups, Topology Appl., 156, 16, 2614-2628 (2009) · Zbl 1189.22003 · doi:10.1016/j.topol.2009.04.016 |
| [11] | Hindman, Neil; Strauss, Dona, Algebra in the Stone-\v Cech compactification, de Gruyter Textbook, xviii+591 pp. (2012), Walter de Gruyter & Co., Berlin · Zbl 1241.22001 |
| [12] | Milliken, Keith R., Ramsey’s theorem with sums or unions, J. Combinatorial Theory Ser. A, 18, 276-290 (1975) · Zbl 0323.05001 |
| [13] | Rado, Richard, Studien zur Kombinatorik, Math. Z., 36, 1, 424-470 (1933) · Zbl 0006.14603 · doi:10.1007/BF01188632 |
| [14] | [S] I.Schur, \"Uber die Kongruenz \(x^m+y^m=z^m\ \pmod p\), Jahresbericht der Deutschen Math.-Verein.25 (1916), 114-117. · JFM 46.0193.02 |
| [15] | Taylor, Alan D., A canonical partition relation for finite subsets of \(\omega \), J. Combinatorial Theory Ser. A, 21, 2, 137-146 (1976) · Zbl 0341.05010 |
| [16] | [W] B.van der Waerden, Beweis einer Baudetschen Vermutung, Nieuw Arch.Wiskunde 19 (1927), 212-216. \endbiblist · 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.
