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
제목: 한 공통 꼭짓점 또는 간선을 공유하는 무지개 삼각형
저자: Xiaozheng Chen (정주대학교), Bo Ning (난카이대학교)
분류: math.CO (조합론)
발표 시간: 2023년 2월 2일 (arXiv 사전인쇄본)
논문 링크: https://arxiv.org/abs/2302.00851

초록

본 논문은 간선 착색 그래프에서 무지개 삼각형의 존재성 문제를 연구한다. $n$ 개의 꼭짓점을 가진 간선 착색 그래프 $G$ 에서, 꼭짓점 $v$ 의 색도(color degree) $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$	-	새로운 결과