Acyclic Dichromatic Number of Tournaments: these are the Champions

기술 요약: 토너먼트의 비순환 이색수 (Acyclic Dichromatic Number)

문제 정의
본 논문은 방향 그래프, 특히 토너먼트의 맥락에서 비순환 이색수($\vec{\chi}_a$)를 조사한다. 비순환 $k$-이색(acyclic $k$-dicolouring)이란 정점 분할을 통해 각 부분에 의해 유도된 부분 방향 그래프가 비순환이고, 임의의 두 부분 사이의 방향 이분 그래프 또한 비순환인 정점 분할을 의미한다. 비순환 이색수는 이러한 분할에 필요한 최소 $k$값이다.

저자들은 Bang-Jensen, Picasarri-Arrieta, Yeo [4]가 제기한 두 가지 구체적인 추측을 다룬다:

1. 챔피언의 특징 규명 (Characterization of Champions): 모든 $H$-free 토너먼트가 유계된 비순환 이색수를 갖는다는 의미에서, 어떤 토너먼트 $H$가 "챔피언"(표준 이색수 이론에서의 "히어로"와 유사함)인지 식별하는 것.
2. 국소-전역 성질 (Local-to-Global Property): 토너먼트의 비순환 이색수가 각 정점의 외이웃(out-neighborhood)의 최대 비순환 이색수에 의해 결정되는 함수로 유계되는지 여부를 결정하는 것.

방법론
본 논문은 구조적 그래프 이론과 Ramsey 유형의 논증을 사용하여 비순환 이색수의 경계값을 설정한다.

• 디매칭 (Dimatchings): 핵심 도구로 도입된 디매칭은 서로 짝이 맞지 않는 호(arc)들의 집합 $\{a_1b_1, \dots, a_kb_k\}$로, $i=j$이면 $a_i \to b_j$이고 $i \neq j$이면 $a_i \leftarrow b_j$인 형태를 띤다. 저자들은 큰 디매칭의 존재가 높은 비순환 이색수를 함의한다는 Bang-Jensen 등의 결과 [4]를 활용한다.
• Ramsey 이론: 증명에는 큰 토너먼트 내에서 전이적(transitive) 부분 토너먼트의 존재성을 다루는 Erdős-Moser 정리 [8]를 사용하여, 특정 구조적 구성(구체적으로 $TT_k \Rightarrow (\Delta(1, 1, k) \Rightarrow TT_k)$ 토너먼트)을 찾아낸다.
• 이분 그래프로의 환원: 높은 비순환 이색수를 가진 토너먼트에서 큰 디매칭의 존재를 증명하기 위해, 저자들은 문제를 이분 그래프의 성질로 환원한다. 저자들은 유도 매칭(induced matchings) 및 공매칭(co-matchings)에 관한 Atminas [2]의 결과를 활용한다. 구체적으로, 이들은 기저가 되는 무방향 이분 그래프에서 유도된 $2K_2$(크기가 2인 유도 매칭)의 부재와 이분 토너먼트의 비순환 이색수 사이의 관계를 이용한다.
• 재귀적 분할: 증명 과정에는 토너먼트를 전이적 집합들로 분해하고, 유도된 부분 방향 그래프에 기초하여 비순환 이색수를 제한하는 Lemma 9로부터 도출된 결론들을 사용하여 이들 사이의 상호작용을 분석하는 과정이 포함된다.

주요 기여 및 결과

1. 챔피언 추측의 확인 (정리 3):
   저자들은 토너먼트 $H$가 챔피언일 필요충분조건이 어떤 정수 $k \ge 1$에 대하여 $TT_k \Rightarrow (\Delta(1, 1, k) \Rightarrow TT_k)$의 부분 토너먼트와 동형인 것이다.

   • 메커니즘: 저자들은 충분히 큰 디매칭을 가진 모든 토너먼트가 $TT_k \Rightarrow (\Delta(1, 1, k) \Rightarrow TT_k)$와 동형인 부분 토너먼트를 포함함을 입증한다. 큰 디매칭은 높은 비순환 이색수를 강제하므로, 이 특정 구조를 피하는 모든 토너먼트는 유계된 비순환 이색수를 갖게 된다.

2. 디매칭의 존재성 (정리 4):
   본 논문은 비순환 이색수가 적어도 $f(k)$인 모든 토너먼트가 크기 $k$의 디매칭을 포함하도록 하는 함수 $f: \mathbb{N} \to \mathbb{N}$를 설정한다.

   • 메커니즘: 이 결과는 이분 그래프에 관한 Atminas의 정리 [2]에 의존한다. 큰 디매칭이 없는 토너먼트의 구조는 특정한 이분 상호작용을 가진 유계된 수의 전이적 집합들로 분할될 수 있음을 보임으로써, 저자들은 비순환 이색수를 제한한다.

3. 국소-전역 성질의 확인 (정리 5):
   저자들은 임의의 토너먼트 $T$에 대하여 $\vec{\chi}_a(T) \le \max_{v \in V(T)} g(\vec{\chi}_a(v^+))$를 만족하는 함수 $g: \mathbb{N} \to \mathbb{N}$의 존재성을 증명한다.

   • 메커니즘: 이는 정리 4의 결과로부터 도출된다. 만약 어떤 토너먼트가 큰 비순환 이색수를 가진다면, 그것은 큰 디매칭을 포함한다. 이 디매칭의 구조는 특정 정점들의 외이웃이 큰 디매칭을 포함하도록 보장하며, 이는 국소적 이웃에서 높은 비순환 이색수를 강제한다.

의의 및 주장
본 논문은 Bang-Jensen, Picasarri-Arrieta, Yeo [4]의 두 가지 추측을 확인하여, 비순환 이색수에 대한 "챔피언"의 특징 규명을 완료하고 국소-전역 성질을 확립하였다.

저자들은 챔피언의 특징 규명에서 (챔피언은 반드시 해당 형태를 가져야 한다는) 순방향 함의는 이미 알려져 있었으나, 그 역(해당 형태의 토너먼트가 실제로 챔피언이라는 것)이 본 연구의 새로운 기여임을 명시한다. 또한, 저자들은 부록에서 정리 4나 Atminas의 결과에 의존하지 않는 정리 3의 대안적 증명을 제공하며, 이것이 더 나은 상한(upper bounds)을 제공하고 향후 연구에 독립적인 관심사가 될 수 있다고 제언한다.

이 연구는 잘 알려진 이색수(여기서 "히어로"는 특정 재귀적 구조로 특징지어짐)와 더 엄격한 제약을 받는 비순환 이색수 사이의 간극을 메우며, 구조는 다르더라도 토너먼트에서 유계성과 국소성의 근본적인 성질이 두 파라미터 모두에서 유지됨을 보여준다.