Färbung (Zahlentheorie)
# Färbung (Zahlentheorie)

Unter einer Färbung $\chi$ versteht man in der Diskreten Zahlentheorie die Einfärbung einer Zahlenmenge $[1,n]\subseteq \mathbb {N}$ mit $r$ Farben. Die Färbung von Zahlenmengen findet ihre Anwendung vor allem in der Ramseytheorie, die unter gewissen Bedingungen untersucht, inwiefern sich Gesetzmäßigkeiten in gefärbten Teilmengen finden lassen.

## Definition

Seien $[1,r]$ $r$ verschiedene Farben. Die Abbildung $\chi :[1,r]\rightarrow [1,n]\subseteq {N}$ definiert auf einer Teilmenge der positiven ganzen Zahlen einer sogenannten $r$-Färbung, durch die jedes Element der Teilmenge $[1,n]$ eine der $r$ Farben zugeordnet bekommt.

## Eigenschaften

* Für jede Farbe aus $i\in [1,r]$ existiert ein Tupel $(i,x)$ mit $x\in [1,n]$. Ist dies für ein $i$ nicht der Fall, sprechen wir von einer $r-1$-Färbung.
* Ist $r=1$, so existiert für jedes $n$ nur eine einzige Färbung.
* Für $r>1$ erhält man die Anzahl der verschiedenen Färbungen leicht durch einige kombinatorische Bemühungen.
* Mit obigen Punkten ergibt sich sofort, dass $r\leq n$ sein muss.
* Die Färbung der Zahlenmenge ist stets beliebig. Aus diesem Grund findet der Färbungsbegriff Anwendung in der Ramseytheorie, die versucht für gefärbte Teilmengen Bedingungen für bestimmte Gesetzmäßigkeiten herauszufinden.

## Beispiel

Wir wählen $r=3$ und $n=7$. Es existieren für diese Zahlen mehrere Färbungen eine mögliche für $\chi :\{1,2,3\}\rightarrow \{1,2,3,4,5,6,7\}$ wäre

| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| - | - | - | - | - | - | - |
| R | B | G | B | R | R | G |

Während bei der Definition von $\chi$ von den Farben $1\ldots r$ gesprochen wird, werden in konkreten Beispielen für diese i. d. R. Farben, wie rot, grün, blau eingesetzt.

## Anwendung

* Einfarbige Lösung
* Ramseytheorie
* Satz von Van der Waerden
* Satz von Schur
* Satz von Ramsey
