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

一つの共通頂点または辺を共有する虹色三角形

基本情報

論文ID: 2302.00851
タイトル: Rainbow triangles sharing one common vertex or edge（一つの共通頂点または辺を共有する虹色三角形）
著者: Xiaozheng Chen（鄭州大学）、Bo Ning（南開大学）
分類: math.CO（組合数学）
発表日: 2023年2月2日（arXiv プレプリント）
論文リンク: https://arxiv.org/abs/2302.00851

要旨

本論文は、辺着色グラフにおける虹色三角形の存在性問題を研究している。 $n$ 個の頂点を持つ辺着色グラフ $G$ に対して、頂点 $v$ の色度 $d^c(v)$ は、 $v$ に隣接する辺に使用される異なる色の数として定義される。最小色度は $\delta^c(G)=\min\{d^c(v):v\in V(G)\}$ と記される。H. Li定理は、 $\delta^c(G)\geq \frac{n+1}{2}$ のとき、グラフ $G$ は虹色三角形を含むことを示している。これに触発されて、著者は辺着色グラフにおける書グラフ（books）と友情グラフ（friendship graphs）の構造を研究した。主要な結果は以下を証明している： $\delta^c(G)\geq \frac{n+k-1}{2}$ かつ $n\geq 3k-2$ のとき、 $G$ は一つの辺を共有する $k$ 個の虹色三角形を含む； $\delta^c(G)\geq \frac{n+2k-3}{2}$ かつ $n\geq 2k+9$ のとき、 $G$ は一つの頂点を共有する $k$ 個の虹色三角形を含む。

研究背景と動機

問題背景

古典的三角形問題：Mantel（1907）は $n$ 個の頂点を持つ三角形を含まないグラフは最大で $\lfloor\frac{n^2}{4}\rfloor$ 本の辺を持つことを証明した
構造化された三角形：Erdősらは書グラフ $B_k$ （一つの辺を共有する $k$ 個の三角形）と友情グラフ $F_k$ （一つの頂点を共有する $k$ 個の三角形）のTurán数を研究した
虹色部分グラフ：虹色部分グラフと正しく着色された部分グラフは、古典的安定性結果、Bermond-Thomassen予想、Caccetta-Häggkvist予想など、多くのグラフ理論的性質と密接に関連している

研究の動機

H. Li定理の一般化：H. Li（2013）は最小色度条件 $\delta^c(G)\geq \frac{n+1}{2}$ が虹色三角形の存在を保証することを証明した
構造化された虹色三角形：複数の虹色三角形が頂点または辺を共有する場合を自然に考察する
古典的グラフ論との関連：古典的な書グラフと友情グラフの概念を辺着色グラフの設定に一般化する

既存方法の限界

虹色三角形に関する既存の研究は主に単一の三角形の存在性に焦点を当てており、複数の虹色三角形の構造化された配置（頂点または辺を共有する場合など）の研究は比較的少ない。

核心的貢献

主定理3： $\delta^c(G)\geq \frac{n+k-1}{2}$ かつ $n\geq 3k-2$ のとき、グラフ $G$ は一つの辺を共有する $k$ 個の虹色三角形（辺着色書グラフ $B_k$ ）を含むことを証明した
主定理4： $\delta^c(G)\geq \frac{n+2k-3}{2}$ かつ $n\geq 2k+9$ のとき、グラフ $G$ は一つの頂点を共有する $k$ 個の虹色三角形（辺着色友情グラフ $F_k$ ）を含むことを証明した
H. Li定理の改善： $k=2$ のとき、両方の主要な結果はH. Liの元の定理を改善している
技術的革新：Czygrinowらの虹色圏技術と最新の計数技術を組み合わせた
極値性分析：結果の緊密性の分析と極値構成を提供した

方法の詳細説明

タスク定義

入力：辺着色グラフ $G=(V,E)$ 、ここで $|V|=n$ 、辺着色関数 $C:E\to \{1,2,\ldots,k\}$ 出力： $G$ が一つの辺（または一つの頂点）を共有する $k$ 個の虹色三角形を含むかどうかを判定する 制約条件：最小色度 $\delta^c(G)$ が特定の閾値を満たす

核心的概念と技術

1. 色度関連の定義

色度： $d^c(v) = |\{C(uv) : u \in N(v)\}|$
$\alpha$ -近傍： $N_\alpha(v) = \{u \in N(v) : C(uv) = \alpha\}$
単色度： $d^{mon}(v) = \max\{|N_\alpha(v)| : \alpha \in C(G)\}$

2. 制限色技術

Czygrinowらの「制限色」概念を導入する：

頂点 $v$ と $X \subseteq N(v)$ に対して、 $\alpha = C(xy)$ が $vxy$ が虹色 $P_3$ を構成し、かつ $\alpha \notin C(y, N(y)\setminus X)$ を満たす場合、 $(v,X)$ は $y$ に対して色 $\alpha$ を制限すると言う
$\sigma_{v,X}(y)$ を $(v,X)$ によって制限される色の数とする

3. 虹色三角形の計数

$rt(v)$ ：頂点 $v$ を含む虹色三角形の数
$rt(v,x)$ ：頂点 $v$ と $x$ の両方を含む虹色三角形の数
$rt(v,X) = \sum_{x \in X} rt(v,x)$

主要補題

補題7（計数補題）

辺最小グラフ $G$ と頂点 $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))$

ここで $N^!(v) = \bigcup_{\alpha\in C(G)}\{N_\alpha(v) : |N_\alpha(v)| = 1\}$ である。

補題9（単色度分析）

最大単色度を持つ頂点 $v$ に対して、 $B(v) \geq 0$ が成立し、 $B(v) = 0$ のとき特殊な構造的性質が存在する。

証明戦略

定理3の証明思路

$k$ 個の共有辺を持つ虹色三角形が存在しないと仮定する
最大単色度を持つ頂点 $v$ を選択する
補題7の計数不等式を利用する
矛盾を通じて条件を満たす構造の存在を証明する

定理4の証明思路

マッチング数に関するErdős-Gallaiの Turán数理論を利用する
補助グラフ $G^\triangle(v)$ （ $v$ を含む虹色三角形の辺から構成）を構成する
$G^\triangle(v)$ の被覆数とマッチング数を分析する
精密な次数分析を通じて矛盾を導く

H. Li定理： $\delta^c(G) \geq \frac{n+1}{2}$ は虹色三角形を保証する
Erdősらの結果：書グラフと友情グラフの古典的Turán数
無色グラフの場合：対応する最小次数条件

実験結果

主要結果の比較

構造	本論文の条件	頂点数要件	H. Li条件	改善
$B_2$	$\delta^c \geq \frac{n+1}{2}$	$n \geq 4$	$\delta^c \geq \frac{n+1}{2}$	構成的改善
$F_2$	$\delta^c \geq \frac{n+1}{2}$	$n \geq 13$	$\delta^c \geq \frac{n+1}{2}$	構成的改善
$B_k$	$\delta^c \geq \frac{n+k-1}{2}$	$n \geq 3k-2$	-	新結果
$F_k$	$\delta^c \geq \frac{n+2k-3}{2}$	$n \geq 2k+9$	-	新結果

緊密性分析

定理3の緊密性：例1は $n \leq 3k-3$ のとき、より強い色度条件 $\delta^c \geq \frac{n+k}{2}$ が必要であることを示している
漸近的緊密性： $k = o(n)$ のとき、結果は漸近的に緊密である

結論と考察

主要な結論

H. Liの虹色三角形に関する古典的結果を、複数の三角形が構造を共有する場合に成功裏に一般化した
辺着色グラフにおける書グラフと友情グラフの存在性に対する十分条件を確立した
結果の緊密性分析と極値構成を提供した

限界

頂点数要件：定理4の条件 $n \geq 2k+9$ は比較的強い
技術的複雑性：証明は複数の複雑な計数技術と構造分析を含む
一般化の程度：結果は主に特定の共有パターン（単一辺または単一頂点）に対するもの

将来の方向

より一般的な共有パターン：より複雑な虹色三角形の配置を研究する
他の虹色構造：虹色圏、虹色経路などへの一般化
アルゴリズム問題：これらの構造を見つけるための効率的なアルゴリズムの設計
ランダムグラフ：ランダムな辺着色グラフにおける対応する結果

深い評価

利点

理論的貢献が顕著：重要な古典的結果の成功した一般化、新しい理論的枠組みの確立
技術的革新：複数の現代的技術（制限色、計数方法、Turán理論）の巧妙な組み合わせ
結果の完全性：存在性結果だけでなく、緊密性と極値の場合の分析も提供
明確な記述：論文の構成が合理的で、証明の思路が明確

不足

証明の複雑性が高い：技術的詳細が多く、結果のアクセス可能性に影響する可能性がある
応用範囲：主に理論的結果であり、実際の応用シナリオが十分に明確でない
定数因子：条件内の定数（例えば $2k+9$ ）が最適でない可能性がある

影響力

理論的価値：極値組合論と虹色部分グラフ理論に新しい研究方向を提供する
方法論的貢献：証明技術は他の類似問題に適用される可能性がある
後続研究：関連問題のさらなる研究の基礎を確立する

適用シナリオ

本研究は主に以下に適用される：

極値組合論の理論研究
グラフ着色理論
構造グラフ論における存在性問題
組合最適化における部分構造検出問題

参考文献

論文は29篇の重要な文献を引用しており、以下を含む：

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
組合数学とグラフ論分野の多くの古典的文献