Rainbow triangles sharing one common vertex or edge

Basic Information

• Paper ID: 2302.00851
• Title: Rainbow triangles sharing one common vertex or edge
• Authors: Xiaozheng Chen (Zhengzhou University), Bo Ning (Nankai University)
• Classification: math.CO (Combinatorics)
• Publication Date: February 2, 2023 (arXiv preprint)
• Paper Link: https://arxiv.org/abs/2302.00851

Abstract

This paper investigates the existence of rainbow triangles in edge-colored graphs. For an edge-colored graph $G$ on $n$ vertices, the color degree $d^c(v)$ of a vertex $v$ is defined as the number of distinct colors on edges incident to $v$. The minimum color degree is denoted $\delta^c(G)=\min\{d^c(v):v\in V(G)\}$. A theorem by H. Li states that when $\delta^c(G)\geq \frac{n+1}{2}$, the graph $G$ contains a rainbow triangle. Motivated by this result, the authors investigate book graphs (books) and friendship graphs structures in edge-colored graphs. The main results prove that: when $\delta^c(G)\geq \frac{n+k-1}{2}$ and $n\geq 3k-2$, $G$ contains $k$ rainbow triangles sharing one common edge; when $\delta^c(G)\geq \frac{n+2k-3}{2}$ and $n\geq 2k+9$, $G$ contains $k$ rainbow triangles sharing one common vertex.

Research Background and Motivation

Problem Background

1. Classical Triangle Problem: Mantel (1907) proved that a triangle-free graph on $n$ vertices has at most $\lfloor\frac{n^2}{4}\rfloor$ edges
2. Structured Triangles: Erdős and others studied the Turán numbers for book graphs $B_k$ ($k$ triangles sharing one edge) and friendship graphs $F_k$ ($k$ triangles sharing one vertex)
3. Rainbow Subgraphs: Rainbow subgraphs and properly colored subgraphs are closely related to many graph-theoretic properties, such as classical stability results, the Bermond-Thomassen conjecture, and the Caccetta-Häggkvist conjecture

Research Motivation

1. Generalization of H. Li's Theorem: H. Li (2013) proved that the minimum color degree condition $\delta^c(G)\geq \frac{n+1}{2}$ guarantees the existence of a rainbow triangle
2. Structured Rainbow Triangles: It is natural to consider cases where multiple rainbow triangles share vertices or edges
3. Connection with Classical Graph Theory: Extending the classical concepts of book graphs and friendship graphs to the edge-colored graph setting

Limitations of Existing Methods

Existing research on rainbow triangles primarily focuses on the existence of single triangles, with relatively limited investigation into structured arrangements of multiple rainbow triangles (such as sharing vertices or edges).

Core Contributions

1. Main Theorem 3: Proves that when $\delta^c(G)\geq \frac{n+k-1}{2}$ and $n\geq 3k-2$, the graph $G$ contains $k$ rainbow triangles sharing one common edge (edge-colored book graph $B_k$)
2. Main Theorem 4: Proves that when $\delta^c(G)\geq \frac{n+2k-3}{2}$ and $n\geq 2k+9$, the graph $G$ contains $k$ rainbow triangles sharing one common vertex (edge-colored friendship graph $F_k$)
3. Improvement of H. Li's Theorem: When $k=2$, both main results improve H. Li's original theorem
4. Technical Innovation: Combines the rainbow cycle techniques of Czygrinow et al. with recent counting methods
5. Extremal Analysis: Provides analysis of result tightness and extremal constructions

Methodology Details

Task Definition

Input: Edge-colored graph $G=(V,E)$, where $|V|=n$, edge coloring function $C:E\to \{1,2,\ldots,k\}$Output: Determine whether $G$ contains $k$ rainbow triangles sharing one common edge (or one common vertex) Constraints: Minimum color degree $\delta^c(G)$ satisfies specific thresholds

Core Concepts and Techniques

1. Color Degree Related Definitions

• Color degree: $d^c(v) = |\{C(uv) : u \in N(v)\}|$
• $\alpha$-neighborhood: $N_\alpha(v) = \{u \in N(v) : C(uv) = \alpha\}$
• Monochromatic degree: $d^{mon}(v) = \max\{|N_\alpha(v)| : \alpha \in C(G)\}$

2. Restricted Color Technique

Introduces the "restricted color" concept from Czygrinow et al.:

• For vertex $v$ and $X \subseteq N(v)$, if $\alpha = C(xy)$ such that $vxy$ forms a rainbow $P_3$ and $\alpha \notin C(y, N(y)\setminus X)$, then $(v,X)$ restricts color $\alpha$ for $y$
• Denote $\sigma_{v,X}(y)$ as the number of colors restricted by $(v,X)$

3. Rainbow Triangle Counting

• $rt(v)$: Number of rainbow triangles containing vertex $v$
• $rt(v,x)$: Number of rainbow triangles containing both vertices $v$ and $x$
• $rt(v,X) = \sum_{x \in X} rt(v,x)$

Key Lemmas

Lemma 7 (Counting Lemma)

For an edge-minimal graph $G$ and vertex $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))$

where $N^!(v) = \bigcup_{\alpha\in C(G)}\{N_\alpha(v) : |N_\alpha(v)| = 1\}$.

Lemma 9 (Monochromatic Degree Analysis)

For a vertex $v$ with maximum monochromatic degree, $B(v) \geq 0$, and special structural properties exist when $B(v) = 0$.

Proof Strategy

Proof Strategy for Theorem 3

1. Assume no $k$ rainbow triangles sharing one edge exist
2. Select a vertex $v$ with maximum monochromatic degree
3. Apply the counting inequality from Lemma 7
4. Derive a contradiction to prove the existence of the desired structure

Proof Strategy for Theorem 4

1. Utilize Erdős-Gallai theory on Turán numbers for matchings
2. Construct auxiliary graph $G^\triangle(v)$ (formed by edges of rainbow triangles containing $v$)
3. Analyze the covering number and matching number of $G^\triangle(v)$
4. Derive contradiction through refined degree analysis

Experimental Setup

Extremal Constructions

Example 1: Construct balanced complete 3-partite graph $G[V_1,V_2,V_3]$, where $|V(G)|=3k-3$, $|V_1|=|V_2|=|V_3|=k-1$, with proper coloring. This graph satisfies $d^c(v) = \frac{n+k-1}{2}$ but contains neither $B_k$ nor $F_k$, proving the tightness of the condition "$n \geq 3k-2$" in Theorem 3.

Comparative Analysis

The paper compares results with the following classical results:

• H. Li's Theorem: $\delta^c(G) \geq \frac{n+1}{2}$ guarantees rainbow triangles
• Erdős et al. Results: Classical Turán numbers for book graphs and friendship graphs
• Uncolored Graph Case: Corresponding minimum degree conditions

Experimental Results

Main Results Comparison

Tightness Analysis

• Tightness of Theorem 3: Example 1 shows that when $n \leq 3k-3$, a stronger color degree condition $\delta^c \geq \frac{n+k}{2}$ is required
• Asymptotic Tightness: When $k = o(n)$, the results are asymptotically tight

Related Work

Rainbow Triangle Research

1. H. Li (2013): First proved that the color degree condition $\delta^c \geq \frac{n+1}{2}$ guarantees rainbow triangles
2. B. Li et al. (2014): Proved that the weaker condition $\sum_{v} d^c(v) \geq \frac{n(n+1)}{2}$ is also sufficient
3. X. Li et al. (2022): Provided counting versions of rainbow triangles

Classical Graph Theory Results

1. Mantel (1907): Upper bound on edges in triangle-free graphs
2. Erdős-Edwards-Khadžiivanov-Nikiforov: Turán numbers for book graphs
3. Erdős et al. (1995): Turán numbers for friendship graphs

Technical Methods

1. Czygrinow et al. (2021): Restricted color technique for rainbow cycles
2. Erdős-Gallai (1959): Turán theory for matching numbers

Conclusions and Discussion

Main Conclusions

1. Successfully generalizes H. Li's classical result on rainbow triangles to cases where multiple triangles share structural properties
2. Establishes sufficient conditions for the existence of book graphs and friendship graphs in edge-colored graphs
3. Provides tightness analysis and extremal constructions for the results

Limitations

1. Vertex Number Requirements: The condition $n \geq 2k+9$ in Theorem 4 is relatively strong
2. Technical Complexity: The proofs involve multiple complex counting techniques and structural analyses
3. Generalization Degree: Results primarily address specific sharing patterns (single edge or single vertex)

Future Directions

1. More General Sharing Patterns: Investigate more complex arrangements of rainbow triangles
2. Other Rainbow Structures: Extend to rainbow cycles, rainbow paths, etc.
3. Algorithmic Problems: Design efficient algorithms for finding these structures
4. Random Graphs: Corresponding results in randomly edge-colored graphs

In-Depth Evaluation

Strengths

1. Significant Theoretical Contribution: Successfully generalizes important classical results and establishes a new theoretical framework
2. Technical Innovation: Cleverly combines multiple modern techniques (restricted colors, counting methods, Turán theory)
3. Result Completeness: Provides not only existence results but also analyzes tightness and extremal cases
4. Clear Presentation: Well-structured paper with clear proof strategies

Weaknesses

1. High Proof Complexity: Abundant technical details may affect accessibility of the results
2. Limited Application Scope: Primarily theoretical results with unclear practical applications
3. Constant Factors: Some constants in conditions (such as $2k+9$) may not be optimal

Impact

1. Theoretical Value: Provides new research directions for extremal combinatorics and rainbow subgraph theory
2. Methodological Contribution: Proof techniques may apply to other similar problems
3. Foundation for Future Research: Establishes basis for further investigation of related problems

Applicable Scenarios

This research primarily applies to:

1. Theoretical research in extremal combinatorics
2. Graph coloring theory
3. Existence problems in structural graph theory
4. Substructure detection in combinatorial optimization

References

The paper cites 29 important references, including:

• H. Li (2013): Rainbow $C_3$'s and $C_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
• Multiple classical works in combinatorics and graph theory