Rado's theorem (Ramsey theory)
Encyclopedia
Rado's theorem is a theorem from the branch of mathematics
known as Ramsey theory
. It is named for the German mathematician Richard Rado
. It was proved in his thesis, Studien zur Kombinatorik.
Let Ax = 0 be a system of linear equations, where A is a matrix with integer entries. This system is said to be r-regular if, for every r-coloring of the natural numbers 1, 2, 3, ..., the system has a monochromatic solution. A system is regular if it is r-regular for all r ≥ 1.
Rado's theorem states that a system Ax=0 is regular if and only if the matrix A satisfies the columns condition. Let ci denote the i-th column of A. The matrix A satisfies the columns condition provided that there exists a partition of the column indices C1, C2, ..., Cn such if
, then
Folkman's theorem
, the statement that there exist arbitrarily large sets of integers all of whose nonempty sums are monochromatic, may be seen as a special case of Rado's theorem concerning the regularity of the system of equations
where T ranges over each nonempty subset of the set
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
known as Ramsey theory
Ramsey theory
Ramsey theory, named after the British mathematician and philosopher Frank P. Ramsey, is a branch of mathematics that studies the conditions under which order must appear...
. It is named for the German mathematician Richard Rado
Richard Rado
Richard Rado FRS was a Jewish German mathematician. He earned two Ph.D.s: in 1933 from the University of Berlin, and in 1935 from the University of Cambridge. He was interviewed in Berlin by Lord Cherwell for a scholarship given by the chemist Sir Robert Mond which provided financial support to...
. It was proved in his thesis, Studien zur Kombinatorik.
Let Ax = 0 be a system of linear equations, where A is a matrix with integer entries. This system is said to be r-regular if, for every r-coloring of the natural numbers 1, 2, 3, ..., the system has a monochromatic solution. A system is regular if it is r-regular for all r ≥ 1.
Rado's theorem states that a system Ax=0 is regular if and only if the matrix A satisfies the columns condition. Let ci denote the i-th column of A. The matrix A satisfies the columns condition provided that there exists a partition of the column indices C1, C2, ..., Cn such if
, then- s1 = 0
- for all i ≥ 2, si can be written as a rational linear combination of the cjs in the Ck with k < i.
Folkman's theorem
Folkman's theorem
Folkman's theorem is a theorem in mathematics, and more particularly in arithmetic combinatorics and Ramsey theory. According to this theorem, whenever the natural numbers are partitioned into finitely many subsets, there exist arbitrarily large sets of numbers all of whose sums belong to the same...
, the statement that there exist arbitrarily large sets of integers all of whose nonempty sums are monochromatic, may be seen as a special case of Rado's theorem concerning the regularity of the system of equations
where T ranges over each nonempty subset of the set