A note on Ramsey numbers for minors

Die Arbeit bestimmt das asymptotische Verhalten der Ramsey-Zahlen für Minoren, indem sie zeigt, dass $R_h(k; \ell)$ für große $k$ proportional zu $\ell k \sqrt{\log k}$ ist.

Das Wesentliche

🎨 Das große Farb-Chaos: Eine Reise in die Welt der Ramsey-Zahlen

Stell dir vor, du hast eine riesige Party mit vielen Gästen. Jeder Gast ist ein Punkt auf einer Karte, und zwischen jedem Paar von Gästen gibt es eine Verbindungslinie (eine Freundschaft). Das ist in der Mathematik ein vollständiger Graph.

Jetzt kommt das Spiel: Du hast viele Farben (z. B. Rot und Blau) und du färbst jede dieser Verbindungslinien zufällig ein. Die Frage, die sich die Mathematiker stellen, ist: Wie viele Gäste müssen mindestens auf der Party sein, damit man garantiert eine bestimmte „Struktur" in einer einzigen Farbe findet?

In der klassischen Mathematik (Ramsey-Theorie) suchte man nach einem perfekten Dreieck (alle drei Punkte sind in derselben Farbe verbunden). In diesem neuen Papier sucht Maria Axenovich nach etwas „Robusterem": Sie sucht nach einem Knoten-Cluster, der so stark verbunden ist, dass man ihn durch geschicktes „Zusammenkleben" von Punkten und Löschen von Linien in einen perfekten Klotz verwandeln kann.

🧱 Was ist das „Hadwiger-Nummer"-Konzept?

Stell dir vor, du hast ein komplexes Lego-Modell.

• Vertex-Deletion (Knoten löschen): Du nimmst ein paar Steine einfach weg.
• Edge-Contraction (Kanten kontrahieren): Du nimmst zwei Steine, die direkt verbunden sind, und klebst sie zu einem einzigen, größeren Stein zusammen.

Wenn du durch diese beiden Tricks aus deinem komplexen Modell am Ende ein perfektes, kleines Würfel-Modell (einen „K-Clustern") bauen kannst, dann hast du eine Minor gefunden.

Die Hadwiger-Zahl ist einfach die Größe des größten perfekten Würfels, den du aus deinem Modell bauen kannst.

• Die Frage des Papiers lautet: Wie groß muss die Party (die Anzahl der Gäste $n$) sein, damit wir bei einer beliebigen Färbung der Freundschaftslinien garantiert eine Gruppe von Leuten finden, die in einer Farbe so stark verbunden ist, dass man daraus einen Würfel der Größe $k$ bauen kann?

Diese Zahl nennen wir $Rh(k)$.

🔍 Die Entdeckungen des Papiers

Die Autorin hat herausgefunden, wie sich diese Zahl verhält, wenn $k$ (die gewünschte Größe des Würfels) sehr groß wird.

1. Die untere Grenze (Das „Schlimmste Szenario"):
Stell dir vor, du bist ein böser Färbungs-Gott und willst verhindern, dass jemand einen großen Würfel findet. Du verteilst die Farben so geschickt wie möglich.
Die Mathematik zeigt: Selbst wenn du dich extrem anstrengst, kannst du nicht verhindern, dass bei einer Party mit ungefähr $k \cdot \sqrt{\log k}$ Gästen ein solcher Würfel in einer Farbe entsteht.

• Analogie: Es ist wie beim Schütteln eines Bechers mit roten und blauen Murmeln. Irgendwann, egal wie du schüttelst, landen genug rote Murmeln zusammen, um ein kleines Haus zu bauen.

2. Die obere Grenze (Das „Beste Szenario"):
Die Autorin hat auch bewiesen, dass man nicht viel mehr Gäste braucht, um diesen Würfel zu garantieren. Die Zahl liegt knapp über der unteren Grenze.

• Die Formel: Sie liegt bei ungefähr $1,031 \cdot k \cdot \sqrt{\log k}$.
• Was bedeutet das? Es bedeutet, dass die Mathematik sehr präzise ist. Der „Spielraum" für den bösen Färbungs-Gott ist winzig. Sobald die Party eine bestimmte Größe erreicht, ist das Ergebnis vorhersehbar.

3. Mehr Farben?
Das Papier betrachtet auch Szenarien mit mehr als zwei Farben (z. B. Rot, Blau, Grün).

• Wenn du mehr Farben hast, brauchst du natürlich eine noch größere Party, um garantiert einen Würfel in einer dieser Farben zu finden.
• Die Formel zeigt: Die benötigte Partygröße wächst linear mit der Anzahl der Farben ($\ell$).
  • Analogie: Wenn du 10 Farben hast, musst du die Party auf 10-mal so viele Gäste vergrößern, damit sich garantiert eine Farbe durchsetzt.

🎯 Warum ist das wichtig?

Früher haben Mathematiker viel über die „Hadwiger-Vermutung" geforscht, die besagt, dass man aus jedem komplexen Netzwerk einen bestimmten Würfel bauen kann, wenn man genug Farben für die Punkte braucht.
Dieses Papier füllt eine Lücke: Es sagt uns nicht nur, ob man einen Würfel bauen kann, sondern wie groß das Netzwerk sein muss, damit man ihn unabhängig davon, wie man es färbt, garantiert findet.

Es ist wie eine Versicherung: „Wenn du mindestens $X$ Gäste einlädst, ist es unmöglich, dass keine Gruppe von $k$ Leuten in einer Farbe so eng verbunden ist, dass sie ein perfektes Team bilden."

🏁 Zusammenfassung in einem Satz

Maria Axenovich hat berechnet, wie groß eine Gruppe von Menschen sein muss, damit man bei einer zufälligen Färbung ihrer Freundschaftslinien garantiert eine stark vernetzte Untergruppe findet, die sich zu einem perfekten mathematischen „Würfel" zusammenfalten lässt – und sie hat gezeigt, dass diese Zahl sehr genau vorhergesagt werden kann, selbst wenn man hunderte von Farben verwendet.

Die Kernaussage: Chaos (zufälliges Färben) kann die Ordnung (die Struktur eines perfekten Würfels) nicht für immer verbergen, sobald die Gruppe groß genug ist.

Technische Zusammenfassung

Hier ist eine detaillierte technische Zusammenfassung des vorliegenden Papiers auf Deutsch:

Titel: Eine Anmerkung zu Ramsey-Zahlen für Minoren

Autorin: Maria Axenovich
Datum: 12. März 2026 (basierend auf dem Entwurf)

---

1. Problemstellung und Motivation

Das Papier untersucht eine Verallgemeinerung der klassischen Ramsey-Theorie, die sich auf den Hadwiger-Parameter (Hadwiger number) statt auf die Clique-Größe (Clique number) konzentriert.

• Klassischer Hintergrund: Die klassische Ramsey-Zahl $R(k)$ ist die kleinste Zahl $n$, sodass jede 2-Färbung der Kanten des vollständigen Graphen $K_n$ eine monochromatische Clique $K_k$ enthält.
• Verallgemeinerung: Für einen Graphenparameter $\xi$ ist $R_\xi(k)$ definiert als die kleinste $n$, sodass jede 2-Färbung von $K_n$ einen monochromatischen Teilgraphen $G$ mit $\xi(G) = k$ enthält.
• Der Hadwiger-Parameter: Die Hadwiger-Zahl $h(G)$ ist die größte Zahl $k$, sodass $G$ einen $K_k$-Minor enthält (d.h. $K_k$ kann durch Kantenkontraktionen und Vertex-Löschungen aus $G$ gewonnen werden).
• Ziel: Die Arbeit definiert und analysiert die Ramsey-Zahl für Minoren, bezeichnet als $Rh(k; \ell)$, wobei $\ell$ die Anzahl der Farben ist. Es wird die kleinste $n$ gesucht, sodass jede $\ell$-Färbung von $K_n$ einen monochromatischen Graphen mit Hadwiger-Zahl $k$ erzwingt.
• Relevanz: Obwohl die Hadwiger-Vermutung ($h(G) \ge \chi(G)$) intensiv erforscht ist, wurde das spezifische Ramsey-Problem für Minoren in der Literatur bisher nicht explizit adressiert.

---

2. Methodik und theoretische Grundlagen

Die Beweise stützen sich auf eine Kombination aus extremaler Graphentheorie, Wahrscheinlichkeitstheorie (Zufallsgraphen) und strukturellen Ergebnissen über Graphen mit hoher Konnektivität.

• Dichte und Hadwiger-Zahl: Ein zentrales Werkzeug ist das asymptotische Verhalten der minimalen Kantendichte $c(k)$, die notwendig ist, um einen $K_k$-Minor zu garantieren. Thomason [13] zeigte, dass $c(k) = \beta k \sqrt{\log_2 k} (1 + o(1))$, wobei $\beta \approx 0.265656$ eine Konstante ist, die aus der Lösung einer transzendenten Gleichung resultiert.
• Zufallsgraphen: Der Satz von Bollobás, Catlin und Erdős [4] liefert die Hadwiger-Zahl für Zufallsgraphen $G(n, p)$, was als untere Schranke für Ramsey-Zahlen dient.
• Konnektivität: Der Beweis nutzt Theorem 1.3 von Thomason, das besagt, dass Graphen mit hinreichend hoher Konnektivität (relativ zur Dichte) mindestens so große Hadwiger-Zahlen haben wie Zufallsgraphen gleicher Dichte.
• Strukturelle Zerlegung: Für die unteren Schranken werden Packungsergebnisse (Packing results) und Zerlegungssätze (z.B. von Wilson und Nash-Williams) verwendet, um $K_n$ in kopien von $K_k$-minor-freien Graphen zu zerlegen.

---

3. Wichtige Ergebnisse

Die Arbeit liefert asymptotische Schranken für $Rh(k; \ell)$ und exakte Werte für kleine $k$.

A. Asymptotische Schranken für zwei Farben ($\ell = 2$)

Für $Rh(k) = Rh(k; 2)$ wird gezeigt:
$$k \sqrt{\log k} (1 + o(1)) \le Rh(k) \le 1.031 \cdot k \sqrt{\log k} (1 + o(1))$$

• Untere Schranke: Wird durch eine zufällige 2-Färbung von $K_n$ mit $n \approx k \sqrt{\log k}$ erreicht. In diesem Fall haben die Farbklassen die Struktur von Zufallsgraphen $G(n, 1/2)$, deren Hadwiger-Zahl mit hoher Wahrscheinlichkeit kleiner als $k$ ist.
• Obere Schranke: Der Beweis verfeinert die naive Anwendung von Thomasons Dichte-Theorem. Durch eine sorgfältige Fallunterscheidung (hohe Konnektivität vs. Existenz von induzierten Subgraphen mit hohem Minimalgrad) wird die Konstante von einem groben Wert von $\approx 1.062$ auf 1.031 verbessert.
• Vermutung: Die Autorin vermutet, dass die Konstante $c$ in $Rh(k) \sim c k \sqrt{\log k}$ tatsächlich 1 ist.

B. Exakte Werte für kleine $k$

• $Rh(3) = 5$: Jede 2-Färbung von $K_5$ enthält einen Zyklus (ein $K_3$-Minor). $K_4$ kann so gefärbt werden (zwei $P_4$), dass keine $K_3$-Minoren entstehen.
• $Rh(4) = 7$: Der Beweis nutzt strukturelle Eigenschaften von $K_4$-minor-freien Graphen (maximale Kantenzahl $2n-3$) und eine detaillierte Fallanalyse für$K_7$.

C. Allgemeine Anzahl von Farben ($\ell \ge 1$)

Für eine feste Anzahl von Farben $\ell$ und hinreichend große $k$ gilt:
$$Rh(k; \ell) = 2 \beta \ell k \sqrt{\log k} (1 + o(1))$$

• Obere Schranke: Folgt direkt aus der Summation der Kantenzahlen. Wenn $n$ zu groß ist, muss eine Farbklasse so viele Kanten haben, dass sie einen $K_k$-Minor erzwingt (basierend auf Thomasons Theorem).
• Untere Schranke: Wird durch eine Konstruktion erreicht, bei der $K_n$ in Kopien eines $K_k$-minor-freien Graphen $H$ zerlegt wird (unter Verwendung von Wilsons Theorem über Graphenzerlegungen und Nash-Williams für Wälder).

---

4. Signifikanz und Beitrag

1. Schließung einer Lücke: Das Papier etabliert erstmals explizit die Theorie der Ramsey-Zahlen für Minoren und verknüpft sie mit der Hadwiger-Vermutung und der Dichte-Frage.
2. Präzisierung der Konstanten: Durch die Verfeinerung des Beweises für die obere Schranke bei zwei Farben wird die Konstante signifikant verbessert (von $\approx 1.06$ auf $1.031$), was die Nähe zur vermuteten optimalen Konstante$1$ zeigt.
3. Verbindung von Disziplinen: Die Arbeit verbindet klassische Ramsey-Theorie, die Theorie der Graphenminoren (Hadwiger) und extremale Graphentheorie (Dichte-Schranken).
4. Methodische Innovation: Die Kombination von Konnektivitätsargumenten (Thomason) mit strukturellen Zerlegungen (Wilson, Alon/Yuster) bietet einen neuen Ansatz für das Lösen von Ramsey-Problemen, die nicht auf Cliquen, sondern auf Minoren basieren.

Fazit

Maria Axenovich liefert eine fundierte Analyse der Ramsey-Zahlen für Hadwiger-Minoren. Sie zeigt, dass diese Zahlen asymptotisch proportional zu $\ell k \sqrt{\log k}$ wachsen. Die Arbeit legt nahe, dass die zugrundeliegende Konstante für zwei Farben 1 ist, und liefert sowohl asymptotische als auch exakte Ergebnisse für kleine Instanzen, wobei sie neue Verbindungen zwischen der Dichte von Graphen und ihrer Minoren-Struktur herstellt.