*Wissenschaftliches Programm*   *Liste der Vortragenden*

Sektion 15
Donnerstag, 21.09.2000, 14.30–14.50 Uhr, WIL C 103

Mehrfarben-Diskrepanzen

Benjamin Doerr, Christian-Albrechts-Universität Kiel

Das Diskrepanzproblem für Hypergraphen (Mengensysteme) ist, die Knoten eines Hypergraphen so in zwei Klassen aufzuteilen, dass jede Kante von dieser Partition in zwei möglichst gleich große Teile geteilt wird. Wie bei derartigen Problemen üblich, stellt man die Partition durch eine Knotenfärbung dar. Verwendet man dabei als Farben -1 und +1, so lässt sich die Unausgeglichenheit einer Hyperkante unter einer Färbung einfach als Summe der Farben der entsprechenden Knoten ausdrücken.

An dieser Stelle fangen die Probleme an, wenn man ausgeglichene Partitionen in mehr als zwei Klassen (Mehrfarbendiskrepanzproblem) untersucht. Im Vortag soll eine geeignete Darstellung für diese Diskrepanzen vorgestellt werden. Mit ihrer Hilfe lässt sich beispielsweise der Satz von Beck und Fiala auf beliebige Farbzahlen erweitern: Für jedes c  (- N und jeden Hypergraphen gibt es eine Partition der Knotenmenge in c Klassen, so dass die Zahl der Knoten einer Hyperkante E in einer Farbklasse vom Idealwert 1
c|E| um weniger als 2D abweicht. Dabei bezeichne D den Maximalgrad des Hypergraphen, d. h. maximale Zahl von Hyperkanten, in denen ein Knoten des Hypergraphen liegt.

Weitere Ergebnisse, die mit diesem Ansatz erzielt wurden, sind eine Mehrfarbenversion des Satzes von Barany-Grunberg, sowie eine untere Schranke für die Diskrepanz der arithmetischen Progressionen. Die vorgestellten Ergebnisse sind eine gemeinsame Arbeit mit A. Srivastav (Kiel).