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