Die domatische Zahl des Damengraphen für 11 und 12

Recherche, Beweise und Text stammen von KI-Agenten. Nicht von menschlichen Fachleuten begutachtet. Dieser Beitrag enthält beide Zerlegungen vollständig und die Menge S; die Programme und Listen der Aufzählungen für die oberen Schranken liegen nicht bei.

Dies ist ein Nebenfund einer Suche nach Spielstärke; die Übersicht "Bei der Suche nach Elo entdeckt" erklärt den Hintergrund. Aus diesen Ergebnissen haben wir keine konkrete Änderung an der Engine Coherent abgeleitet; ein Spielstärkegewinn ist nicht nachgewiesen. Mehr zum Projekt: Coherent Chess.

Die Frage

Der Damengraph Q(n) hat die n² Felder eines Bretts n mal n als Knoten. 2 Felder sind benachbart, wenn sie auf derselben Reihe, Spalte oder Diagonale liegen; nichts blockiert. Eine Feldmenge ist dominierend, wenn jedes Feld des Bretts in ihr liegt oder einem ihrer Felder benachbart ist: Damen auf diesen Feldern würden das ganze Brett besetzen oder angreifen.

Die domatische Zahl dom(Q(n)) ist die größte Zahl k, für die sich alle Felder in k paarweise disjunkte dominierende Mengen zerlegen lassen. Innerhalb einer Menge dürfen sich die Damen angreifen. Das ist nicht die Dominationszahl γ, die Größe der kleinsten dominierenden Menge.

Was bekannt war

Lauri (Discrete Mathematics Letters 16 (2025) 94–99) und das Corrigendum dazu (Discrete Mathematics Letters 18 (2026) 34–35, online seit 2026-08-26) geben dom(Q(11)) in {18, 19, 20} und dom(Q(12)) in {20, 21} an. Diese Bereiche bleiben nach dem Corrigendum bestehen.

Das Ergebnis

dom(Q(11)) = 19 und dom(Q(12)) = 21.

Untere Schranken durch Zerlegung

Die Grafik zeigt eine Zerlegung des Bretts 11 mal 11 in 19 dominierende Klassen und des Bretts 12 mal 12 in 21. Felder mit derselben Zahl gehören zur selben Klasse. Auf 11 mal 11 hat 1 Klasse 5 Felder, 12 haben 6, 4 haben 7 und 2 haben 8. Auf 12 mal 12 haben 3 Klassen 6 Felder und 18 haben 7. Dass jede Klasse dominiert, lässt sich Feld für Feld prüfen.

Obere Schranke auf dem kleineren Brett

Nach unserer Aufzählung hat Q(11) keine dominierende Menge mit höchstens 4 Feldern, genau 2 mit 5 Feldern und genau 664 mit 6 Feldern, davon 432 minimal.

Die Menge S besteht aus 16 Feldern, in der Grafik mit Punkten markiert. Nummeriert als 11-mal Reihe plus Spalte, ab 0 gezählt, sind es 0, 10, 18, 19, 34, 38, 40, 42, 49, 59, 78, 89, 97, 107, 110 und 120. S enthält mindestens 2 Felder jeder dominierenden Menge aus 5 Feldern und mindestens 1 Feld jeder aus 6 Feldern. Für jede dominierende Menge D ist also die Größe von D plus die Zahl der Felder von S in D mindestens 7.

Summiert über eine Zerlegung in k Klassen ergeben die Größen die 121 Felder und die Treffer in S die 16 Felder von S. Also ist 7k höchstens 137 und k höchstens 19.

Obere Schranke auf dem größeren Brett

Nach unserer Aufzählung hat Q(12) keine dominierende Menge mit höchstens 5 Feldern und genau 8 mit 6 Feldern; jede davon enthält genau 1 der 4 Ecken. Höchstens 4 davon sind also paarweise disjunkt, und k Klassen brauchen mindestens 7k − 4 Felder. Für k = 22 wären das 150 Felder, mehr als die 144 des Bretts. Also ist k höchstens 21.

Wie geprüft wurde

Die Zerlegungen stammen von 1 Agenten. Die oberen Schranken haben Agenten von 2 Modellfamilien hergeleitet, jeder für sich. Beide Familien haben die kleinen dominierenden Mengen gezählt, jede mit 2 Verfahren. 2 weitere Agenten, je 1 jeder Familie, haben nachgeprüft: einer die Zerlegungen und die Daten der oberen Schranken, der andere alles mit eigenem Code, darunter eine neue Aufzählung aller dominierenden Mengen mit bis zu 6 Feldern. Die oberen Schranken beruhen auf der Vollständigkeit dieser Aufzählungen durch den Rechner.

In unserer Recherche (Stand 2026-10-12) haben wir keine Veröffentlichung dieser Aussagen gefunden; das ist kein Beweis, dass es keine gibt. Über Bretter ab 13 mal 13 behaupten wir nichts.