On the $(k+2,k)$-problem of Brown, Erd\H{o}s and Sós for even integers $k$

In diesem Papier bestimmen die Autoren den exakten Grenzwert für das von Brown, Erdős und Sós gestellte $(k+2,k)$-Problem für jede gerade ganze Zahl $k \geq 4$ und Uniformität $r \geq 2+\sqrt{\frac{3}{2}k-4}$ und zeigen, dass dieser Wert $\frac{1}{r^2-r}$ beträgt.

Das Wesentliche

Das große Puzzle der Mathematik: Wie viele Teile passen in einen Kasten?

Stellen Sie sich vor, Sie haben einen riesigen Kasten mit vielen kleinen Steinen (das sind die Punkte oder Ecken). Ihre Aufgabe ist es, so viele Karten (das sind die Verbindungen oder Kanten) zwischen diesen Steinen zu legen wie möglich.

Aber es gibt eine strenge Regel: Wenn Sie sich eine bestimmte Anzahl von Karten zusammennehmen (sagen wir, $k$ Karten), dürfen diese Karten nicht zu viele Steine berühren. Wenn sie zu viele Steine berühren, ist das erlaubt. Wenn sie aber zu wenige Steine berühren, ist das verboten.

Die Mathematiker fragen sich: Wie viele Karten kann ich maximal in den Kasten legen, ohne gegen diese Regel zu verstoßen?

Das Rätsel der Brown-Erdős-Sós-Vermutung

Vor vielen Jahren haben drei kluge Köpfe (Brown, Erdős und Sós) eine Vermutung aufgestellt. Sie sagten: „Wenn der Kasten unendlich groß wird, dann gibt es eine ganz bestimmte Grenze, wie viele Karten pro Stein man maximal legen kann. Diese Grenze ist wie ein fester Wert, den man berechnen kann."

Für viele Jahre war dieses Rätsel extrem schwer. Man wusste zwar, dass die Zahl nicht unendlich groß wird, aber den exakten Wert zu finden, war wie der Versuch, den Inhalt eines verschlossenen Safe zu erraten, ohne den Code zu kennen.

Die neue Entdeckung: Ein besserer Schlüssel

In diesem neuen Papier haben Yan Wang und Jiasheng Zeng einen neuen, schlaueren Schlüssel gefunden, um diesen Safe für eine spezielle Gruppe von Problemen zu öffnen.

Das Problem:
Stellen Sie sich vor, die Karten sind nicht nur Verbindungen zwischen zwei Punkten, sondern verbinden immer $r$ Punkte gleichzeitig (wie ein Dreieck, das 3 Punkte verbindet, oder ein Viereck, das 4 verbindet).
Die Forscher haben sich auf Fälle konzentriert, bei denen die Anzahl der Karten ($k$) eine gerade Zahl ist (wie 4, 6, 8, 10...).

Die alte Lösung:
Ein anderes Team (Letzter und Sgueglia) hatte bereits einen Weg gefunden, um die Antwort zu berechnen. Aber ihr Schlüssel funktionierte nur, wenn der Kasten (die Struktur der Karten) sehr, sehr groß und komplex war. Man könnte sagen: „Es funktioniert, wenn Sie mindestens 1000 Karten pro Gruppe haben." Das war nicht ideal für kleinere Gruppen.

Die neue Lösung:
Wang und Zeng haben ihren Schlüssel geschärft. Sie haben gezeigt, dass man die Antwort schon viel früher finden kann. Ihr Schlüssel funktioniert bereits, wenn die Gruppen viel kleiner sind.

Die magische Formel:
Sie haben bewiesen, dass für alle geraden Zahlen $k$ (ab 4) und für eine bestimmte Größe des Kastens ($r$), die maximale Anzahl an Karten immer genau $1 / (r^2 - r)$ ist.

Das klingt trocken, aber hier ist die Analogie:
Stellen Sie sich vor, Sie bauen ein Haus mit $r$ Stockwerken. Die Forscher sagen: „Egal wie viele Zimmer ($k$) Sie in einem bestimmten Bereich haben wollen, solange das Haus groß genug ist, ist die maximale Anzahl an Fenstern, die Sie einbauen dürfen, immer genau ein bestimmter Bruchteil der Gesamtfläche."

Wie haben sie das gemacht? (Die Metapher des „Klebestreifens")

Statt sich jeden einzelnen Stein und jede Karte einzeln anzusehen (was wie das Zählen von Sandkörnern am Strand wäre), haben die Autoren eine cleverere Methode benutzt:

1. Das Zusammenkleben: Sie haben kleine Gruppen von Karten genommen und sie zu größeren „Clustern" zusammengeklebt.
2. Die Waage: Für jede dieser Gruppen haben sie eine imaginäre Waage benutzt. Sie haben jedem Punkt in der Gruppe ein kleines Gewicht gegeben.
3. Die Regel: Die wichtigste Regel war: „Die Summe aller Gewichte in einem Cluster darf niemals schwerer als 1 Kilogramm sein."
4. Der Trick: Sie haben gezeigt, dass wenn man die Karten so clever anordnet, wie es die mathematischen Regeln erlauben, man die Waage immer genau bis zum Limit (1 kg) füllen kann, ohne sie zu überladen.

Wenn man weiß, wie schwer die Waage maximal sein darf, kann man leicht berechnen, wie viele Karten insgesamt in den Kasten passen.

Warum ist das wichtig?

• Präzision: Früher wusste man nur, dass die Zahl irgendwo in der Nähe liegt. Jetzt wissen wir den exakten Wert.
• Effizienz: Ihre Methode funktioniert für viel kleinere Gruppen als die vorherige. Das ist wie ein Werkzeug, das nicht nur für riesige Baustellen, sondern auch für normale Hausrenovierungen funktioniert.
• Der Baustein: Dieses Ergebnis hilft anderen Mathematikern, noch größere und komplexere Rätsel zu lösen. Es ist wie ein neues, stabiles Fundament für ein Hochhaus.

Zusammenfassung in einem Satz

Wang und Zeng haben einen cleveren mathematischen Trick entwickelt, um genau zu berechnen, wie viele Verbindungen man in einem riesigen Netzwerk machen kann, ohne ein bestimmtes Muster zu erzeugen – und sie haben gezeigt, dass diese Grenze für viele Fälle viel früher erreicht wird als bisher angenommen.

Die Moral der Geschichte: Manchmal muss man nicht den ganzen Ozean leeren, um zu wissen, wie viel Wasser darin ist. Man braucht nur den richtigen Eimer und die richtige Formel.

Technische Zusammenfassung

Titel und Kontext

Das Papier mit dem Titel *"On the $p_k, kq$-problem of Brown, Erdős and Sós for even integers $k$" von Yan Wang und Jiasheng Zeng (veröffentlicht am 23. März 2026) befasst sich mit einem zentralen Problem der extremalen Hypergraphentheorie: der Bestimmung der genauen asymptotischen Dichte von Hypergraphen, die bestimmte Konfigurationen vermeiden.

1. Das Problem

Das Kernproblem ist die Untersuchung der Funktion $f^{(r)}(n; s, k)$, die die maximale Anzahl an Kanten in einem $r$-uniformen Hypergraphen mit $n$ Knoten angibt, in dem jede Auswahl von $k$ Kanten mehr als $s$ Knoten spannt.

• Konjektur von Brown, Erdős und Sós (1973): Für $r=3$ und $s=k+3$ wurde vermutet, dass $f^{(3)}(n; k+3, k) = o(n^2)$. Dies ist als $(k+3, k)$-Konjektur bekannt und für $k \ge 3$ weitgehend offen.
• Der untersuchte Fall: Die Autoren konzentrieren sich auf den Fall, in dem die Größenordnung durch $f^{(r)}(n; (r-2)k+2, k) = \Theta(n^2)$ gegeben ist. Hier ist die Frage, ob der Grenzwert
  $$\pi(r, k) := \lim_{n \to \infty} n^{-2} f^{(r)}(n; (r-2)k+2, k)$$
  existiert und welchen genauen Wert er annimmt.
• Bekannter Stand: Für $r=3$ wurde die Existenz des Grenzwerts kürzlich von Delcourt und Postle bewiesen. Für kleine $k$ und bestimmte $r$ wurden exakte Werte bestimmt (z.B. $\pi(3,2)=1/6$, $\pi(3,3)=1/5$). Für gerade $k$ und große $r$ zeigten Letzter und Sgueglia, dass $\pi(r, k) = \frac{1}{r^2-r}$ gilt, sofern $r$ groß genug ist (spezifisch $r \gtrsim \sqrt{2} k^{3/2}$).

2. Methodik

Die Autoren verwenden eine Kombination aus struktureller Analyse und einer gewichteten Zählmethode (Weighting Method), die auf Arbeiten von Glock, Joos, Kim, Kühn, Lichev, Pikhurko und Shangguan aufbaut.

• Vermeidung von Konfigurationen: Der Beweis konzentriert sich auf $G_k^{(r)}$-freie Hypergraphen, wobei $G_k^{(r)}$ die Familie aller $k$-Konfigurationen (Kantenmenge der Größe $k$ mit höchstens $(r-2)k+2$ Knoten) und aller $\ell^-$-Konfigurationen für $\ell < k$ umfasst.
• Cluster-Merging (Zusammenführung):
  • Der Hypergraph wird in "1-Cluster" (maximale zusammenhängende Teilgraphen) zerlegt.
  • Anschließend werden diese Cluster iterativ zu "2-Cluster" zusammengeführt, basierend auf der "Mergeability" (Zusammenführbarkeit) von Kantenpaaren. Zwei Cluster sind $(A|B)$-zusammenführbar, wenn sie bestimmte Schnittmengen von Kanten und Knoten aufweisen.
  • Die Struktur dieser Cluster wird durch die Eigenschaft "Property P" analysiert, die das Vorhandensein flexibler "Diamanten" (zwei Kanten, die genau zwei Knoten teilen) und deren Anordnung beschreibt.
• Gewichtszuweisung:
  • Den Knotenpaaren innerhalb der Cluster werden Gewichte zugewiesen ($w_F(xy)$), basierend darauf, ob das Paar durch 1 Kante oder 2 Kanten "behauptet" (claimed) wird.
  • Ein zentrales Lemma (Lemma 3.13) zeigt, dass die Summe der Gewichte für jedes Knotenpaar über alle Cluster hinweg höchstens 1 beträgt.
  • Durch den Vergleich der Anzahl der Kanten in einem Cluster mit der Summe der zugewiesenen Gewichte wird eine obere Schranke für die Gesamtzahl der Kanten hergeleitet.

3. Hauptergebnisse

Das Papier liefert einen signifikanten Fortschritt bei der Bestimmung des Schwellenwerts für $r$, ab dem die exakte Formel für $\pi(r, k)$ gilt.

• Theorem 1.2 (Hauptresultat): Für jede gerade ganze Zahl $k \ge 4$ und jede Uniformität $r$ mit
  $$r \ge 2 + \sqrt{\frac{3}{2}k - 4}$$
  gilt:
  $$\pi(r, k) = \frac{1}{r^2 - r}$$
• Verbesserung gegenüber vorherigen Arbeiten:
  • Letzter und Sgueglia hatten gezeigt, dass die Formel für $r \gtrsim \sqrt{2} k^{3/2}$ gilt.
  • Die neuen Autoren verbessern die untere Schranke für $r$ auf $\Theta(k^{1/2})$ (spezifisch $r \approx \sqrt{1.5k}$).
  • Dies bedeutet, dass die exakte Dichte $\frac{1}{r^2-r}$ bereits für deutlich kleinere Werte von $r$ (im Verhältnis zu $k$) erreicht wird als bisher angenommen.
• Spezialfälle:
  • Für $k=4$ ergibt sich $r \ge 4$, was mit früheren Ergebnissen übereinstimmt.
  • Für $k=6$ und $k=8$ zeigt das Ergebnis, dass $r_0(k) \le 5$ gilt (wobei $r_0(k)$ der kleinste Wert ist, ab dem die Formel gilt).

4. Technische Details und Beweisskizze

• Untere Schranke: Folgt direkt aus Lemma 3.1, indem ein einzelner Hypergraph mit einer Kante als Beispiel verwendet wird, was die untere Schranke $\frac{1}{r^2-r}$ liefert.
• Obere Schranke:
  • Es wird gezeigt, dass für $G_k^{(r)}$-freie Graphen die Anzahl der Kanten $|G|$ durch $\binom{r}{2}^{-1} \binom{n}{2}$ beschränkt ist.
  • Der Schlüssel liegt in Lemma 3.14, das beweist, dass für $r \ge 2 + \sqrt{\frac{3}{2}k - 4}$ die Gesamtgewichtung $w(F)$ eines Clusters $F$ mindestens $\binom{r}{2}|F|$ beträgt.
  • Dies erfordert eine präzise Analyse der Struktur von Clustern mit $|F| \ge k+1$ (Theorem 3.7 und 3.8), die zeigen, dass solche Cluster aus einer spezifischen Anordnung von Diamanten und kleinen Clustern bestehen müssen, die die "Property P" erfüllen.
  • Die algebraische Ungleichung, die aus der Gewichtung resultiert, führt unter der neuen Bedingung für $r$ zu einem Widerspruch, falls die Kantenanzahl zu hoch wäre.

5. Bedeutung und Ausblick

• Lösung des Problems für gerade $k$: Das Papier schließt eine Lücke in der Bestimmung der exakten Werte von $\pi(r, k)$ für gerade $k$ und erweitert den Gültigkeitsbereich der Formel $\frac{1}{r^2-r}$ erheblich.
• Optimierung der Schwellenwerte: Die Reduktion des benötigten $r$ von $\Theta(k^{3/2})$ auf $\Theta(k^{1/2})$ ist ein wesentlicher Fortschritt in der extremalen Kombinatorik. Es zeigt, dass die strukturellen Einschränkungen durch das Vermeiden von $k$-Konfigurationen bereits bei viel niedrigeren Uniformitäten wirken als bisher gedacht.
• Offene Fragen: Die Autoren stellen das Problem 4.1: Bestimmung des kleinsten $r_0(k)$ für gegebene gerade $k$. Während ihre Arbeit eine obere Schranke liefert, bleibt die Frage offen, ob $r_0(k) = 4$ für alle $k \in \{6, 8, \dots\}$ gilt (was optimal wäre). Für $k=6,8$ deuten frühere Arbeiten darauf hin, dass $r_0(k)=4$ möglich sein könnte, erfordert aber noch feinere Gewichtszuweisungen.

Zusammenfassend liefert das Papier einen eleganten Beweis für die Existenz und den genauen Wert des Grenzwerts $\pi(r, k)$ für eine breitere Klasse von Parametern als zuvor bekannt, indem es die strukturelle Analyse von Hypergraph-Clustern mit einer optimierten Gewichtsmethode kombiniert.