Großer Durchbruch beim fairen Aufteilen

Man braucht keinen Doktortitel in Mathematik, um 12 Personen für ein Quiz in zwei Teams aufzuteilen. Aber jede Person hat andere Stärken und Schwächen: Eine Person kennt sich sehr gut mit Geografie aus, aber nicht mit Musik. Eine andere Person kennt sich mit Natur aus, schaut aber kein Fernsehen. Eine dritte Person liebt Filme, liest aber nie Bücher. Dann ist es viel schwerer, die Eigenschaften fair zwischen zwei Teams zu verteilen.

Wie gleich kann man also die Teams bilden? Wie schafft man es, dass beide Teams in jeder Kategorie gleich stark sind, von griechischer Mythologie bis College-Basketball?

Forscher, die kombinatorische Diskrepanz-Theorie studieren, sagen: Man kann die Teams immer überraschend gleich machen.

Die Diskrepanz-Theorie ist ein Teil der Mathematik. Sie beschäftigt sich damit, Ressourcen so gleich wie möglich zu verteilen. Wenn ein Quiz-Team das ganze Wissen über Geschichte hat und das andere Team nichts hat, dann ist das eine große Diskrepanz.

Anfang der 1980er Jahre hat der Mathematiker János Komlós eine überraschende Vermutung gemacht. Er hat gesagt: Egal wie viele Objekte (zum Beispiel Spieler) oder Dimensionen (zum Beispiel Quiz-Kategorien) man hat, die Diskrepanz wird nie größer als eine feste Zahl. Man kann die Diskrepanz messen. Und es gibt immer einen Weg, die Teams so zu teilen, dass die Diskrepanz unter dieser festen Zahl bleibt.

„Das ist wirklich erstaunlich“, sagt Haotian Jiang. Er ist theoretischer Informatiker an der University of Chicago. „Die Komlós-Vermutung sagt: Die Dimension des Problems ist egal. Es ist eine universelle Konstante.“

Niemand hat bisher einen Beweis gefunden, dass die Vermutung falsch ist. Aber sie ist so erstaunlich, dass manche Mathematiker dachten, sie muss falsch sein. Der Beweis ist „eines dieser Heiligen-Gral-Probleme in der Diskrepanz-Theorie“, sagt Nikhil Bansal. Er ist theoretischer Informatiker an der University of Michigan.

Sogar der Erfinder der Vermutung findet sie ein bisschen absurd. „Ich war jung und dumm, als ich sie gemacht habe“, schreibt der heute pensionierte Komlós in einer E-Mail als Witz. „Ich habe mit dieser unverantwortlichen Vermutung ein Problem in die kombinatorische Diskrepanz-Theorie gebracht.“

Wenn die Komlós-Vermutung richtig ist, kann sie Antworten auf viele andere Probleme geben. Das gilt für die Diskrepanz-Theorie selbst und auch für andere Bereiche wie Operations Research.

Aber jahrzehntelang sah ein Beweis sehr unwahrscheinlich aus. Mathematiker konnten nicht viel Fortschritt machen. Ihr bestes oberes Limit für die Diskrepanz kam aus dem Jahr 1998. Dieses Limit hing noch stark von der Dimension des Problems ab. Es war weit entfernt von einer Konstanten.

Dann, im Herbst 2025, haben Bansal und Jiang den ersten großen Fortschritt seit fast 30 Jahren bekannt gegeben. Sie haben ein Limit gefunden, das sich nur sehr langsam mit der Dimension ändert. Sogar bei einer astronomisch großen Zahl von Dimensionen ist es nur ein kleines bisschen von einer Konstanten entfernt. Andere Forscher beschreiben die Arbeit, die einen neuen algorithmischen Ansatz benutzt, als „sehr spannend“, „ein schönes Ergebnis“ und „einen riesigen Schritt nach vorn“.

Das unerwartete Ergebnis hat das Problem noch nicht komplett gelöst. Aber es ist der bisher stärkste Hinweis, dass die Vermutung von Komlós doch nicht so unverantwortlich war. „Früher dachte ich eher, die Vermutung ist falsch“, sagt Aleksandar Nikolov. Er ist Informatiker an der University of Toronto. Die neue Arbeit „macht mich jetzt viel sicherer, dass die Vermutung wahrscheinlich doch richtig ist.“

Die Lösung von Bansal und Jiang zeigt: Man kann sehr komplexe Systeme viel einfacher machen und leichter untersuchen. Und sie gibt Ideen, die man vielleicht in Mathematik, Physik und sogar im maschinellen Lernen nutzen kann.

Aufteilen in zwei Gruppen

Diskrepanz-Probleme wie bei Komlós handeln davon, eine Menge von Objekten in zwei Teilmengen zu teilen. Man kann an das Aufteilen von Personen in Quiz-Teams denken, oder von gebrauchten Autos in zwei Gruppen, oder von Teilnehmern einer medizinischen Studie in Behandlungs-Gruppe und Placebo-Gruppe.

Die Komlós-Vermutung stellt sich jede Person (oder jedes Objekt) als Pfeil mit der Länge 1 vor. Das nennt man Einheitsvektor. Dieser Vektor hat eine Liste von Koordinaten. Jede Koordinate zeigt, wie viel von einer bestimmten Eigenschaft die Person hat.

Stellen wir uns vor, wir schauen nur auf zwei Quiz-Bereiche: Bücher und Filme. So kann man sich jede Person als Vektor vorstellen:

Jetzt teilt man jeden Vektor einem Team zu. Wenn man einen Vektor in Team A gibt, lässt man seine Koordinaten so wie sie sind. Wenn man ihn in Team B gibt, multipliziert man jede Koordinate mit −1. Man dreht den Vektor also um.

Wenn man perfekt teilen kann und beide Teams gleich viel Wissen über Bücher und Filme haben, dann ergeben alle Vektoren zusammen Null. Das ist perfekte Harmonie.

Aber Perfektion ist meistens nicht möglich. Deshalb ist die Frage: Wie nah kann man an Null herankommen?

In unserem Beispiel mit vier Spielern kann man leicht alle Möglichkeiten testen. Dann sieht man: Alice und Bob sollten in einem Team sein, und Carla und Dave im anderen Team. Man muss übrigens nicht gleich viele Personen in beiden Teams haben. Man will die Vektoren nur so aufteilen, dass man so viele wie nötig mit −1 multipliziert und sie sich gegenseitig aufheben.

Diese Aufgabe wird viel schwerer, wenn man mehr Vektoren und mehr Eigenschaften hat, die man ausgleichen will. Trotzdem hatte Komlós eine sehr optimistische Hypothese: Egal wie viele Vektoren und Dimensionen man hat, die Diskrepanz bleibt immer unter einer festen Konstante.