Färbung (Zahlentheorie)

Unter einer Färbung χ 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 sogenannte 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 χ 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