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.

Definition

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.

Eigenschaften

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.

Beispiel

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.

Anwendung

Bearbeiten