2025-11-10T03:03:05.603358

Rainbow triangles sharing one common vertex or edge

Chen, Ning
Let $G$ be an edge-colored graph on $n$ vertices. For a vertex $v$, the \emph{color degree} of $v$ in $G$, denoted by $d^c(v)$, is the number of colors appearing on the edges incident with $v$. Denote by $δ^c(G)=\min\{d^c(v):v\in V(G)\}$. By a theorem of H. Li, an $n$-vertex edge-colored graph $G$ contains a rainbow triangle if $δ^c(G)\geq \frac{n+1}{2}$. Inspired by this result, we consider two related questions concerning edge-colored books and friendship subgraphs of edge-colored graphs. Let $k\geq 2$ be a positive integer. We prove that if $δ^c(G)\geq \frac{n+k-1}{2}$ where $n\geq 3k-2$, then $G$ contains $k$ rainbow triangles sharing one common edge; and if $δ^c(G)\geq \frac{n+2k-3}{2}$ where $n\geq 2k+9$, then $G$ contains $k$ rainbow triangles sharing one common vertex. The special case $k=2$ of both results improves H. Li's theorem. The main novelty of our proof of the first result is a combination of the recent new technique for finding rainbow cycles due to Czygrinow, Molla, Nagle, and Oursler and some recent counting technique from \cite{LNSZ}. The proof of the second result is with the aid of the machine implicitly in the work of Turán numbers for matching numbers due to Erdős and Gallai.
academic

Regenbogendreiecke, die einen gemeinsamen Scheitelpunkt oder eine gemeinsame Kante teilen

Grundinformationen

  • Paper-ID: 2302.00851
  • Titel: Rainbow triangles sharing one common vertex or edge
  • Autoren: Xiaozheng Chen (Universität Zhengzhou), Bo Ning (Nankai-Universität)
  • Klassifizierung: math.CO (Kombinatorik)
  • Veröffentlichungsdatum: 2. Februar 2023 (arXiv-Preprint)
  • Paper-Link: https://arxiv.org/abs/2302.00851

Zusammenfassung

Diese Arbeit untersucht die Existenz von Regenbogendreiecken in kantengefärbten Graphen. Für einen kantengefärbten Graph GG mit nn Scheitelpunkten wird der Farbgrad dc(v)d^c(v) eines Scheitelpunkts vv als die Anzahl unterschiedlicher Farben definiert, die von den zu vv inzidenten Kanten verwendet werden. Der minimale Farbgrad wird als δc(G)=min⁡{dc(v):v∈V(G)}\delta^c(G)=\min\{d^c(v):v\in V(G)\} notiert. Ein Theorem von H. Li zeigt, dass GG ein Regenbogendreieck enthält, wenn δc(G)≥n+12\delta^c(G)\geq \frac{n+1}{2}. Inspiriert davon untersuchen die Autoren Buchgraph- (books) und Freundschaftsgraph- (friendship graphs) Strukturen in kantengefärbten Graphen. Die Hauptergebnisse zeigen: Wenn δc(G)≥n+k−12\delta^c(G)\geq \frac{n+k-1}{2} und n≥3k−2n\geq 3k-2, dann enthält GG kk Regenbogendreiecke, die eine gemeinsame Kante teilen; wenn δc(G)≥n+2k−32\delta^c(G)\geq \frac{n+2k-3}{2} und n≥2k+9n\geq 2k+9, dann enthält GG kk Regenbogendreiecke, die einen gemeinsamen Scheitelpunkt teilen.

Forschungshintergrund und Motivation

Problemhintergrund

  1. Klassisches Dreieck-Problem: Mantel (1907) bewies, dass ein dreiecksfreier Graph mit nn Scheitelpunkten höchstens ⌊n24⌋\lfloor\frac{n^2}{4}\rfloor Kanten hat
  2. Strukturierte Dreiecke: Erdős und andere untersuchten Turán-Zahlen für Buchgraphen BkB_k (kk Dreiecke, die eine gemeinsame Kante teilen) und Freundschaftsgraphen FkF_k (kk Dreiecke, die einen gemeinsamen Scheitelpunkt teilen)
  3. Regenbogenteilgraphen: Regenbogenteilgraphen und korrekt gefärbte Teilgraphen sind eng mit vielen graphentheoretischen Eigenschaften verbunden, wie klassischen Stabilitätsergebnissen, der Bermond-Thomassen-Vermutung und der Caccetta-Häggkvist-Vermutung

Forschungsmotivation

  1. Verallgemeinerung des H. Li-Theorems: H. Li (2013) bewies, dass die Bedingung des minimalen Farbgrads δc(G)≥n+12\delta^c(G)\geq \frac{n+1}{2} die Existenz eines Regenbogendreiecks garantiert
  2. Strukturierte Regenbogendreiecke: Natürliche Erweiterung auf mehrere Regenbogendreiecke, die Scheitelpunkte oder Kanten teilen
  3. Verbindung zur klassischen Graphentheorie: Verallgemeinerung der klassischen Konzepte von Buchgraphen und Freundschaftsgraphen auf kantengefärbte Graphen

Einschränkungen bestehender Methoden

Bisherige Forschungen zu Regenbogendreiecken konzentrieren sich hauptsächlich auf die Existenz einzelner Dreiecke; die Forschung zu strukturierten Anordnungen mehrerer Regenbogendreiecke (wie gemeinsame Scheitelpunkte oder Kanten) ist begrenzt.

Kernbeiträge

  1. Haupttheorem 3: Beweis, dass GG kk Regenbogendreiecke enthält, die eine gemeinsame Kante teilen (kantengefärbter Buchgraph BkB_k), wenn δc(G)≥n+k−12\delta^c(G)\geq \frac{n+k-1}{2} und n≥3k−2n\geq 3k-2
  2. Haupttheorem 4: Beweis, dass GG kk Regenbogendreiecke enthält, die einen gemeinsamen Scheitelpunkt teilen (kantengefärbter Freundschaftsgraph FkF_k), wenn δc(G)≥n+2k−32\delta^c(G)\geq \frac{n+2k-3}{2} und n≥2k+9n\geq 2k+9
  3. Verbesserung des H. Li-Theorems: Beide Hauptergebnisse verbessern das ursprüngliche Theorem von H. Li, wenn k=2k=2
  4. Technische Innovation: Kombination der Regenbogenzyklus-Techniken von Czygrinow und anderen mit neuesten Zähltechniken
  5. Extremalanalyse: Bereitstellung von Analysen der Straffheit der Ergebnisse und extremaler Konstruktionen

Methodische Details

Aufgabendefinition

Eingabe: Kantengefärbter Graph G=(V,E)G=(V,E) mit ∣V∣=n|V|=n und Kantenfärbungsfunktion C:E→{1,2,…,k}C:E\to \{1,2,\ldots,k\}Ausgabe: Bestimmung, ob GG kk Regenbogendreiecke enthält, die eine gemeinsame Kante (oder einen gemeinsamen Scheitelpunkt) teilen Nebenbedingungen: Der minimale Farbgrad δc(G)\delta^c(G) erfüllt bestimmte Schwellwerte

Kernkonzepte und Techniken

1. Farbgrad-bezogene Definitionen

  • Farbgrad: dc(v)=∣{C(uv):u∈N(v)}∣d^c(v) = |\{C(uv) : u \in N(v)\}|
  • α\alpha-Nachbarschaft: Nα(v)={u∈N(v):C(uv)=α}N_\alpha(v) = \{u \in N(v) : C(uv) = \alpha\}
  • Einfarbiger Grad: dmon(v)=max⁡{∣Nα(v)∣:α∈C(G)}d^{mon}(v) = \max\{|N_\alpha(v)| : \alpha \in C(G)\}

2. Eingeschränkte Farbtechnik

Einführung des Konzepts der "eingeschränkten Farbe" von Czygrinow und anderen:

  • Für einen Scheitelpunkt vv und X⊆N(v)X \subseteq N(v), wenn α=C(xy)\alpha = C(xy) so ist, dass vxyvxy einen Regenbogen-P3P_3 bildet und α∉C(y,N(y)∖X)\alpha \notin C(y, N(y)\setminus X), dann wird gesagt, dass (v,X)(v,X) die Farbe α\alpha für yy einschränkt
  • Notiere σv,X(y)\sigma_{v,X}(y) als die Anzahl der von (v,X)(v,X) eingeschränkten Farben

3. Regenbogendreieck-Zählung

  • rt(v)rt(v): Anzahl der Regenbogendreiecke, die den Scheitelpunkt vv enthalten
  • rt(v,x)rt(v,x): Anzahl der Regenbogendreiecke, die sowohl vv als auch xx enthalten
  • rt(v,X)=∑x∈Xrt(v,x)rt(v,X) = \sum_{x \in X} rt(v,x)

Schlüssellemmata

Lemma 7 (Zähllemma)

Für einen kantenminimalen Graph GG und einen Scheitelpunkt vv gilt: rt(v,Ni(v))≥∑x∈Ni(v)(dc(x)+dc(v)−n)+di(v)∑1≤j≤s(dj(v)−1)−di(v)(di(v)−1)−∑y∈N!(v)dvyc(y,Ni(v))rt(v,N_i(v)) \geq \sum_{x\in N_i(v)}(d^c(x) + d^c(v) - n) + d_i(v)\sum_{1\leq j\leq s}(d_j(v)-1) - d_i(v)(d_i(v)-1) - \sum_{y\in N^!(v)}d^c_{vy}(y,N_i(v))

wobei N!(v)=⋃α∈C(G){Nα(v):∣Nα(v)∣=1}N^!(v) = \bigcup_{\alpha\in C(G)}\{N_\alpha(v) : |N_\alpha(v)| = 1\}.

Lemma 9 (Einfarbige Gradanalyse)

Für einen Scheitelpunkt vv mit maximalem einfarbigem Grad gilt B(v)≥0B(v) \geq 0, und wenn B(v)=0B(v) = 0, dann existieren spezielle Struktureigenschaften.

Beweisstrategien

Beweisansatz für Theorem 3

  1. Annahme, dass keine kk Regenbogendreiecke existieren, die eine gemeinsame Kante teilen
  2. Auswahl eines Scheitelpunkts vv mit maximalem einfarbigem Grad
  3. Anwendung der Zählungleichung aus Lemma 7
  4. Beweis durch Widerspruch der Existenz einer erfüllenden Struktur

Beweisansatz für Theorem 4

  1. Anwendung der Turán-Theorie von Erdős-Gallai zur Matchingzahl
  2. Konstruktion eines Hilfsgraphen G△(v)G^\triangle(v) (bestehend aus Kanten von Regenbogendreiecken, die vv enthalten)
  3. Analyse der Überdeckungszahl und Matchingzahl von G△(v)G^\triangle(v)
  4. Ableitung eines Widerspruchs durch feinkörnige Gradanalyse

Experimentelle Einrichtung

Extremale Konstruktionen

Beispiel 1: Konstruktion eines ausgewogenen vollständigen 3-teiligen Graphen G[V1,V2,V3]G[V_1,V_2,V_3] mit ∣V(G)∣=3k−3|V(G)|=3k-3, ∣V1∣=∣V2∣=∣V3∣=k−1|V_1|=|V_2|=|V_3|=k-1, mit korrekter Färbung. Dieser Graph erfüllt dc(v)=n+k−12d^c(v) = \frac{n+k-1}{2}, enthält aber weder BkB_k noch FkF_k, was die Straffheit der Bedingung "n≥3k−2n \geq 3k-2" in Theorem 3 beweist.

Vergleichende Analyse

Das Papier vergleicht die Ergebnisse mit den folgenden klassischen Ergebnissen:

  • H. Li-Theorem: δc(G)≥n+12\delta^c(G) \geq \frac{n+1}{2} garantiert ein Regenbogendreieck
  • Erdős und andere Ergebnisse: Klassische Turán-Zahlen für Buchgraphen und Freundschaftsgraphen
  • Ungefärbter Graphenfall: Entsprechende minimale Gradbedingungen

Experimentelle Ergebnisse

Vergleich der Hauptergebnisse

StrukturBedingung in dieser ArbeitScheitelpunktanforderungH. Li-BedingungVerbesserung
B2B_2δc≥n+12\delta^c \geq \frac{n+1}{2}n≥4n \geq 4δc≥n+12\delta^c \geq \frac{n+1}{2}Konstruktive Verbesserung
F2F_2δc≥n+12\delta^c \geq \frac{n+1}{2}n≥13n \geq 13δc≥n+12\delta^c \geq \frac{n+1}{2}Konstruktive Verbesserung
BkB_kδc≥n+k−12\delta^c \geq \frac{n+k-1}{2}n≥3k−2n \geq 3k-2-Neues Ergebnis
FkF_kδc≥n+2k−32\delta^c \geq \frac{n+2k-3}{2}n≥2k+9n \geq 2k+9-Neues Ergebnis

Straffheitsanalyse

  • Straffheit von Theorem 3: Beispiel 1 zeigt, dass wenn n≤3k−3n \leq 3k-3, eine stärkere Farbgradbedingung δc≥n+k2\delta^c \geq \frac{n+k}{2} erforderlich ist
  • Asymptotische Straffheit: Wenn k=o(n)k = o(n), sind die Ergebnisse asymptotisch straff

Verwandte Arbeiten

Regenbogendreieck-Forschung

  1. H. Li (2013): Erstmals bewies, dass die Farbgradbedingung δc≥n+12\delta^c \geq \frac{n+1}{2} ein Regenbogendreieck garantiert
  2. B. Li und andere (2014): Bewies, dass die schwächere Bedingung ∑vdc(v)≥n(n+1)2\sum_{v} d^c(v) \geq \frac{n(n+1)}{2} auch ausreichend ist
  3. X. Li und andere (2022): Gab eine Zählversion für Regenbogendreiecke

Klassische Graphentheorie-Ergebnisse

  1. Mantel (1907): Obere Grenze für Kantenzahl dreiecksfreier Graphen
  2. Erdős-Edwards-Khadžiivanov-Nikiforov: Turán-Zahlen für Buchgraphen
  3. Erdős und andere (1995): Turán-Zahlen für Freundschaftsgraphen

Technische Methoden

  1. Czygrinow und andere (2021): Eingeschränkte Farbtechnik für Regenbogenzyklen
  2. Erdős-Gallai (1959): Turán-Theorie für Matchingzahlen

Schlussfolgerungen und Diskussion

Hauptschlussfolgerungen

  1. Erfolgreiche Verallgemeinerung des klassischen Ergebnisses von H. Li über Regenbogendreiecke auf Fälle mehrerer Dreiecke mit gemeinsamen Strukturen
  2. Etablierung hinreichender Bedingungen für die Existenz von Buchgraphen und Freundschaftsgraphen in kantengefärbten Graphen
  3. Bereitstellung von Straffheitsanalysen und extremalen Konstruktionen der Ergebnisse

Einschränkungen

  1. Scheitelpunktanforderungen: Die Bedingung n≥2k+9n \geq 2k+9 in Theorem 4 ist relativ stark
  2. Technische Komplexität: Der Beweis umfasst mehrere komplexe Zähltechniken und Strukturanalysen
  3. Verallgemeinerungsgrad: Die Ergebnisse konzentrieren sich hauptsächlich auf spezifische Teilungsmuster (einzelne Kante oder einzelner Scheitelpunkt)

Zukünftige Richtungen

  1. Allgemeinere Teilungsmuster: Untersuchung komplexerer Anordnungen von Regenbogendreiecken
  2. Andere Regenbogenstrukturen: Verallgemeinerung auf Regenbogenzyklen, Regenbogenpfade usw.
  3. Algorithmische Probleme: Entwurf effizienter Algorithmen zum Auffinden dieser Strukturen
  4. Zufallsgraphen: Entsprechende Ergebnisse in zufällig kantengefärbten Graphen

Tiefgreifende Bewertung

Stärken

  1. Signifikanter theoretischer Beitrag: Erfolgreiche Verallgemeinerung eines wichtigen klassischen Ergebnisses und Etablierung eines neuen theoretischen Rahmens
  2. Technische Innovation: Geschickte Kombination mehrerer moderner Techniken (eingeschränkte Farbe, Zählmethoden, Turán-Theorie)
  3. Vollständigkeit der Ergebnisse: Nicht nur Existenzergebnisse, sondern auch Analysen der Straffheit und extremaler Fälle
  4. Klare Darstellung: Angemessene Papierstruktur und klare Beweislogik

Schwächen

  1. Hohe Beweiskomplexität: Viele technische Details können die Zugänglichkeit der Ergebnisse beeinträchtigen
  2. Anwendungsbereich: Hauptsächlich theoretische Ergebnisse mit unklar definierten praktischen Anwendungsszenarien
  3. Konstante Faktoren: Einige Konstanten in den Bedingungen (wie 2k+92k+9) sind möglicherweise nicht optimal

Einfluss

  1. Theoretischer Wert: Bietet neue Forschungsrichtungen für Extremale Kombinatorik und Regenbogenteilgraph-Theorie
  2. Methodologischer Beitrag: Beweisteechniken könnten auf ähnliche Probleme anwendbar sein
  3. Nachfolgeforschung: Legt den Grundstein für weitere Forschung zu verwandten Problemen

Anwendungsszenarien

Diese Forschung ist hauptsächlich anwendbar auf:

  1. Theoretische Forschung in Extremaler Kombinatorik
  2. Graphenfärbungstheorie
  3. Existenzprobleme in struktureller Graphentheorie
  4. Teilstruktur-Erkennungsprobleme in kombinatorischer Optimierung

Literaturverzeichnis

Das Papier zitiert 29 wichtige Referenzen, einschließlich:

  • H. Li (2013): Rainbow C3C_3's and C4C_4's in edge-colored graphs
  • Erdős, Füredi, Gould, Gunderson (1995): Extremal graphs for intersecting triangles
  • Czygrinow, Molla, Nagle, Oursler (2021): On odd rainbow cycles in edge-colored graphs
  • Sowie viele weitere klassische Werke in Kombinatorik und Graphentheorie