Coloring (number theory)

Under a coloring is understood in the discrete number theory coloring a set of numbers with colors . The coloring of sets of numbers is mainly used in Ramsey theory , which examines under certain conditions to what extent regularities can be found in colored subsets. ${\displaystyle \chi }$ ${\displaystyle [1,n]\subseteq \mathbb {N} }$ ${\displaystyle r}$

definition

Be different colors. The mapping defines a so-called coloration on a subset of the positive integers , through which each element of the subset is assigned one of the colors. ${\displaystyle [1,r]}$ ${\displaystyle r}$ ${\displaystyle \chi :[1,r]\rightarrow [1,n]\subseteq {N}}$ ${\displaystyle r}$ ${\displaystyle [1,n]}$ ${\displaystyle r}$

properties

• For each color from there is a tuple with . If this is not the case for one , we speak of a coloration. ${\displaystyle i\in [1,r]}$ ${\displaystyle (i,x)}$ ${\displaystyle x\in [1,n]}$ ${\displaystyle i}$ ${\displaystyle r-1}$
• If there is only one color for each . ${\displaystyle r=1}$ ${\displaystyle n}$
• The number of different stains can easily be obtained by some combinatorial effort. ${\displaystyle r>1}$
• With the above points it immediately follows that it has to be. ${\displaystyle r\leq n}$
• The coloring of the number is always arbitrary. For this reason, the concept of coloring is used in Ramsey theory , which tries to find out conditions for certain regularities for colored subsets.

example

We choose and . There are these numbers several colorations possible for would ${\displaystyle r=3}$ ${\displaystyle n=7}$ ${\displaystyle \chi :\{1,2,3\}\rightarrow \{1,2,3,4,5,6,7\}}$

1	2	3	4th	5	6th	7th
R.	B.	G	B.	R.	R.	G

While the definition of colors is used, concrete examples of these i. d. R. Colors such as red, green, blue are used. ${\displaystyle \chi }$ ${\displaystyle 1\ldots r}$

application

• One color solution
• Ramsey theory
• Van der Waerden's Theorem
• Schur's theorem
• Ramsey's theorem