Neue kleine reguläre Graphen mit gegebener Taillenweite: Das Käfig-Problem und darüber hinaus

Grundinformationen

• Paper-ID: 2511.07247
• Titel: New small regular graphs of given girth: the cage problem and beyond
• Autoren: Geoffrey Exoo, Jan Goedgebeur, Jorik Jooken, Louis Stubbe, Tibo Van den Eede
• Klassifizierung: math.CO (Kombinatorik), cs.DM (Diskrete Mathematik)
• Veröffentlichungsdatum: 11. November 2025
• Paper-Link: https://arxiv.org/abs/2511.07247

Zusammenfassung

Das Käfig-Problem befasst sich mit der Suche nach $(k,g)$-Graphen mit minimaler Knotenzahl, d.h. $k$-regulären Graphen mit Taillenweite (girth) $g$. Das Kernziel besteht darin, $n(k,g)$ (die minimale Ordnung solcher Graphen) zu bestimmen und die entsprechenden Extremalgraphen zu identifizieren. Diese Arbeit untersucht das Käfig-Problem und mehrere seiner Varianten aus rechnerischer Perspektive und entwickelt vier komplementäre Graphenerzeugungsalgorithmen: erschöpfende Erzeugung basierend auf Lifts, Tabu-Suche-Heuristik, Hill-Climbing-Heuristik und Schneidetechniken. Mit diesen Methoden werden neue Obergrenzen für elf Fälle des klassischen Käfig-Problems etabliert: $n(3,16) \leq 936$, $n(3,17) \leq 2048$, $n(4,9) \leq 270$, $n(4,10) \leq 320$, $n(4,11) \leq 713$, $n(5,9) \leq 1116$, $n(6,11) \leq 7783$, $n(8,7) \leq 774$, $n(10,7) \leq 1608$, $n(12,7) \leq 2890$, $n(14,7) \leq 4716$. Diese Ergebnisse verbessern mehrere Grenzen, die 22 Jahre lang unverändert waren, insbesondere wird $n(4,10)$ von der langjährigen Grenze 384 auf 320 reduziert, was eine wesentliche Verbesserung darstellt.

Forschungshintergrund und Motivation

Problemdefinition

1. Kernproblem: Das Käfig-Problem sucht nach $(k,g)$-Käfigen (cages), d.h. $k$-regulären Graphen mit minimaler Knotenzahl $n(k,g)$ und Taillenweite $g$. Die Taillenweite ist die Länge des kürzesten Zyklus in einem Graphen.
2. Problemrelevanz:
   • Theoretische Bedeutung: Käfige sind zentrale Forschungsobjekte der extremalen Graphentheorie und stehen in enger Beziehung zu klassischen Theorien wie der Moore-Schranke
   • Praktische Anwendungen: Die dünn besetzten und hochgradig symmetrischen Strukturen haben Anwendungen in der Kommunikationsnetzwerk-Gestaltung, Fehlerkorrekturcodes und Kryptographie
   • Netzwerk-Design: Bieten Topologien, die effiziente gleichmäßige Informationsausbreitung unterstützen, Überlastung zentraler Knoten vermeiden und Robustheit gegenüber Ausfällen bieten
3. Einschränkungen bestehender Methoden:
   • Für die meisten Parameterpaar $(k,g)$ ist der exakte Wert $n(k,g)$ unbekannt
   • Viele bestehende Grenzen wurden jahrelang nicht verbessert (einige Grenzen sind 22 Jahre alt)
   • Moore-Graphen existieren möglicherweise nur für $g \in \{3,4,5,6,8,12\}$
   • Die Rechenkomplexität wächst mit $k$ und $g$ drastisch an
4. Forschungsmotivation:
   • Nutzung moderner Rechenleistung und Optimierungsalgorithmen zur Verbesserung langjähriger Grenzen
   • Entwicklung systematischer Rechenmethoden zur Behandlung des Käfig-Problems und seiner Varianten
   • Bereitstellung konkreter Graphkonstruktionen als Evidenz für theoretische Forschung (z.B. Vermutung der Bipartitheit von Käfigen mit gerader Taillenweite)

Kernbeiträge

1. Algorithmen-Framework: Entwicklung von vier komplementären Graphenerzeugungsalgorithmen
   • Backtracking-Algorithmus basierend auf Spannungsgraph-Lifts (BTA)
   • Tabu-Suche-Heuristik (TS)
   • Hill-Climbing-Heuristik
   • Schneidetechniken
2. Durchbrüche beim klassischen Käfig-Problem: Etablierung von elf neuen Obergrenzen, einschließlich:
   • $n(4,10) \leq 320$ (erhebliche Reduktion von 384)
   • $n(3,16) \leq 936$ (Verbesserung von 960)
   • $n(3,17) \leq 2048$ (Verbesserung von 2176)
   • Erste nicht-triviale Obergrenzen für $n(4,11)$ und $n(6,11)$
3. Fortschritt bei Varianten-Problemen:
   • Kantenumfang-reguläre (egr) Graphen: 21 neue Grenzen (2 enge Grenzen)
   • Knotenumfang-reguläre (vgr) Graphen: 29 neue Grenzen (7 enge Grenzen)
   • $(k,g,g+1)$-Graphen: 6 neue Grenzen
   • $(k,g)$-Spektrum: Bestimmung von 34 zuvor ungelösten Ordnungen
4. Rechnerische Ressourcen und Reproduzierbarkeit:
   • Etwa 5 CPU-Jahre Rechenarbeit
   • Alle Codes und Daten öffentlich auf GitHub verfügbar
   • Vollständige Verifikation und Konsistenzprüfungen

Methodische Details

Aufgabendefinition

Eingabe: Regularitätsgrad $k$, Taillenweite $g$, optionale zusätzliche Einschränkungen (z.B. Knoten-/Kantenumfang-Regularität)

Ausgabe: Graph mit minimaler Ordnung, der die Bedingungen erfüllt, oder verbesserte Obergrenze $n(k,g)$

Einschränkungen: Der Graph muss $k$-regulär sein (jeder Knoten hat Grad $k$) und Taillenweite mindestens $g$ haben (kürzester Zyklus $\geq g$)

Kerntechnik: Spannungsgraph-Lifts (Voltage Graph Lifts)

Grundprinzip

Gegeben ein Bassgraph $G=(V,E)$, eine Gruppe $\Gamma$ und eine Spannungszuweisung $\alpha: A \rightarrow \Gamma$ ($A$ ist die Menge der gerichteten Kanten), ist die Knotenmenge des Lift-Graphen $G_\alpha$: $V(G_\alpha) = \{u_s | u \in V, s \in \Gamma\}$

Für jede Kante $(u,v) \in A$ und jedes $s \in \Gamma$ existiert eine Kante $(u_s, v_{s \cdot \alpha(a)}) \in A(G_\alpha)$.

Schlüsseleigenschaften

1. Erhaltung der Regularität (Beobachtung 1): $G$ ist $k$-regulär genau dann, wenn $G_\alpha$ $k$-regulär ist
2. Notwendige Bedingung für Zusammenhang (Beobachtung 2): Wenn $G$ nicht zusammenhängend ist, dann ist $G_\alpha$ nicht zusammenhängend
3. Taillenweite-Berechnung (Proposition 1): Die Taillenweite von $G_\alpha$ entspricht der Länge des kürzesten geschlossenen nicht-rückwärts-gerichteten Pfades (mit Netto-Spannung $0_\Gamma$) im gerichteten Graphen von $G$
4. Spannbaum-Vereinfachung (Proposition 2): Alle Spannungen auf Spannbaum-Kanten können auf $0_\Gamma$ gesetzt werden, ohne die Isomorphieklasse des Lift-Graphen zu ändern

Algorithmus 1: Backtracking-Algorithmus (BTA)

Strukturierte Ausschlussregeln

Strukturbasierte Ausschlüsse (unabhängig von Spannungszuweisung):

1. Halbkanten-Einschränkung: Halbkanten entsprechende Kanten können nur Gruppenelementen der Ordnung 2 zugewiesen werden
2. Spannbaum-Optimierung: Wähle Spannbaum $T$, setze alle Spannungen auf Kanten von $T$ auf $0_\Gamma$
3. Zyklusbasierte Ausschlüsse: Für nicht-Spannbaum-Kanten, wenn die Spannungszuweisung $a$ einen Zyklus der Länge $(q+1)s$ (wobei $a^s=0_\Gamma$) erzeugt, der kleiner als die Ziel-Taillenweite ist, schließe diese Spannung aus

Zuweisungsbasierte Ausschlüsse (abhängig von partieller Spannungszuweisung):

1. Kanonizitätsprüfung (Algorithmus 1):
   • Nutze Gruppenautomorphismen $\phi_\Gamma$ und Kantenauto-morphismen $\phi_G$
   • Behalte nur den lexikographisch kleinsten Vertreter
   • Wenn eine Teilzuweisung nicht kanonisch ist, können alle ihre Vervollständigungen ausgeschlossen werden
2. Inkrementelle Taillenweite-Verifikation (Algorithmus 2):
   • Prüfe nur geschlossene nicht-rückwärts-gerichtete Pfade, die neue Zuweisungskanten verwenden
   • Nutze Inkrementalität zur Effizienzsteigerung

Algorithmus-Ablauf (Algorithmus 3)

BTA(G, Γ, g_min):
  1. Führe Strukturprüfungen durch, bestimme machbare Spannungsmengen N
  2. Rekursive Spannungszuweisung:
     - Für jede nützliche Kante d, versuche jede Spannung in N(d)
     - Wende Taillenweite-Prüfung und Kanonizitätsprüfung an
     - Wenn bestanden, rekursiv zur nächsten Kante
     - Backtrack bei Rückkehr, stelle Zustand wieder her
  3. Nach vollständiger Zuweisung, konstruiere Lift-Graph und filtere

Algorithmus 2: Tabu-Suche (TS)

Motivation

BTA hat hohe Rechenkosten bei großen Instanzen; TS erkundet vielversprechende Spannungszuweisungen durch heuristische Stichprobennahme.

Schlüsselkomponenten

Nachbarschaftsdefinition: Alle alternativen Zuweisungen, die genau ein Gruppenelement einer Kante ändern

Kostenfunktion:

1. Basierend auf Taillenweite ($c_{girth}$): $c_{girth} = \sum_{i=1}^m f(q_i, a_i), \quad f(q,a) = \begin{cases} \frac{1}{q \cdot \text{Ord}(a)} & \text{wenn } \text{Ord}(a) \neq 1 \\ C & \text{sonst} \end{cases}$ wobei $C$ eine große Strafkonstante ist und $m$ die Anzahl der Stichprobenpfade
2. Basierend auf Regularität ($c_{reg}$): $c_{reg} = \min\left[\text{Var}(f_V), \text{Var}(f_D)\right]$ wobei $f_V$ und $f_D$ die Häufigkeit des Auftretens von Knoten bzw. Kanten in Taillenweite-Zyklen sind

Tabu-Liste: Speichert kürzliche Modifikationsoperationen zur Vermeidung unmittelbarer Rückkehr, Länge $3|\Gamma|$

Störungsmechanismus: Bei Steckenbleiben in lokalen Optima, wende zufällige Modifikationen an zum Ausbrechen

Hyperparameter-Einstellung (Tabelle 1)

• Begrenzung Kanten-/Gruppenautomorphismen: 200/2000
• BTA und TS Zeitlimit: je 20 Sekunden/Instanz
• Minimale Nachbarschafts-Taillenweite: $g_{nbr} = g_{min} - 2$ (Taillenweite-Problem) oder $g_{nbr} = g_{min}$ (Regularitätsproblem)

Algorithmus 3: Hill-Climbing-Heuristik

Unterschied zu vorherigen Methoden: Sucht gleichzeitig Bassgraph und Spannungszuweisung

Ablauf:

1. Beginne mit $n$ isolierten Knoten
2. Jede Iteration:
   • Betrachte alle hinzufügbaren Kantenpaar und Spannungszuweisungen $t \in T(G)$
   • Wähle die Modifikation, die $|T(G_t)|$ maximiert (Greedy-Strategie)
3. Prüfe, ob Lift-Graph einen Rekord bricht

Algorithmus 4: Schneidetechniken

Grundidee: Lösche Knoten aus bekannten kleinen $(k,g+1)$-Graphen, füge dann Kanten hinzu, um $k$-Regularität zu vervollständigen

Konkrete Strategien:

1. Taillenweite 7, gerader Grad $8 \leq k \leq 14$:
   • Lösche zwei Knoten $u,v$ mit Abstand 4 aus $(k,8)$-Käfig
   • Lösche $N_1(u), N_1(v), N_2(u,v)$
   • Schnittmenge-Größe: $3k$ (Verbesserung gegenüber de Ruiter und Biggs' $3k-1$)
2. Taillenweite 11:
   • Aus $(4,12)$-Käfig: Lösche $u,v$ mit Abstand 6, $N_1(u), N_1(v), N_3(u,v)$ und einen Knoten aus $N_2(u) \cap N_4(v)$, Schnittmenge $3k+3$ Knoten
   • Aus $(6,12)$-Käfig: Ähnliche Strategie, Schnittmenge $5k-1$ Knoten

Experimentelle Einrichtung

Rechnerische Ressourcen

• Gesamtrechenleistung: Etwa 5 CPU-Jahre
• Infrastruktur: Flemish Supercomputer Center (VSC)
• Implementierungssprache: Basierend auf C++ (vermutet, nicht explizit angegeben)

Erzeugung von Bassgraphen und Gruppen

1. Gruppen: Verwendung des GAP-Systems zur Erzeugung aller nicht-isomorphen Gruppen der Ordnung $n < 1024$
2. Bassgraphen:
   • Erweiterter multigraph-Generator (multigraph+)
   • Erzeugung zusammenhängender regulärer Graphen mit parallelen Kanten, Schleifen und Halbkanten
   • Verwendung von Nauty zur Entfernung isomorpher Graphen

Verifikationsstrategie

1. Eingabe-Verifikation:
   • Gruppen: Direkt von GAP
   • Bassgraphen: Vergleich mit pregraph-Generator (bis Ordnung 13)
2. Optimierungs-Korrektheit:
   • Deaktiviere einzeln verschiedene Optimierungen (Graphautomorphismen, Gruppenautomorphismen, Taillenweite-Grenzen)
   • Verifiziere Konsistenz der Anzahl erzeugter nicht-isomorpher Lift-Graphen
3. Erschöpfungs-Verifikation:
   • Vergleich mit drei unabhängigen Implementierungen:
     • $K_{1,3}$-basierte Konstruktion
     • Gray- und Theta-Graph-Lifts
     • Block-Zirkular-Graph-Generator (äquivalent zu zyklischen Gruppen-Lifts)
   • Vollständige Übereinstimmung aller Ausgaben in allen Fällen

Filterprozess

1. Zusammenhangs-Prüfung
2. Isomorphie-Filterung: Verwendung von Nauty zur Konstruktion kanonischer Darstellung
3. Taillenweite- und Regularitäts-Verifikation: Verwendung von Algorithmen aus 29

Experimentelle Ergebnisse

Hauptergebnisse: Klassisches Käfig-Problem (Tabelle 2)

Signifikante Verbesserungen

Ergebnisse der Schneidetechniken

• $(8,7) \leq 774$ (Verbesserung von 777 um 3 Knoten)
• $(10,7) \leq 1608$ (Verbesserung von 1611 um 3 Knoten)
• $(12,7) \leq 2890$ (Verbesserung von 2893 um 3 Knoten)
• $(14,7) \leq 4716$ (Verbesserung von 4719 um 3 Knoten)

Schlüsselfunde

1. Durchbruch bei $(4,10)$: Reduktion von 384 auf 320, Reduktion um 16,7%, ist die überraschendste Verbesserung
2. Bipartitäts-Evidenz: Neue $(3,16)$- und $(4,10)$-Graphen sind beide bipartit, unterstützen die Vermutung "Käfige mit gerader Taillenweite müssen bipartit sein"
3. Konstruktionsdetails (Abbildung 4):
   • $(3,16)$: Verwendung der Gruppe $C_{13} \rtimes C_9$ (Ordnung 117), Bassgraph mit 8 Knoten
   • $(4,10)$: Verwendung der Gruppe $C_5 \times D_4$ (Ordnung 40), Bassgraph mit 8 Knoten

Ergebnisse bei Varianten-Problemen

Kantenumfang-reguläre Graphen (Tabelle 3)

• 21 neue Grenzen, davon 2 enge Grenzen (Ober- und Untergrenze gleich):
  • $n(4,5,4) = 30$ (neu bestimmt)
  • Mehrere $(6,5,\lambda_e)$-Fälle erhalten erstmals Obergrenzen

Knotenumfang-reguläre Graphen (Tabelle 4)

• 29 neue Grenzen, davon 7 enge Grenzen:
  • $n(3,7,1) = n(3,7,2) = n(3,7,4) = 42$
  • $n(4,5,1) = n(4,5,6) = n(4,5,7) = 30$
  • Erhebliche Verbesserung mehrerer $(4,6,\lambda_v)$-Fälle

$(k,g)$-Spektrum (Tabelle 5)

• Bestimmung von 34 zuvor ungelösten Ordnungen
• Hauptsächlich konzentriert auf:
  • $(3,11)$ und $(3,12)$: 7 neue Ordnungen
  • $(4,7)$ und $(4,8)$: 12 neue Ordnungen
  • $(5,7)$: 24 neue Ordnungen (von 184 bis 256)

Graphen ohne $(g+1)$-Zyklen (Tabelle 6)

• 6 neue Grenzen:
  • $n(3,11,12) \leq 228$ (Verbesserung von 272)
  • $n(3,13,14) \leq 600$ (Verbesserung von 800)
  • $n(3,15,16) \leq 1760$ (Verbesserung von 2162)

Algorithmen-Effizienzanalyse

Zeit-Allokationsstrategie

• Jede Bassgraph-Gruppen-Kombination: BTA 20 Sekunden, TS 20 Sekunden
• TS-Anfangslösungssuche: 2 Sekunden
• Graphautomorphismen-Suche: 2 Sekunden

Algorithmen-Komplementarität

1. BTA: Vollständige Erschöpfung bei kleinen Instanzen, garantiert Vollständigkeit
2. TS: Heuristische Stichprobennahme bei großen Instanzen, gute Skalierbarkeit
3. Hill-Climbing: Gleichzeitige Optimierung von Bassgraph und Zuweisung, hohe Flexibilität
4. Schneidetechniken: Nutzt bekannte große Graphen, zielgerichtet

Verwandte Arbeiten

Klassische Käfig-Problem-Forschung

1. Theoretische Grenzen:
   • Moore-Schranke (1963): Grundlegende Untergrenze
   • Sauer (1967): $n(k,g) < n(k,g+1)$ Ungleichung
   • Wong (1982): Käfig-Übersicht
2. Konstruktionsmethoden:
   • Balaban (1972-1973): $(3,10)$ und $(3,11)$ Käfige
   • Benson (1966): $(k,12)$ Käfige
   • Biggs-Arbeitsreihe: Mehrere kleine Taillenweite-Graphen
3. Rechenmethoden:
   • McKay et al. (1998): Schnelles Backtracking für Käfige
   • Exoo (2002-2020): Spannungsgraph-Techniken
   • de Ruiter & Biggs (2015): Ganzzahlige Programmierung und Schneidetechniken

Lift-Theorie

• Gross & Tucker (1987): Topologische Graphentheorie-Grundlagen
• Exoo & Jajcay (2011): Taillenweite-Theorie von Spannungsgraph-Lifts
• Diese Arbeit erweitert: Systematisierte Optimierung und Heuristiken

Varianten-Probleme

1. Umfang-reguläre Graphen:
   • Jajcay et al. (2018): Kantenumfang-reguläre Graphen
   • Jajcay et al. (2024): Knotenumfang-reguläre Graphen
   • Goedgebeur & Jooken (2025): Erschöpfende Erzeugung
2. Spektrum-Problem:
   • Eze et al. (2025): Theorie und Rechenmethoden des $(k,g)$-Spektrums
3. Graphen ohne kurze Zyklen:
   • Eze et al. (2026): $(k,g,g+1)$-Graphen und ihre Beziehung zum Käfig-Problem

Vorteile dieser Arbeit

1. Systematisiertes Framework: Einheitliche Behandlung des Käfig-Problems und mehrerer Varianten
2. Algorithmen-Komplementarität: Vier Methoden decken unterschiedliche Größen und Charakteristiken ab
3. Wesentliche Verbesserungen: Bricht mehrere langjährige Rekorde
4. Offene Ressourcen: Code und Daten vollständig öffentlich

Schlussfolgerungen und Diskussion

Hauptschlussfolgerungen

1. Durchbrüche beim klassischen Käfig-Problem:
   • 11 neue Obergrenzen, wobei $(4,10)$ die signifikanteste Verbesserung zeigt (384→320)
   • Mehrere Grenzen, die 22 Jahre lang unverändert waren, erstmals verbessert
   • Erste nicht-triviale Obergrenzen für $(4,11)$ und $(6,11)$
2. Fortschritt bei Varianten-Problemen:
   • Kantenumfang- und Knotenumfang-reguläre Graphen: 50 neue Grenzen (9 enge Grenzen)
   • $(k,g)$-Spektrum: 34 neu bestimmte Ordnungen
   • Graphen ohne $(g+1)$-Zyklen: 6 verbesserte Grenzen
3. Methodologische Beiträge:
   • Systematisiertes Algorithmen-Framework basierend auf Lifts
   • Strukturierte und zuweisungsbasierte Ausschlussregeln
   • Effektive Kombination von Heuristiken und Erschöpfungsmethoden

Einschränkungen

1. Rechenkomplexität:
   • Große $(k,g)$-Parameter sind weiterhin schwer zu handhaben
   • Erfordert erhebliche Rechenressourcen (5 CPU-Jahre)
   • Heuristische Methoden garantieren keine optimale Lösung
2. Methodische Anwendbarkeit:
   • Lift-Methoden hängen von geeigneten Bassgraphen und Gruppen ab
   • Schneidetechniken benötigen bekannte große Graphen als Ausgangspunkt
   • Einige Parameterkombinationen wurden nicht verbessert (z.B. $(3,9)$, $(4,7)$ mit bekannten Käfigen)
3. Theoretische Lücken:
   • In den meisten Fällen bleibt die Lücke zwischen Ober- und Untergrenze groß
   • Keine neuen Untergrenzen-Verbesserungen
   • Für einige Parameter bleiben Obergrenzen als "?" (unbekannt) markiert
4. Hyperparameter-Sensitivität:
   • Zeitlimits, Tabu-Listen-Größe etc. erfordern empirische Anpassung
   • Keine systematische Hyperparameter-Optimierungsstudie

Zukünftige Richtungen

1. Theoretische Richtung:
   • Ableitung unendlicher Familien aus neuen Konstruktionen
   • Verbesserung der Moore-Schranke und ihrer Varianten
   • Beweis oder Widerlegung der Bipartitäts-Vermutung für Käfige mit gerader Taillenweite
2. Algorithmen-Verbesserungen:
   • Entwicklung effizienterer Taillenweite-Berechnungsalgorithmen
   • Erkundung maschinelles Lernens zur heuristischen Gestaltung
   • Parallelisierung zur Nutzung moderner Multi-Core-Architekturen
3. Verallgemeinerung von Schneidetechniken:
   • Systematisierte Strategien zur Schnittmenge-Auswahl
   • Erweiterung auf mehr $(k,g)$-Parameterpaar
   • Theoretische Analyse der Schneidetechniken-Effektivität
4. Anwendungs-Erkundung:
   • Anwendung neu entdeckter Graphen im Netzwerk-Design
   • Erkundung von Anwendungen in Fehlerkorrekturcodes
   • Untersuchung kryptographischer Relevanz

Tiefgehende Bewertung

Stärken

1. Bedeutende empirische Beiträge:
   • Bricht mehrere 22 Jahre alte Rekorde, besonders die große Verbesserung bei $(4,10)$
   • Bietet zahlreiche konkrete Konstruktionen als Material für theoretische Forschung
   • Liefert erstmals nicht-triviale Grenzen für bestimmte Parameter
2. Methodologische Innovationen:
   • Systematisierte Ausschlussregeln: Struktur- und zuweisungsbasierte Ausschlüsse reduzieren Suchraum erheblich
   • Algorithmen-Komplementarität: BTA, TS, Hill-Climbing und Schneidetechniken decken verschiedene Szenarien ab
   • Inkrementelle Verifikation: Algorithmus 2's inkrementelle Taillenweite-Prüfung verbessert Effizienz
   • Kanonizitätsprüfung: Nutzt Symmetrie zur Vermeidung redundanter Berechnungen
3. Strenge experimentelle Gestaltung:
   • Mehrschichtige Verifikationsstrategie (Eingabe, Optimierung, Erschöpfung)
   • Vergleich mit drei unabhängigen Implementierungen
   • Detaillierte Hyperparameter-Einstellung
   • Vollständige Reproduzierbarkeitsunterstützung
4. Forschungsbreite:
   • Konzentriert sich nicht nur auf klassisches Problem, sondern systematisch auf vier Varianten
   • Etabliert erste Obergrenzen für mehrere Varianten
   • Einheitliches Framework für verschiedene Probleme
5. Open-Science-Praktiken:
   • Code und Daten vollständig öffentlich (GitHub)
   • Graphen in House of Graphs-Datenbank aufgenommen
   • Verifizierbare Zertifikate (konstruierte Graphen) bereitgestellt

Schwächen

1. Begrenzte theoretische Tiefe:
   • Hauptsächlich rechnerische/empirische Arbeit, mangelnde tiefe theoretische Einsichten
   • Keine neuen Untergrenzen oder theoretischen Analysen
   • Fehlende theoretische Erklärung, warum bestimmte Parameter signifikante Verbesserungen zeigen
2. Methoden-Vollständigkeit:
   • Heuristische Methoden (TS, Hill-Climbing) ohne Vollständigkeitsgarantie
   • Hyperparameter-Auswahl empirisch basiert, mangelnde systematische Untersuchung
   • Keine Analyse theoretischer Garantien oder Konvergenz
3. Experimentelle Berichterstattungs-Details:
   • Nicht berichtet, welche Algorithmen zu spezifischen Verbesserungen beitragen
   • Fehlende detaillierte Laufzeit-Analyse
   • Keine Diskussion von Fehlerfällen oder schwierigen Instanzen
4. Skalierungsprobleme:
   • Methodische Machbarkeit für größere $k$ und $g$ unklar
   • Wachstum der Rechenressourcen-Anforderungen mit Parametern nicht analysiert
   • Einige Ergebnisse mit "≥100" markiert, deuten auf unvollständige Erkundung hin
5. Schreib-Organisation:
   • Technische Details dicht, Lesbarkeit für Nicht-Spezialisten herausfordernd
   • Einige Algorithmen-Beschreibungen (z.B. Algorithmus 4 Pseudocode) unvollständig
   • Zahlreiche Ergebnis-Tabellen, aber mangelnde einheitliche Zusammenfassung

Einfluss

1. Akademischer Einfluss:
   • Hoch: Käfig-Problem ist klassisches extremales Graphentheorie-Problem, Verbesserung langjähriger Rekorde ist bedeutsam
   • Bietet indirekte Forschungswege für berühmte offene Probleme wie 57-Moore-Graph
   • Methoden verallgemeinerbar auf andere extremale Graphenprobleme
2. Praktischer Wert:
   • Mittel: Neue Graphen verwendbar für Netzwerk-Topologie-Design, Fehlerkorrekturcodes
   • Open-Source-Tools für andere Forscher verfügbar
   • Algorithmen-Framework anwendbar auf verwandte kombinatorische Optimierungsprobleme
3. Reproduzierbarkeit:
   • Ausgezeichnet: Vollständiger Code und Daten öffentlich
   • Detaillierte Verifikationsstrategien erhöhen Vertrauenswürdigkeit
   • Konkrete Konstruktionen unabhängig verifizierbar
4. Potenzial für Folgeforschung:
   • Neue Konstruktionen könnten unendliche Familien inspirieren
   • Algorithmen-Framework anwendbar auf andere Graphenerzeugungsprobleme
   • Erste Ergebnisse bei Varianten-Problemen eröffnen neue Forschungsrichtungen

Anwendungsszenarien

1. Direkte Anwendung:
   • Netzwerk-Design benötigt kleine hochgradig Taillenweite-reguläre Graphen
   • LDPC-Code-Konstruktion und andere Fehlerkorrekturcodes
   • Kryptographische Anwendungen wie Schlüsselaustausch
2. Forschungswerkzeuge:
   • Rechnerische Experimente in extremaler Graphentheorie
   • Testfälle für Graph-Isomorphismus und Kanonisierungs-Algorithmen
   • Benchmark-Tests für kombinatorische Optimierungs-Heuristiken
3. Lehrmaterialien:
   • Demonstration von Rechenmethoden-Anwendungen in reiner Mathematik
   • Fallstudien in Algorithmen-Design und Optimierung
   • Beispiele für Open Science und reproduzierbare Forschung
4. Verallgemeinerungsfelder:
   • Andere extremale Graphenprobleme (Ramsey-Zahlen, Turán-Probleme etc.)
   • Constraint-Satisfaction-Probleme
   • Kombinatorische Designs und Codierungstheorie

Ausgewählte Referenzen

1. Grundlagen-Theorie:
   • 45 Sachs (1963): Beweis der Existenz von $(k,g)$-Graphen für alle $k \geq 2, g \geq 3$
   • 31 Gross & Tucker (1987): Topologische Graphentheorie und Lift-Theorie
   • 47 Wong (1982): Umfassende Käfig-Übersicht
2. Rechenmethoden:
   • 24 Exoo et al. (2011): Rechnerische Bestimmung von $(3,11)$ und $(4,7)$ Käfigen
   • 38 McKay et al. (1998): Schnelle Backtracking-Prinzipien
   • 15 de Ruiter & Biggs (2015): Ganzzahlige Programmierungs-Methoden
3. Neueste Fortschritte:
   • 22 Exoo & Jajcay (2011): Taillenweite-Theorie von Spannungsgraph-Lifts
   • 29 Goedgebeur & Jooken (2025): Erschöpfende Erzeugung kantenumfang-regulärer Graphen
   • 34 Jajcay et al. (2024): Knotenumfang-reguläre Graphen
4. Werkzeuge:
   • 37 McKay & Piperno (2014): Nauty Graph-Isomorphismus-Software
   • 27 GAP-System: Gruppentheorie-Berechnung
   • 12 House of Graphs: Graph-Datenbank

Gesamtbewertung: Dies ist ein hochqualitatives Papier der rechnergestützten Kombinatorik, das durch systematische Algorithmen-Entwicklung und großflächige Rechenexperimente signifikante empirische Fortschritte beim klassischen Käfig-Problem und seinen Varianten erzielt. Die methodologischen Innovationen (besonders systematisierte Ausschlussregeln und Algorithmen-Komplementarität) und strenge Verifikationsstrategien sind Hauptmerkmale. Obwohl die theoretische Tiefe begrenzt ist, machen die empirischen Beiträge, Open-Science-Praktiken und Feldförderung es zu einem wichtigen Beitrag. Für Forscher in extremaler Graphentheorie, Graphalgorithmen oder kombinatorischer Optimierung bietet dieses Papier wertvolle Methoden und Ressourcen.