Färbung (Zahlentheorie)
Unter einer Färbung <math>\chi</math> versteht man in der Diskreten Zahlentheorie die Einfärbung einer Zahlenmenge <math>[1,n] \subseteq \mathbb{N}</math> mit <math>r</math> 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 <math>[1,r]</math> <math>r</math> verschiedene Farben. Die Abbildung <math>\chi : [1,r] \rightarrow [1,n] \subseteq{N}</math> definiert auf einer Teilmenge der positiven ganzen Zahlen einer sogenannten <math>r</math>-Färbung, durch die jedes Element der Teilmenge <math>[1,n]</math> eine der <math>r</math> Farben zugeordnet bekommt.
Eigenschaften
- Für jede Farbe aus <math>i \in [1,r]</math> existiert ein Tupel <math>(i,x)</math> mit <math>x \in [1,n]</math>. Ist dies für ein <math>i</math> nicht der Fall, sprechen wir von einer <math>r-1</math>-Färbung.
- Ist <math>r=1</math>, so existiert für jedes <math>n</math> nur eine einzige Färbung.
- Für <math>r>1</math> erhält man die Anzahl der verschiedenen Färbungen leicht durch einige kombinatorische Bemühungen.
- Mit obigen Punkten ergibt sich sofort, dass <math>r \leq n</math> 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 <math>r=3</math> und <math>n = 7</math>. Es existieren für diese Zahlen mehrere Färbungen eine mögliche für <math>\chi: \{1,2,3\} \rightarrow \{1,2,3,4,5,6,7\}</math> wäre
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| R | B | G | B | R | R | G |
Während bei der Definition von <math>\chi</math> von den Farben <math>1 \ldots r</math> gesprochen wird, werden in konkreten Beispielen für diese i. d. R. Farben, wie rot, grün, blau eingesetzt.