2025-11-12T07:25:09.921673

Bipartite Turán number of paths and other trees

Bonamy, Leclere, Picavet
We solve a recent question of Caro, Patkós and Tuza by determining the exact maximum number of edges in a bipartite connected graph as a function of the longest path it contains as a subgraph and of the number of vertices in each side of the bipartition. This was previously known only in the case where both sides of the bipartition have equal size and the longest path has size at most $5$. We also discuss possible generalizations replacing "path" with some specific types of trees.
academic

Bipartite Turán-Zahl von Pfaden und anderen Bäumen

Grundinformationen

  • Papier-ID: 2511.07374
  • Titel: Bipartite Turán number of paths and other trees
  • Autoren: Marthe Bonamy, Théotime Leclere, Timothé Picavet
  • Institutionen: CNRS, LaBRI, Université de Bordeaux; ENS Paris-Saclay
  • Klassifizierung: math.CO (Kombinatorik), cs.DM (Diskrete Mathematik)
  • Veröffentlichungsdatum: 11. November 2025
  • Papier-Link: https://arxiv.org/abs/2511.07374

Zusammenfassung

Dieses Papier löst vollständig ein kürzlich von Caro, Patkós und Tuza gestelltes Problem: die Bestimmung des exakten Maximalwerts der Kantenzahl in zusammenhängenden bipartiten Graphen, wobei dieser Maximalwert eine Funktion der längsten Pfadlänge im Graphen und der Anzahl der Knoten auf beiden Seiten der bipartiten Zerlegung ist. Zuvor war dieses Problem nur für den Fall bekannt, dass die beiden Seiten der bipartiten Zerlegung gleich groß sind und die längste Pfadlänge höchstens 5 beträgt. Das Papier diskutiert auch mögliche Verallgemeinerungen, bei denen „Pfade" durch bestimmte Baumtypen ersetzt werden.

Forschungshintergrund und Motivation

Problemhintergrund

  1. Klassisches Turán-Problem: Das Turán-Theorem bestimmt die maximale Kantenzahl in einem n-Knoten-Graphen, der keinen vollständigen Untergraphen einer gegebenen Ordnung enthält. Dies eröffnete die systematische Untersuchung von Extremalproblemen mit verbotenen Untergraphen.
  2. Einschränkungen des Erdős-Stone-Theorems: Dieses Theorem gibt asymptotisch die Turán-Zahlen für alle nicht-bipartiten verbotenen Graphen an, liefert aber für den bipartiten Fall keine Informationen.
  3. Besonderheiten bipartiter Graphen: Das Turán-Problem für bipartite Graphen bleibt offen und hat mehrere Kernvermutungen hervorgebracht, von denen die berühmteste die Erdős-Sós-Vermutung ist: Ein n-Knoten-Graph, der einen Baum mit k Knoten ausschließt, hat höchstens (k-2)n/2 Kanten.
  4. Forschung zu zusammenhängenden bipartiten Graphen: Caro, Patkós und Tuza CPT25 konzentrierten sich kürzlich auf den Fall, in dem der Gastgraph sowohl bipartit als auch zusammenhängend ist. Sie führten die Notation exb,c(a,b,H) ein, um die maximale Kantenzahl in zusammenhängenden bipartiten Graphen mit Partitionsgrößen a und b zu bezeichnen, die H nicht als Untergraph enthalten.

Forschungsmotivation

  • Einschränkungen bekannter Ergebnisse: CPT25 löste nur den Fall aller Bäume mit 6 oder weniger Knoten, Doppelsterne und bestimmte Spinnengraphen. Insbesondere war nur exb,c(n,n,P₅) = exb,c(n,n,P₆) = 2n-1 bekannt
  • Offene Probleme: Es ist notwendig, exb,c(n,n,Pₖ) für beliebige Pfade Pₖ zu bestimmen, zumindest asymptotische Werte zu geben
  • Verallgemeinerungsbedarf: Es ist erforderlich, exb,c-Werte für bestimmte Baumfamilien zu untersuchen

Kernbeiträge

  1. Vollständige Lösung des Pfadproblems: Für alle Pfade Pₖ werden exakte Werte von exb,c(a,b,Pₖ) angegeben, nicht nur asymptotische Werte, sondern auch für unausgeglichene bipartite Graphen (Hauptsatz 1.5)
  2. Erweiterung auf Besengraphen: Für Besengraphen Sp,d* (Kombination eines Pfads der Länge p und eines Sterns mit d Ästen) werden exakte Werte angegeben, wenn der Stern größer als der Pfad ist (Satz 1.6)
  3. Obere Schranken: Wenn der Stern höchstens die Hälfte der Pfadgröße ist, werden obere Schranken bereitgestellt (Satz 1.7)
  4. Technische Innovationen: Es werden neue Techniken zur Behandlung zusammenhängender bipartiter Graphen entwickelt, einschließlich eines Existenzlemmas für kritische Knoten und eines Induktionsrahmens

Methodische Erläuterung

Aufgabendefinition

Definition 1.1: Für feste ganze Zahlen a, b und einen Graphen H ist exb,c(a,b,H) die maximale Kantenzahl in zusammenhängenden bipartiten Graphen mit Partitionsgrößen a und b, die H nicht als Untergraph enthalten.

Diese Arbeit untersucht hauptsächlich:

  • Eingabe: Pfadlänge k, bipartite Partitionsgrößen a, b
  • Ausgabe: Exakte Wert von exb,c(a,b,Pₖ)
  • Einschränkungen: Der Graph muss zusammenhängend, bipartit sein und Pₖ nicht als Untergraph enthalten

Kernsätze

Satz 1.5 (Hauptergebnis): Für alle k ≥ 3 und b ≥ a ≥ k gilt: exb,c(a,b,P2k)=exb,c(a,b,P2k−1)=(k−2)(b−1)+a\text{ex}_{b,c}(a,b,P_{2k}) = \text{ex}_{b,c}(a,b,P_{2k-1}) = (k-2)(b-1) + a

Diese Formel zeigt:

  • Pfade mit ungerader und gerader Länge haben die gleiche Turán-Zahl
  • Die Kantenzahl wächst linear mit dem größeren Teil b, mit Koeffizient (k-2)
  • Es gibt einen additiven Korrekturterm a

Beweisarchitektur

1. Untere Schranke Konstruktion (Abschnitt 2)

Proposition 2.1 liefert einen konstruktiven Beweis:

Konstruktion eines Graphen G mit bipartiter Zerlegung A = {u₁,...,uₐ} und B = {v₁,...,vᵦ}:

  • Die ersten k-2 Knoten in A sind vollständig mit allen Knoten in B verbunden (bilden Kₖ₋₂,ᵦ)
  • Die verbleibenden a-(k-2) Knoten in A sind Blätter, alle verbunden mit einem bestimmten Knoten in B

Kantenanzahlberechnung: ∣E(G)∣=b(k−2)+(a−(k−2))=(k−2)(b−1)+a|E(G)| = b(k-2) + (a-(k-2)) = (k-2)(b-1) + a

P₂ₖ₋₁-freie Eigenschaft Beweis:

  • Der vollständige bipartite Graph Kₖ₋₂,ᵦ hat einen längsten Pfad mit 2k-3 Knoten
  • Die hinzugefügten Blätter können den Pfad nicht verlängern, da sie alle Grad 1 haben

2. Obere Schranke Beweis (Abschnitt 3)

Verwendet Induktion mit drei Schlüssellemmata:

Lemma 3.2 (Existenz von Knoten mit kleinem Grad): Im größeren Teil B existiert ein Knoten x mit Grad ≤ k-2, dessen Entfernung den Graphen zusammenhängend erhält.

Beweisidee:

  • Verwende DFS-Baum, um ein Blatt b in B zu finden
  • Wenn d(b) ≤ k-2, setze x = b
  • Wenn d(b) = k-1, muss die Pfadlänge 2k-2 sein, was zu einem Zyklus führt
  • In diesem Fall kann man einen anderen Knoten b' mit Grad ≤ k-2 finden

Lemma 3.3 (Löschbare Knotenpaare in ausgeglichenen Graphen): Für ausgeglichene bipartite Graphen existieren zwei Knoten x, y mit d(x) + d(y) ≤ k-1, deren Entfernung den Graphen zusammenhängend und ausgeglichen erhält.

Der Beweis verwendet Analyse der Endpunkte des längsten Pfads P:

  • Wenn Endpunkte in verschiedenen Teilen sind, können sie möglicherweise direkt verwendet werden
  • Andernfalls verwende DFS-Baum, um ein geeignetes Blatt-Paar zu finden

Lemma 3.4 (Basisfall): Wenn a = b = k, dann |E(G)| ≤ (k-1)² + 1.

Der Beweis verwendet Induktion, mit Schlüsselbeobachtung:

  • Finde einen Knoten x mit minimalem Grad, der kein Schnittknoten ist
  • Analysiere die Struktur des verbleibenden Graphen nach Entfernung von x
  • Nutze die P₂ₖ-freie Eigenschaft, um Grad und Struktur zu begrenzen

Hauptsatzbeweis:

  • Wenn b > a: Verwende Lemma 3.2, um einen Knoten zu löschen, dann Induktion
  • Wenn a = b > k: Verwende Lemma 3.3, um zwei Knoten zu löschen, dann Induktion
  • Wenn a = b = k: Verwende Lemma 3.4

Ergebnisse für Besengraphen

Satz 1.6: Für k, d ≥ 2, wenn n ≥ d²/2 und d > 2k, dann: exb,c(n,n,S2k,d)=exb,c(n,n,S2k+1,d)=nd\text{ex}_{b,c}(n,n,S_{2k,d}) = \text{ex}_{b,c}(n,n,S_{2k+1,d}) = nd

Schlüsseltechnisches Lemma:

Lemma 4.1: Wenn der Graph einen Knoten enthält, der nicht Endpunkt eines 2k-Pfads ist, dann |E(G)| ≤ (k-1)(b+a)

Lemma 4.2: Wenn |E(G)| ≥ k(b+a)+1, dann hat jeder Knoten Grad höchstens k+d-1

Der Beweis kombiniert diese Lemmata, indem er Knoten mit maximalem Grad und ihre Nachbarn löscht und dabei Zusammenhängigkeit und Gradbeschränkungen nutzt, um einen Widerspruch zu erhalten.

Experimentelle Einrichtung

Als rein theoretisches mathematisches Papier enthält diese Arbeit keinen experimentellen Teil. Alle Ergebnisse werden durch rigorose mathematische Beweise erhalten.

Experimentelle Ergebnisse

Verifikation der Hauptergebnisse

Exakte Formel für Pfade:

  • Für P₅ und P₆: exb,c(n,n,P₅) = exb,c(n,n,P₆) = 2n-1
    • Mit Formel: k=3, (3-2)(n-1)+n = n-1+n = 2n-1 ✓
  • Für allgemeines Pₖ: Die Formel gibt exakte Werte für alle Fälle, einschließlich unausgeglichener bipartiter Graphen

Besengraph-Ergebnisse:

  • Wenn der Sternteil dominant ist (d > 2k), ist die Turán-Zahl nd
  • Dies stimmt mit Maximalgradbeschränkungen überein

Vergleich mit bekannten Ergebnissen

  1. Verallgemeinerung von Proposition 1.2: Die Ergebnisse dieses Papiers enthalten vollständig und verallgemeinern exb,c(n,n,P₅) = 2n-1 aus CPT25
  2. Erhöhte Allgemeinheit:
    • Erweiterung von ausgeglichenen auf unausgeglichene Graphen
    • Erweiterung von speziellen kleinen Pfaden auf beliebige Pfade
    • Von asymptotischen Ergebnissen zu exakten Formeln

Verwandte Arbeiten

Klassische Ergebnisse

  1. Turán-Theorem Tur45: Extremalproblem für vollständige Graphen
  2. Erdős-Stone-Theorem ES46: Asymptotische Turán-Zahlen für nicht-bipartite Graphen
  3. Gallai-Erdős GE59: Asymptotische Ergebnisse für zusammenhängende Graphen, die Pfade fester Größe ausschließen
  4. Gyárfás-Rousseau-Schelp GRS84: Exakte Turán-Zahlen für bipartite Graphen, die Pfade fester Größe ausschließen

Direkt verwandte Arbeiten

Caro-Patkós-Tuza CPT25:

  • Führte die exb,c-Notation ein
  • Löste den Fall kleiner Bäume (≤ 6 Knoten)
  • Löste Doppelsterne und bestimmte Spinnengraphen
  • Stellte die in diesem Papier gelösten Probleme

Unabhängige Arbeiten

He-Salia-Zhu HSZ25: Die Autoren erwähnen unabhängige Arbeiten mit ähnlichen Fortschritten, die am selben Tag eingereicht wurden

Schlussfolgerungen und Diskussion

Hauptschlussfolgerungen

  1. Vollständige Beantwortung von Frage 1.3: Exakte Werte von exb,c(n,n,Pₖ) für alle Pfade Pₖ werden angegeben, was über die asymptotischen Werte hinausgeht, die die Frage fordert
  2. Teilweise Beantwortung von Frage 1.4: Für die Besengraph-Familie werden in bestimmten Parameterbereichen exakte Werte oder obere Schranken angegeben
  3. Methodologische Beiträge: Es wird ein neuer technischer Rahmen zur Behandlung von Extremalproblemen zusammenhängender bipartiter Graphen entwickelt

Einschränkungen

  1. Einschränkungen bei Besengraphen:
    • Satz 1.6 erfordert d > 2k und n ≥ d²/2
    • Satz 1.7 gibt nur obere Schranken, keine exakten Werte
    • Zwischenfälle (d ≈ k) sind nicht vollständig gelöst
  2. Allgemeiner Fall von Bäumen: Nur Pfade und Besengraphen werden behandelt, allgemeinere Baumfamilien bleiben offen
  3. Technische Einschränkungen: Einige Beweisschritte hängen von spezifischen Struktureigenschaften ab und lassen sich möglicherweise nicht auf komplexere verbotene Untergraphen verallgemeinern

Zukünftige Richtungen

  1. Verbesserung der Besengraph-Ergebnisse: Bestimmung exakter Werte für alle Parameterbereiche
  2. Erweiterung auf andere Baumfamilien:
    • Vollständige Charakterisierung von Spinnengraphen
    • Andere spezielle Baumstrukturen
  3. Tiefere Untersuchung des unausgeglichenen Falls: Obwohl dieses Papier den Fall a ≠ b behandelt, könnten verfeinerte Ergebnisse möglich sein
  4. Rechenkomplexität: Untersuchung algorithmischer Probleme zur Bestimmung, ob ein gegebener Graph die Turán-Schranke erreicht

Tiefgreifende Bewertung

Stärken

  1. Vollständige Lösung offener Probleme:
    • Beantwortet nicht nur Frage 1.3, sondern gibt auch stärkere exakte Formeln als gefordert
    • Erweiterung auf unausgeglichene bipartite Graphen erhöht die Allgemeinheit der Ergebnisse
  2. Elegante Beweistechniken:
    • Untere Schranke-Konstruktion ist prägnant und klar
    • Obere Schranke-Beweis hat klare Induktionsstruktur
    • Schlüssellemmata (3.2, 3.3, 3.4) sind prägnant formuliert und bewiesen
  3. Vollständigkeit der Ergebnisse:
    • Für Pfade werden exakte Formeln für alle Parameter angegeben
    • Formelform ist prägnant: (k-2)(b-1)+a
    • Einheitliche Behandlung von Pfaden mit ungerader und gerader Länge
  4. Schreibqualität:
    • Papierstruktur ist klar, Logik ist rigoros
    • Schlüsselschritte werden durch detaillierte Unterpropositionen gestützt
    • Abbildungen (wie Abbildung 1) helfen beim Verständnis der Konstruktion
  5. Technische Innovation:
    • Lemma 3.2 über die Existenz von Knoten mit kleinem Grad, die keine Schnittknoten sind, ist eine Schlüsseleinsicht
    • Die Charakterisierung löschbarer Knotenpaare in ausgeglichenen Graphen (Lemma 3.3) hat unabhängigen Wert
    • Die Verwendung von DFS-Bäumen durchzieht den Beweis und zeigt die effektive Anwendung klassischer Werkzeuge

Mängel

  1. Unvollständige Besengraph-Ergebnisse:
    • Es gibt einen Parameterlücke zwischen Satz 1.6 und 1.7
    • Satz 1.7 gibt nur obere Schranke 2nk+1 an, Abstand zur möglichen exakten Lösung ist unbekannt
    • Die Bedingung n ≥ d²/2 wirkt technisch, könnte möglicherweise nicht optimal sein
  2. Komplexer Basisfall-Beweis:
    • Der Beweis von Lemma 3.4 (Fall a=b=k) nimmt großen Platz ein
    • Benötigt mehrere Unterpropositionen (Claims 3.11-3.13)
    • Möglicherweise existiert direktere Argumentation
  3. Begrenzte Verallgemeinerbarkeit:
    • Methode hängt stark von speziellen Strukturen von Pfaden und Besengraphen ab
    • Unklar, wie diese Techniken auf allgemeine Bäume angewendet werden können
    • Keine Diskussion möglicher einheitlicher Rahmen
  4. Beziehung zu unabhängiger Arbeit:
    • Unabhängige Arbeit HSZ25 wird erwähnt, aber nicht detailliert verglichen
    • Unklar, ob technische Methoden beider Papiere identisch sind

Auswirkungen

  1. Theoretische Beiträge:
    • Vollständige Lösung eines klar gestellten offenen Problems
    • Bereitstellung neuer technischer Werkzeuge für das Problem der zusammenhängenden bipartiten Turán-Zahlen
    • Die Genauigkeit der Ergebnisse macht sie zum Benchmark in diesem Bereich
  2. Methodologischer Wert:
    • Der Induktionsrahmen könnte auf andere Probleme mit verbotenen Untergraphen anwendbar sein
    • Schlüssellemmata könnten in anderen Kontexten nützlich sein
  3. Nachfolgeforschung:
    • Wirft natürlich die Frage nach vollständiger Charakterisierung von Besengraphen auf
    • Motiviert die Untersuchung von exb,c-Werten für andere Baumfamilien
    • Könnte Forschung zum nicht-zusammenhängenden Fall inspirieren
  4. Verifizierbarkeit:
    • Als rein theoretisches Ergebnis kann es durch Überprüfung des Beweises verifiziert werden
    • Konstruktionen sind explizit und leicht verständlich
    • Formeln sind prägnant und leicht anwendbar und zitierbar

Anwendungsszenarien

  1. Theoretische Forschung:
    • Referenzergebnis für Forscher der extremalen Graphentheorie
    • Technische Quelle für Turán-Typ-Probleme
    • Fallstudie von Extremalproblemen unter Zusammenhängigkeitsbeschränkung
  2. Verwandte Probleme:
    • Könnte Forschung zur Erdős-Sós-Vermutung inspirieren
    • Bietet Vergleich für Turán-Zahlen anderer Bäume
    • Untersuchung von Struktureigenschaften zusammenhängender bipartiter Graphen
  3. Lehrwert:
    • Zeigt Anwendung von Induktion in extremaler Kombinatorik
    • Beispiel für DFS-Baum und Pfadanalyse
    • Vollständiges Beispiel für Matching von oberen und unteren Schranken

Referenzen (Schlüsselliteratur)

  1. CPT25 Caro, Patkós, Tuza: Bipartite Turán number of trees - Stellt die in diesem Papier gelösten Probleme
  2. Tur45 Turán: On an extremal problem in graph theory - Legt den Grundstein für Turán-Probleme
  3. ES46 Erdős, Stone: On the structure of linear graphs - Erdős-Stone-Theorem
  4. GRS84 Gyárfás, Rousseau, Schelp: An extremal problem for paths in bipartite graphs - Exakte Turán-Zahlen für Pfade in bipartiten Graphen (ohne Zusammenhängkeitsanforderung)
  5. HSZ25 He, Salia, Zhu: The connected bipartite Turán problem for long cycles and paths - Unabhängige verwandte Arbeit

Gesamtbewertung

Dies ist ein hochqualitatives Papier der Kombinatorik, das ein klar gestelltes offenes Problem vollständig löst und stärkere Ergebnisse als gefordert liefert. Die Beweistechniken sind elegant und innovativ, die Ergebnisse sind vollständig und präzise. Obwohl noch Arbeit bei der Verallgemeinerung auf allgemeine Bäume zu leisten ist, bietet das Papier im Fall von Pfaden eine definitive Antwort. Diese Arbeit leistet einen wesentlichen Beitrag zur Forschung des zusammenhängenden bipartiten Turán-Problems und wird voraussichtlich zu einer wichtigen Referenz in diesem Bereich.