Extensions of Infinite Partition Regular Systems
Open Access
- 14 April 2015
- journal article
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 22 (2) , P2.29
Abstract
A finite or infinite matrix $A$ with rational entries (and only finitely many non-zero entries in each row) is called image partition regular if, whenever the natural numbers are finitely coloured, there is a vector $x$, with entries in the natural numbers, such that $Ax$ is monochromatic. Many of the classicial results of Ramsey theory are naturally stated in terms of image partition regularity.Our aim in this paper is to investigate maximality questions for image partition regular matrices. When is it possible to add rows on to $A$ and remain image partition regular? When can one add rows but `nothing new is produced'? What about adding rows and also new variables? We prove some results about extensions of the most interesting infinite systems, and make several conjectures.Our most surprising positive result is a compatibility result for Milliken-Taylor systems, stating that (in many cases) one may adjoin one Milliken-Taylor system to a translate of another and remain image partition regular. This is in contrast to earlier results, which had suggested a strong inconsistency between different Milliken-Taylor systems. Our main tools for this are some algebraic properties of $\beta {\mathbb N}$, the Stone-Čech compactification of the natural numbers.
Keywords
This publication has 11 references indexed in Scilit:
- Partition regularity without the columns propertyProceedings of the American Mathematical Society, 2015
- Partition regularity in the rationalsJournal of Combinatorial Theory, Series A, 2013
- SEPARATING MILLIKEN–TAYLOR SYSTEMS WITH NEGATIVE ENTRIESProceedings of the Edinburgh Mathematical Society, 2003
- Infinite partition regular matricesCombinatorica, 1995
- Image Partition Regularity of MatricesCombinatorics, Probability and Computing, 1993
- Partitions and sums of (m, p, c)-setsJournal of Combinatorial Theory, Series A, 1987
- A canonical partition relation for finite subsets of ωJournal of Combinatorial Theory, Series A, 1976
- Ramsey's theorem with sums or unionsJournal of Combinatorial Theory, Series A, 1975
- Finite sums from sequences within cells of a partition of NJournal of Combinatorial Theory, Series A, 1974
- Partitionen und lineare GleichungssystemeMathematische Zeitschrift, 1973