On the maximum number of tangencies among $1$-intersecting curves

Die Autoren verbessern die bekannten oberen Schranken für die maximale Anzahl von Berührungspunkten bei Familien von Jordan-Bögen, die sich höchstens einmal schneiden, von $O(n^{7/4})$ bzw. $O(n^{7/4})$ auf $O(n^{5/3})$ und $O(n^{3/2})$ und beweisen zudem eine verallgemeinerte graphentheoretische Aussage.

Das Wesentliche

Stellen Sie sich vor, Sie haben eine große Schachtel voller langer, flexibler Gummibänder. Diese Gummibänder liegen auf einem Tisch und bilden ein verworrenes Netz. In der Welt der Mathematik nennen wir diese Gummibänder „Kurven" und den Tisch die „Ebene".

Die Forscher Eyal Ackerman und Balázs Keszegh haben sich in diesem Papier eine sehr spezifische Frage gestellt: Wie oft können sich diese Gummibänder berühren, ohne sich zu durchdringen?

Hier ist die einfache Erklärung der wichtigsten Punkte, gemischt mit ein paar anschaulichen Bildern:

1. Das Grundproblem: Die „Berührungs-Party"

Stellen Sie sich vor, jedes Gummiband ist eine Person auf einer Party.

• Die Regel: Jede Person darf sich mit jeder anderen Person genau einmal treffen. Das kann ein Händedruck sein (ein Kreuzungspunkt) oder ein sanftes Berühren der Schulter (ein Tangentialpunkt).
• Das Verbot: Niemand darf sich an derselben Stelle mit drei Personen gleichzeitig treffen.
• Die Frage: Wenn wir 100 Gummibänder haben, wie oft können sie sich maximal nur berühren (ohne sich zu kreuzen), bevor das Chaos unüberschaubar wird?

Früher dachten die Mathematiker, die Antwort sei einfach: „Wenn du $n$ Gummibänder hast, gibt es höchstens eine lineare Anzahl an Berührungen (also etwa $n$)." Das wäre wie zu sagen: „Bei 100 Gästen gibt es höchstens 100 Händedrücke."

Aber das war zu optimistisch! Die Forscher haben bewiesen, dass es etwas mehr sein kann, aber immer noch überschaubar bleibt.

2. Die neuen Entdeckungen: Ein besserer Zähler

Die Autoren haben die alten, etwas ungenauen Schätzungen verbessert. Sie haben neue, schärfere Grenzen gefunden:

• Für ganz beliebige Gummibänder: Früher dachte man, es könnte bis zu $n^{1,75}$ Berührungen geben (eine ziemlich hohe Zahl). Die neuen Forscher sagen: „Nein, es ist eher wie $n^{1,66}$." Das ist wie ein Sicherheitsventil, das verhindert, dass das System explodiert.
• Für Gummibänder, die sich nur einmal treffen: Hier haben sie die Grenze von $n^{1,75}$ auf $n^{1,5}$ gesenkt. Das ist ein riesiger Fortschritt. Stellen Sie sich vor, Sie haben eine Tüte mit 1000 Gummibändern. Die alte Rechnung sagte, es könnten sich 30.000 Mal berühren. Die neue Rechnung sagt: „Nein, maximal 31.600." (Die Zahlen sind nur zur Veranschaulichung der Exponenten).

3. Der Spezialfall: Die „Morgenlatte"-Regel

Ein besonders spannendes Ergebnis betrifft Gummibänder, die alle an einer geraden Linie hängen (wie Wäsche an einer Leine) und nur in eine Richtung wachsen (nach rechts).

• Die Situation: Alle Gummibänder starten an derselben vertikalen Leine links im Bild.
• Das Ergebnis: Hier ist die maximale Anzahl an Berührungen exakt berechnet: Es ist proportional zu $n^{1,33}$.
• Die Analogie: Stellen Sie sich vor, Sie haben viele Schlangen, die alle aus demselben Loch im Boden kommen. Wie oft können sie sich aneinander reiben, bevor sie sich verheddern? Die Antwort ist: Genau so oft, wie die Formel $n^{4/3}$ sagt. Das ist ein sehr präzises Ergebnis, das fast perfekt mit der unteren Grenze übereinstimmt.

4. Der mathematische „Super-Trick"

Um diese Ergebnisse zu beweisen, mussten die Autoren ein neues Werkzeug aus dem Werkzeugkasten der Graphentheorie (der Mathematik von Punkten und Verbindungen) entwickeln.

Stellen Sie sich vor, Sie haben eine riesige Stadt (den Graphen), in der die Straßen (die Verbindungen) sehr spärlich sind, wenn man bestimmte Stadtteile betrachtet.

• Der alte Trick: Früher sagten Mathematiker: „Wenn in jedem kleinen Stadtviertel nicht zu viele Straßen sind, dann ist die ganze Stadt nicht zu groß."
• Der neue Trick (Satz 8): Die Autoren haben gezeigt: „Selbst wenn wir nur wissen, dass die Nachbarschaften von zwei benachbarten Häusern nicht überfüllt sind, können wir trotzdem sagen, dass die ganze Stadt eine bestimmte Größe nicht überschreiten kann."

Das ist wie ein Detektiv, der nicht die ganze Stadt durchsuchen muss, sondern nur ein paar spezifische Nachbarschaften prüft, um zu wissen, wie viele Häuser es maximal geben kann. Dieser Trick ist so nützlich, dass er auch in anderen Bereichen der Mathematik helfen könnte, etwa bei der Analyse von Netzwerken oder Datenstrukturen.

5. Warum ist das wichtig?

Warum beschäftigen sich Leute damit, wie oft Gummibänder sich berühren?

• Roboter: Wenn ein Roboterarm sich durch einen Raum bewegt, muss er wissen, wie viele Hindernisse er umgehen muss. Die „Berührungen" sind hier die kritischen Punkte, an denen Kollisionen passieren könnten.
• Computergrafik: Um 3D-Bilder zu rendern, müssen Computer wissen, wie Objekte sich schneiden oder berühren. Je besser wir die Grenzen kennen, desto schneller und effizienter werden die Programme.
• Optimierung: Es hilft uns zu verstehen, wie komplex ein System werden kann, bevor es unkontrollierbar wird.

Zusammenfassung

Die Autoren haben bewiesen, dass das Chaos in einem System von sich berührenden Kurven nicht so wild ist, wie man dachte. Sie haben die Grenzen verschärft und dabei ein neues, mächtiges mathematisches Werkzeug entwickelt, das wie ein verfeinerter Kompass funktioniert, um die Dichte von Verbindungen in komplexen Netzwerken vorherzusagen.

Kurz gesagt: Sie haben die Regeln für das „Gummiband-Chaos" neu geschrieben und dabei gezeigt, dass die Welt zwar verworren, aber mathematisch gut beherrschbar ist.

Technische Zusammenfassung

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

Titel und Autoren

Titel: On the maximum number of tangencies among 1-intersecting curves (Über die maximale Anzahl von Berührungspunkten bei 1-schneidenden Kurven)
Autoren: Eyal Ackerman und Balázs Keszegh
Datum: 13. März 2026 (vorgelegt als Preprint)

---

1. Problemstellung

Das Paper untersucht die maximale Anzahl von Berührungspunkten (Tangenzialpunkten) in einer Familie von $n$ Jordan-Bögen (planaren Kurven) unter bestimmten Schnittbedingungen.

• Definitionen:
  • Eine Kurvenfamilie ist $k$-schneidend, wenn sich je zwei Kurven in höchstens $k$ Punkten schneiden.
  • Zwei Kurven sind tangential (berührend), wenn sie genau einen gemeinsamen Punkt haben, der kein Kreuzungspunkt ist.
  • Eine Familie ist präzise 1-schneidend, wenn sich je zwei Kurven in genau einem Punkt schneiden (entweder Kreuzung oder Berührung).
  • Es wird angenommen, dass keine drei Kurven einen gemeinsamen Punkt teilen.
• Ziel: Bestimmung der asymptotischen oberen Schranke für die Anzahl der Tangenzialpaare in Abhängigkeit von $n$.
• Hintergrund:
  • Eine Vermutung von Pach besagt, dass für präzise 1-schneidende Kurven die Anzahl der Tangenzen $O(n)$ beträgt. Dies wurde bisher nur für Spezialfälle bewiesen.
  • Der beste bekannte allgemeine obere Schrankenwert lag bei $O(n^{7/4})$ (basierend auf einem Ergebnis von Keszegh und Pálvölgyi).
  • Für den Fall, dass Kurven $x$-monoton sind, war die beste bekannte Schranke $O(n^{4/3}(\log n)^{2/3})$ (Pach und Sharir).

---

2. Methodik und Werkzeuge

Die Autoren verwenden eine Kombination aus geometrischer Kombinatorik, Graphentheorie und rekursiven Zerlegungstechniken.

A. Graphentheoretische Verallgemeinerung (Theorem 8 & 9)

Ein zentraler Beitrag ist ein neuer graphentheoretischer Satz, der ein Ergebnis von Erdős und Simonovits erweitert.

• Konzept: Zwei Knoten $u, v$ haben $f$-sparse Sub-Binachbarschaften, wenn die Anzahl der Kanten zwischen beliebigen disjunkten Teilmengen ihrer offenen Nachbarn durch eine Funktion $f$ begrenzt ist.
• Theorem 8: Wenn in einem Graphen $G$ jedes Paar von Knoten $f$-sparse Sub-Binachbarschaften hat und $f(n) = O(n^{2-\alpha})$, dann ist die Anzahl der Kanten $|E(G)| = O(|V|^{2 - \frac{\alpha}{\alpha+1}})$.
• Bedeutung: Dies verallgemeinert den Satz von Erdős-Simonovits und liefert eine scharfe untere Schranke (Theorem 9), die zeigt, dass die obere Schranke asymptotisch scharf ist.

B. Geometrische Zerlegung (Cutting Lemma)

Für $x$-monotone Kurven wird das Cutting Lemma (Theorem 10) verwendet, um die Ebene in generalized trapezoids (allgemeine Trapeze) zu zerlegen, sodass jede Trapezregion nur von einer kleinen Teilmenge der Kurven geschnitten wird. Dies ermöglicht eine rekursive Analyse der Tangenzialpunkte innerhalb und zwischen diesen Regionen.

C. Topologische Argumente

• Proposition 1 & 2: Es werden topologische Eigenschaften genutzt, um zu zeigen, dass bestimmte Konfigurationen von Berührungspunkten (z. B. bei "geerdeten" Kurven) zu Widersprüchen führen, wenn sie zu häufig auftreten.
• Verwendung des Kővári-Sós-Turán-Theorems: Um die Anzahl der Kanten in bipartiten Graphen zu begrenzen, die keine vollständigen bipartiten Teilgraphen $K_{s,t}$ enthalten.
• Davenport-Schinzel-Folgen: Werden im Kontext von unteren Hüllen (lower envelopes) von Kurven verwendet, um die Komplexität von Berührungsmustern zu analysieren.

---

3. Hauptergebnisse

Die Autoren verbessern die bekannten oberen Schranken für verschiedene Klassen von Kurvenfamilien signifikant:

A. Allgemeine 1-schneidende Kurven (Arbitrary 1-intersecting)

• Theorem 2: Für eine Familie von $n$ beliebigen 1-schneidenden Kurven ist die maximale Anzahl der Tangenzen $O(n^{5/3})$.
  • Verbesserung: Reduzierung von $O(n^{7/4})$ auf $O(n^{5/3})$.
• Theorem 3: Für eine Familie von $n$ präzise 1-schneidenden Kurven ist die maximale Anzahl der Tangenzen $O(n^{3/2})$.
  • Bedeutung: Dies ist ein wichtiger Schritt zur Beweiserung der Pach-Vermutung ($O(n)$), auch wenn die Vermutung selbst noch offen bleibt.

B. $x$-monotone Kurven

• Theorem 4: Für $n$ 1-schneidende $x$-monotone Kurven ist die maximale Anzahl der Tangenzen $O(n^{4/3}(\log n)^{1/3})$.
  • Verbesserung: Dies verbessert die Schranke von Pach und Sharir um einen Faktor von $(\log n)^{1/3}$.
  • Untere Schranke: Es existiert eine Konstruktion mit $\Omega(n^{4/3})$ Tangenzen (basierend auf der Erdős-Konstruktion für Punkt-Linie-Inzidenzen).

C. Geerdete $x$-monotone Kurven (Grounded)

• Theorem 5: Wenn die linken Endpunkte aller $n$ $x$-monotonen 1-schneidenden Kurven auf einer gemeinsamen vertikalen Linie liegen, ist die maximale Anzahl der Tangenzen $\Theta(n^{4/3})$.
  • Dies ist eine asymptotisch scharfe Schranke (Upper und Lower Bound stimmen überein).

D. Bi-infinit $x$-monotone Kurven

• Theorem 6: Für $n$ bi-infinit $x$-monotone 1-schneidende Kurven ist die maximale Anzahl der Tangenzen $\Theta(n \log n)$.
  • Im Fall präziser 1-Schnitte ist die Anzahl genau $n-1$.

---

4. Signifikanz und Implikationen

1. Lösung offener Probleme: Das Paper schließt die Lücke zwischen den bekannten unteren Schranken ($\Omega(n^{4/3})$) und den oberen Schranken für $x$-monotone Kurven erheblich. Für den "geerdeten" Fall wird das Problem vollständig gelöst ($\Theta(n^{4/3})$).
2. Graphentheoretischer Durchbruch: Theorem 8 ist ein eigenständiges Ergebnis von graphentheoretischem Interesse. Es verallgemeinert den Satz von Erdős und Simonovits und liefert eine scharfe untere Schranke für eine Klasse von Graphen, die durch Sparsamkeit in den Nachbarschaften definiert sind. Dies könnte Anwendungen in anderen Bereichen der extremalen Kombinatorik finden.
3. Technische Innovation: Die Kombination aus der Verallgemeinerung von Erdős-Simonovits mit geometrischen Zerlegungsmethoden (Cutting Lemma) und topologischen Einschränkungen (Propositionen über Berührungstypen) stellt einen neuen Ansatz zur Analyse von Kurvenanordnungen dar.
4. Zusammenhang zu anderen Problemen: Die Ergebnisse haben direkte Implikationen für Probleme wie die Unit-Distance-Problematik, die Komplexität von Arrangements (Anzahl der Flächen der Größe 2) und die Analyse von Algorithmen zur Linienabdeckung (Bentley-Ottmann).

Zusammenfassung der Verbesserungen (Tabelle 1 im Paper)

Kurventyp	Bisher beste obere Schranke	Neue obere Schranke
Beliebig, 1-schneidend	$O(n^{7/4})$	$O(n^{5/3})$
Beliebig, präzise 1-schneidend	$O(n^{7/4})$	$O(n^{3/2})$
$x$-monoton, 1-schneidend	$O(n^{4/3}(\log n)^{2/3})$	$O(n^{4/3}(\log n)^{1/3})$
Geerdet, $x$-monoton	$\Omega(n^{4/3}), O(n^{3/2})$	$\Theta(n^{4/3})$ (Scharf)

Das Paper liefert somit die bisher besten bekannten Ergebnisse für die maximale Anzahl von Tangenzialpunkten in diesen Kurvenfamilien und stellt ein mächtiges neues graphentheoretisches Werkzeug für zukünftige Forschung bereit.