No label defined (Q4359495)

In 1930 Ramsey published his paper ``On a problem in formal logic'' [\textit{F. P. Ramsey}, Proc. Lond. Math. Soc. (2) 30, 264-286 (1930; JFM 55.0032.04)]. He established a result, nowadays known as Ramsey's theorem: Let \(k\) and \(r\) be positive integers. Then for every \(r\)-coloring of the \(k\)-element subsets of \(\omega\) there exists an infinite subset \(S\subseteq\omega\) such that all \(k\)-element subsets of \(S\) are colored the same. Already in 1927 van der Waerden published his theorem on arithmetic progressions [\textit{B. L. van der Waerden}, Nieuw Arch. Wisk. 15, 212-216 (1927; JFM 53.0073.04)]. He proved that for every coloring of the natural numbers with finitely many colors there exists a monochromatic arithmetic progression of given length. Van der Waerden's result can be seen in the context of Schur's investigations on the distribution of quadratic residues and nonresidues. Schur knew about the existence of monochromatic solutions of \(x+y=z\). He worked on such problems in order to resolve Fermat's conjecture, which was proved by Wiles in 1994. The above-mentioned works of Ramsey and of van der Waerden gave rise to the part of discrete mathematics, known as Ramsey theory or partition theory. An important contribution was made by Rado in 1933. Working on his dissertation, supervised by Schur, he was able to prove a common generalization of Schur's and van der Waerden's results by introducing the concept of regularity: A system of linear equation \(A\vec x=\vec 0\) is called regular over a ring \(R\) if it has monochromatic solutions for every coloring of \(R\) with finitely many colors. In his ``Studien zur Kombinatorik'' [Math. Z. 36, 424-480 (1933; Zbl 0006.14603)], \textit{R. Rado} gave a complete characterization of all regular systems of linear equations over the rational numbers. The property Rado used in order to describe regular systems of linear equations is an syntactical property of the matrix. It is characterized by certain linear dependences of the columns of the matrix \(A\) and is called column property. It is possible to generalize the concept of regularity to systems of linear inequalities. We call a system of linear inequalities \(A\vec x\leq\vec 0\) partition regular if for every coloring of the natural numbers with finitely many colors there exists a monochromatic solution of \(A\vec x\leq\vec 0\). Rado considered systems of linear inequalities only incidentally. He stated the following proposition which is easy to prove: Let the system \(\sum^n_{j=1} a_{ij}x_j=0\), \(1\leq i\leq m\), be partition regular and assume that the following system of inequalities has a solution in the natural numbers: \[ \sum^n_{j=1} a_{ij}x_j\begin{cases} =0\quad\text{for}\quad 1\leq i\leq m_1,\\ >0\quad\text{for}\quad m_1<i\leq m.\end{cases}\tag{\(*\)} \] Then also \((*)\) is partition regular. Of course this observation is far away from being a characterization of partition regular systems of inequalities, but it can be taken as a starting point of our investigations. The characterization of all partition regular systems of linear inequalities is a central goal of this paper. In the first chapter we define a generalized column property called \(cpi\), which can be used to characterize partition regular systems of linear inequalities. It is an interesting feature of Rado's proof that a linear system \(A\vec x=\vec 0\) is already regular if there exists a monochromatic solution with respect to one (number theoretic) type of coloring. Systems of inequalities let things tend to be more difficult. Several years after finishing his ``Studien zur Kombinatorik'', \textit{R. Rado} considered systems of linear equations with coefficients in \(\mathbb{R}\) and he also extended the set of partitioned numbers to the field of real numbers. It turned out that it is possible to carry over the previous results from the natural numbers to the reals. We will show in chapter 1 that our arguments can also be used if we consider real systems of inequalities partitioning the set of reals. Whereas the results of the first chapter refer to systems of homogeneous inequalities, we consider systems of inhomogeneous inequalities in the second chapter. We will give a complete characterization of those systems which are partition regular over the natural numbers, over the set of integers and over the rationals. As well as for homogeneous systems the column property plays an important role for the characterization of partition regular systems of inhomogeneous inequalities. The column property for systems of inequalities (as well as the column property in the sense of Rado) is a syntactical property of the matrix and does not explicitly refer to the set of solutions of the system. In 1973 \textit{W. Deuber} [Math. Z. 133, 109-123 (1973; Zbl 0254.05011)] gave a semantical characterization of partition regular systems of equations. The approach is by a description of the arithmetic structure of the sets of solutions of regular linear systems \(A\vec x=\vec 0\). The central notion is the one of \((m,p,c)\)-sets. He proved the following theorem: A system \(A\vec x=\vec 0\) is partition regular if and only if there exist positive integers \(m\), \(p\), \(c\) such that every \((m,p,c)\)-set contains a solution of \(A\vec x=\vec 0\). In chapter three we will show that \((m,p,c)\)-sets can also be used to characterize solution spaces of partition regular systems of linear inequalities. Starting with results of Erdös and Rado another part of partition theory was developed, which is nowadays known as canonical Ramsey theory. In canonical Ramsey theory one considers colorings with no restriction on the number of colors. The first result is a canonical version of Ramsey's theorem. Later Erdös and Graham proved a generalization of van der Waerden's theorem: For every coloring \(\Delta\) of the natural numbers with arbitrary many colors there exists an arithmetic progression, which is colored monochromatic or injective with respect to \(\Delta\). A canonical analogue of the Rado-Deuber theorem on regular systems of equations and \((m,p,c)\)-sets was proved by Lefmann. His result states: Let \(A\vec x=\vec 0\) be a partition regular system of linear equations. For every coloring \(\Delta\) of the natural numbers with arbitrary many colors there exists a solution of the system \(A\vec x=\vec 0\) such that \(\Delta\) restricted to this solution is either monochromatic, injective or a block-coloring. The third case is related to the partitioning of the columns of \(A\) into blocks, corresponding to the column property and to the rows of the \((m,p,c)\)-sets. In chapter 4 we prove a canonical partition theorem for systems of inequalities. Ramsey, Graham, Leeb and Rothschild (1972) and Shelah (1994) considered colorings of objects of higher rank. In the last chapter we consider colorings which are defined on the \(k\)-element subsets of \(\mathbb{N}\). Let \(k\geq 2\). We call a system \(A\vec x\leq\vec 0\) partition regular for \(k\)-sets if for every coloring of the \(k\)-element subsets of \(\mathbb{N}\) there exists a solution \((x_1\dots x_n)\in\mathbb{N}^n\) such that all \(k\)-element subsets of \(\{x_1,\dots,x_n\}\) are colored the same. Our main result of this chapter is a characterization of all systems of linear inequalities over \(\mathbb{N}\), which are partition regular for \(k\)-sets. It is an interesting corollary that there are only very special systems of equations which are partition regular for \(k\)-sets; namely those having solutions, which only consist of \(k\) different elements. Such solutions can be understood as generalized singleton solutions.