Färbung (Zahlentheorie)
Unter einer Färbung versteht man in der Diskreten Zahlentheorie die Einfärbung einer Zahlenmenge mit 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.
![{\displaystyle [1,n]\subseteq \mathbb {N} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/a1741f88c7b3c25620f219d96a5385deaeeb99d6)
Definition
[Bearbeiten | Quelltext bearbeiten]Seien verschiedene Farben. Die Abbildung definiert auf einer Teilmenge der positiven ganzen Zahlen einer sogenannten -Färbung, durch die jedes Element der Teilmenge eine der Farben zugeordnet bekommt.
![{\displaystyle [1,r]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/520d42eb6c1af22cd98e64bb762ec04f92fb632a)
![{\displaystyle \chi :[1,r]\rightarrow [1,n]\subseteq {N}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/aa5d726871c7c63617b2dce3bfbf4c233737c529)
![{\displaystyle [1,n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7c79af450e22e8fd23f28e6be4cb23a47b24c1ba)
Eigenschaften
[Bearbeiten | Quelltext bearbeiten]- Für jede Farbe aus existiert ein Tupel mit . Ist dies für ein nicht der Fall, sprechen wir von einer -Färbung.
- Ist , so existiert für jedes nur eine einzige Färbung.
- Für erhält man die Anzahl der verschiedenen Färbungen leicht durch einige kombinatorische Bemühungen.
- Mit obigen Punkten ergibt sich sofort, dass 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.
![{\displaystyle i\in [1,r]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1b328bc0453143651e397e28c62c43ff76b8c7ce)
![{\displaystyle x\in [1,n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/07745963f0cc506e5b35e4878d116d2eacbb6d24)
Beispiel
[Bearbeiten | Quelltext bearbeiten]Wir wählen und . Es existieren für diese Zahlen mehrere Färbungen eine mögliche für 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 gesprochen wird, werden in konkreten Beispielen für diese i. d. R. Farben, wie rot, grün, blau eingesetzt.
