Ramsey theory studies the ordered configurations that every finite coloring of a sufficiently large structure must contain.
A finite coloring of a set is a function into a finite set of colors. A subset is monochromatic when the restriction of to it is constant.
The infinite form of Ramsey's theorem says that if the -element subsets of an infinite set are finitely colored, then some infinite subset has all its -element subsets in one color.
For positive integers , there is such that every -coloring of the -element subsets of has a monochromatic -element subset. A diagonal compactness argument deduces this from Ramsey's theorem.
Let be a finite alphabet. A combinatorial line in is obtained by fixing some coordinates and replacing every coordinate in one nonempty active set by the same variable letter. It therefore contains one word for each letter of .
For every finite alphabet and every positive integer , there is such that every -coloring of contains a monochromatic combinatorial line.
Every finite coloring of the positive integers contains monochromatic arithmetic progressions of every prescribed finite length.
For all positive integers , some has the following property: every -coloring of contains for whichis monochromatic. Thus the common difference has the same color as the progression.
Several monochromatic arithmetic progressions are color-focused when they have different colors and extend by one further term to the same point. Such focused families give an elementary induction proof of the length-three case of the Van der Waerden theorem.
For every finite , every finite coloring of contains a monochromatic homothetic copy . The theorem follows from the Hales-Jewett theorem by coloring a word according to the sum of the points indexed by its letters.
A rational matrix is partition regular when every finite coloring of the positive integers admits a nonzero monochromatic vector satisfying .
If are the columns of a matrix, the matrix has the columns property when has an ordered partition such thatand, for , belongs to the linear span of the columns indexed by .
Rado's theorem states that a rational matrix is partition regular if and only if it has the columns property.
The necessity direction in Rado's theorem colors an integer using initial data from a P-adic valuation. Applying partition regularity and grouping the coordinates of a monochromatic solution by valuation yields the blocks in the columns property; reduction modulo successively higher powers of supplies the required linear dependences.
Every finite coloring of the positive integers has an infinite sequence for which all nonempty finite sums of distinct terms have one color.
The Milliken–Taylor theorem gives monochromatic systems of separated block sums with a fixed compressed coefficient vector, such as . Systems associated with two nonproportional compressed coefficient vectors need not have the same color: in particular, there is a finite coloring for which a finite-sums set and the Milliken–Taylor system cannot be monochromatic together.
There is a finite coloring of the positive integers for which no infinite set has all pairwise sums and pairwise products in one color. Refining this coloring by the parity of the 2-adic valuation also prevents a constant infinite sequence from evading the obstruction.
A finite set is Euclidean Ramsey when, for every number of colors, some finite-dimensional Euclidean space has the property that every coloring of it contains a monochromatic isometric copy of .
A finite point set is spherical when it lies on a sphere. Every Euclidean Ramsey set is spherical. Whether every finite spherical point set is Euclidean Ramsey is open.
If finite point sets and are Euclidean Ramsey, then their orthogonal Cartesian product is Euclidean Ramsey. The proof first chooses a finite Ramsey witness for , colors a witness for by the complete color pattern it induces on the first witness, and then applies the two Ramsey properties in succession.
Every regular polygon is a Euclidean Ramsey set. A Hales-Jewett theorem combinatorial line in a Cartesian power of its vertex set is a scaled regular polygon; including finitely many reciprocal square-root scalings makes one such line isometric to the original polygon.
A finite Euclidean configuration is edge Ramsey when every finite edge coloring of a suitable finite Euclidean set contains a monochromatic isometric copy. The edge Ramsey configurations are exactly the equidistant sets, equivalently the vertex sets of regular simplices.
Every finite cyclic transitive point set is a Euclidean Ramsey set. In particular every regular polygon is Euclidean Ramsey.
Articles by others on the same topic
Ramsey theory is a branch of combinatorial mathematics that studies conditions under which a certain order or structure must appear within a larger set. It is primarily concerned with the existence of particular substructures within large systems or configurations. The core principle is often summarized by the statement that "sufficiently large structures will always contain a certain order.