Färbung (Zahlentheorie)

Unter einer Färbung ${\displaystyle \chi }$ versteht man in der Diskreten Zahlentheorie die Einfärbung einer Zahlenmenge ${\displaystyle [1,n]\subseteq \mathbb {N} }$ mit ${\displaystyle 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 ${\displaystyle [1,r]}$ ${\displaystyle r}$ verschiedene Farben. Die Abbildung ${\displaystyle \chi :[1,r]\rightarrow [1,n]\subseteq {N}}$ definiert auf einer Teilmenge der positiven ganzen Zahlen einer sogenannten ${\displaystyle r}$-Färbung, durch die jedes Element der Teilmenge ${\displaystyle [1,n]}$ eine der ${\displaystyle r}$ Farben zugeordnet bekommt.

Eigenschaften

• Für jede Farbe aus ${\displaystyle i\in [1,r]}$ existiert ein Tupel ${\displaystyle (i,x)}$ mit ${\displaystyle x\in [1,n]}$. Ist dies für ein ${\displaystyle i}$ nicht der Fall, sprechen wir von einer ${\displaystyle r-1}$-Färbung.
• Ist ${\displaystyle r=1}$, so existiert für jedes ${\displaystyle n}$ nur eine einzige Färbung.
• Für ${\displaystyle r>1}$ erhält man die Anzahl der verschiedenen Färbungen leicht durch einige kombinatorische Bemühungen.
• Mit obigen Punkten ergibt sich sofort, dass ${\displaystyle 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 ${\displaystyle r=3}$ und ${\displaystyle n=7}$. Es existieren für diese Zahlen mehrere Färbungen eine mögliche für ${\displaystyle \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 ${\displaystyle \chi }$ von den Farben ${\displaystyle 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