The Zarankiewicz problem on tripartite graphs

이 논문은 밀도 증가 논법을 활용하고 최적의 경계를 입증하기 위해 극단적 그래프 군(family of extremal graphs)을 구성함으로써, $n \times n \times n$ 삼분 그래프가 $K_{t,t,t}$ 부분 그래프를 포함하는 데 필요한 최소 차수 임계값 $\tau$가 $\mathcal{O}(n^{1-1/t})$임을 증명하여 볼로바스(Bollobás), 에르되시(Erdős), 세메레디(Szemerédi)의 1975년 추측을 해결한다.

핵심

당신이 거대한 삼각 교차로를 설계하는 도시 계획가라고 상상해 보십시오. 당신에게는 세 개의 뚜렷한 이웃 동네(이름을 북쪽, 동쪽, 남쪽이라고 합시다)가 있고, 각 동네에는 정확히 $n$개의 집이 있습니다.

이 도시에서 도로는 서로 다른 동네 사이에만 놓일 수 있습니다. 북쪽의 집에서 북쪽의 다른 집으로 가는 도로는 건설할 수 없습니다. 이 논문의 목표는 매우 구체적인 질문에 답하는 것입니다: 특정한 "슈퍼 구조(super-structure)"가 나타나도록 강제하기 위해 우리는 얼마나 많은 추가 도로를 건설해야 하는가?

"슈퍼 구조": $K_{t,t,t}$

수학적으로 이 구조는 $K_{t,t,t}$라고 불립니다. 우리 도시의 비유를 빌리자면, 북쪽에서 $t$개, 동쪽에서 $t$개, 남쪽에서 $t$개의 집을 선택하는 것을 상상해 보십시오. 만약 당신이 선택한 북쪽 그룹의 모든 집이 동쪽 그룹의 모든 집과 연결되어 있고, 또한 남쪽 그룹의 모든 집과도 연결되어 있으며, 동시에 동쪽과 남쪽 그룹 사이도 완전히 연결되어 있다면, 당신은 $K_{t,t,t}$를 구축한 것입니다.

이는 마치 $3t$개의 집이 완벽하게 상호 연결된 그물망과 같습니다.

문제: 도시가 얼마나 "분주"해야 하는가?

저자들은 도시의 **최소 차수(minimum degree)**를 살펴보고 있습니다. 이는 다음과 같은 의미입니다: "도시의 어떤 단일 가구라도 가질 수 있는 최소한의 도로 수는 얼마인가?"

• 만약 모든 집이 정확히 $n$개의 도로를 가지고 있다면, 슈퍼 구조를 완전히 회피하도록 도시를 배치할 수 있습니다. (예를 들어, 북쪽은 동쪽과 연결되고 북쪽은 남쪽과 연결되지만, 동쪽과 남쪽은 서로 대화하지 않는 도시를 생각해보십시오. 삼각형이나 슈퍼 구조가 없는 상태입니다.)
• 질문은 이것입니다: 만약 모든 집에 약간의 추가 도로(이를 $\tau$라고 부릅시다)를 더한다면, 어느 시점에서 슈퍼 구조가 불가피하게 나타나게 될까요?

오랫동안 수학자들은 가장 작은 슈퍼 구조($t=2$)의 경우, 약 $\sqrt{n}$만큼의 추가 도로가 필요할 것이라고 추측해 왔습니다. 하지만 아무도 이를 증명하지 못했습니다.

해결책: "밀도 부스트(Density Boost)"

저자인 프란체스코 디 브라치오(Francesco Di Braccio)와 프레디 일링워스(Freddie Illingworth)는 정답이 실제로 대략 $\sqrt{n}$ (구체적으로는 $n^{1-1/t}$)임을 증명했습니다.

그들은 다음과 같이 이 문제를 해결했습니다:

1. "부스터(Booster)" 도로
저자들은 **"부스터"**라는 개념을 발명했습니다. 북쪽의 집과 동쪽의 집 사이에 있는 도로를 상상해 보십시오. 만약 동쪽의 집이 북쪽의 집보다 더 인기 있다면(즉, 도로가 더 많다면), 그 도로는 "부스터"입니다.

• 중요한 이유: 부스터는 자석처럼 작용하기 때문에 특별합니다. 만약 북쪽에서 동쪽으로 가는 도로가 있고, 그 동쪽의 집이 매우 인기가 높다면, 남쪽 동네 또한 두 집 모두와 연결될 가능성이 매우 높습니다. 이는 슈퍼 구조에 필요한 "삼각형"을 만들어냅니다.

2. 두 가지 시나리오
저자들은 도시를 보고 이렇게 말했습니다: "자, 만약 우리가 충분한 추가 도로를 가지고 있다면, 다음 두 가지 중 하나가 반드시 일어나야 합니다."

• 시나리오 A: 조밀한 웹(Dense Web). 도시의 특정 구역에서 "부스터" 도로가 너무 빽빽하고 풍부하여 조밀한 웹을 형성하는 경우입니다. 만약 부스터의 웹이 조밀하다면, 수학적 원리에 의해 슈퍼 구조가 즉시 나타나게 됩니다.
• 시나리오 B: 헤비 히터(Heavy Hitters). 만약 웹이 조밀하지 않다면, "헤비 히터"라고 불리는 집들의 집단이 존재해야 합니다. 이 집들은 자신들도 매우 잘 연결되어 있는 다른 집들과 많은 연결을 가지고 있습니다. 설령 웹이 조밀하지 않더라도, 이 헤비 히터들은 충분한 압력을 만들어내어 결국 슈퍼 구조가 툭 하고 튀어나오게 만듭니다.

3. "밀도 증가(Density Increment)" 기법
이 증명의 핵심은 밀도 증가 전략입니다.
지저분한 방에서 특정 패턴을 찾으려고 노력한다고 상상해 보십시오.

1. 먼저, 나머지 부분보다 약간 더 지저분한(밀도가 높은) 방의 작은 구석을 찾습니다.
2. 그 구석으로 줌인(zoom in)합니다.
3. 그 구석 내부에서 훨씬 더 지저분한 구석을 다시 찾습니다.
4. 이 과정을 반복합니다.
   결국, 무질서함이 너무 집중되면 당신이 찾고 있는 패턴(슈퍼 구조)을 놓치는 것이 불가능해집니다. 저자들은 이 논리를 사용하여, 만약 아직 슈퍼 구조가 없다면, 항상 더 "조밀한" 부분을 찾아낼 수 있으며, 결국 구조가 존재함을 인정할 수밖에 없음을 보여주었습니다.

"멀리 떨어진" 극단들

이 논문은 또한 멋진 작업도 수행했습니다: "최악의 경우"에 해당하는 도시들의 가족(family)을 구축한 것입니다.
이 도시들은 슈퍼 구조를 피할 수 있을 만큼의 딱 적당한 도로를 가지고 있지만, 서로 매우 다릅니다.

• 도시 A와 도시 B를 상상해 보십시오. 둘 다 슈퍼 구조를 피합니다.
• 도시 A를 도시 B로 바꾸려면, 엄청난 수의 도로(약 $n^2$개의 도로)를 철거하고 다시 건설해야 합니다.
• 이는 슈퍼 구조를 피하는 방법이 단 한 가지의 "이상한" 방식만 있는 것이 아니라, 매우 다양하고 서로 확연히 구분되는 수많은 방식이 존재한다는 것을 증명합니다. 이는 이전 연구자들이 구조를 피하는 방법이 몇 가지뿐일 것이라고 생각했던 점에 대한 놀라운 발견이었습니다.

결론

이 논문은 50년 된 추측을 확인해 줍니다: 세 개의 이웃 동네가 있는 도시에서 완벽하게 상호 연결된 $3t$개의 집의 웹을 강제하려면, 각 집마다 대략 $n^{1-1/t}$만큼의 추가 도로를 더해야 합니다. 만약 그만큼의 도로를 추가한다면, 도로를 어떻게 배치하든 상관없이 그 구조는 반드시 나타납니다. 만약 그보다 적게 추가한다면, 슈퍼 구조를 피하는 도시를 건설할 수 있습니다.

또한, 저자들은 구조를 피하는 데 성공하는 "도시들"이 믿기 힘들 정도로 다양하며 서로 멀리 떨어져 있다는 것을 보여줌으로써, 이 문제가 이전에 생각했던 것보다 훨씬 더 풍부한 문제임을 입증했습니다.

기술 요약

기술 요약: 삼분 그래프에서의 자란츠키에비치 문제 (The Zarankiewicz Problem on Tripartite Graphs)

문제 정의
본 논문은 1975년 볼로바이즈(Bollobás), 에르되시(Erdős), 세메레디(Szemerédi)가 제기한 삼분 그래프(tripartite graphs) 맥락에서의 자란츠키에비치 문제의 특정 변형을 다룬다. 핵심 질문(문제 1.1)은 최소 차수가 $n + \tau$ 이상인 $n \times n \times n$ 삼분 그래프가 완전 삼분 부분 그래프 $K_{t,t,t}$를 포함하도록 하는 가장 작은 함수 $\tau(n)$을 찾는 것이다.

임계값 $n$은 중요한데, 왜냐하면 최소 차수가 정확히 $n$인 $n \times n \times n$ 삼분 그래프들이 존재하며, 이들은 이분 그래프(따라서 삼각형이 없는 triangle-free)이기 때문이다. 이전 연구들은 $t \ge 2$에 대해 $\tau = O(n^{1 - 1/(3t^2)})$임을 입증하였으며, $t=2$인 경우 올바른 차수가 $\tau = \Theta(n^{1/2})$라는 구체적인 추측을 제시하였다. 최근의 독립적인 연구는 이 경계값을 $O(n^{1 - 1/(t(t+1))})$로 개선하였으나, 추측된 최적의 경계값은 여전히 규명되지 않은 상태였다.

방법론
저자들은 "부스터(booster)" 에지의 구조적 분석과 결합된 **밀도 증가 논법(density increment argument)**을 채택한다. 증명 전략은 다음과 같이 진행된다:

1. 구조적 이분법 (보조정리 5.1): 저자들은 충분히 높은 최소 차수를 가진 삼분 그래프가 다음 두 가지 특정 구성 중 하나를 반드시 포함함을 먼저 입증한다:

   • 경우 (i): 상수 밀도를 가진 "부스터" 에지(에지 $uv$에서$v$의 순방향 차수(forward degree)가 $u$의 차수보다 크거나 같은 에지)의 조밀한 부분 그래프.
   • 경우 (ii): 상대적으로 작은 순방향 차수를 가지면서도 많은 "헤비(heavy)" 에지(공통 이웃의 크기가 큰 에지)와 연결된 정점들의 큰 집합.

2. 조밀한 영역 처리 (섹션 5.2): 경우 (i)의 경우, 저자들은 밀도 증가 기법을 활용한다. 만약 그래프가 $K_{t,t,t}$-free라면, 공통 이웃(codegree)의 크기가 감소하는 부스터 에지들의 부분 그래프를 반복적으로 찾을 수 있음을 보여준다. 그러나 보조정리 4.2에 의해, 부스터 에지는 본질적으로 최소 차수의 초과분 $\tau$에 비례하는 큰 공통 이웃 크기를 갖는다. 이 모순은 $K_{t,t,t}$의 존재를 강제한다.

3. 헤비 에지 영역 처리 (섹션 5.3): 경우 (ii)의 경우, 저자들은 제한된 순방향 차수를 가지면서 많은 헤비 에지와 연결된 정점들의 집합인 "$r$-스쿼드($r$-squad)" 개념을 도입한다. 저자들은 매개변수 $r$에 대한 극대성 논증을 사용한다. 만약 극대 $r$-스쿼드가 존재한다면, 더 큰 매개변수 $r'$을 갖는 새로운 스쿼드를 구성할 수 있으며, 이는 $K_{t,t,t}$를 발견하지 못하는 한 모순을 일으킨다. 이 과정에는 공통 이웃의 정교한 계산과 의존적 무작위 선택(dependent random choice) 보조정리의 적용이 포함된다.

4. 극한 구성 (섹션 2): 상한의 타이트함(tightness)을 입증하기 위해, 저자들은 **안드라시아이 그래프(Andrásfai graphs)**에 기반한 극한 그래프의 무한 가족을 구성한다. 이 구성들은 삼각형이 없고 3-채색 가능한 안드라시아이 그래프에 $K_{t,t}$를 피하는 이분 그래프를 결합한 가중 버전이다.

주요 기여 및 결과

• 주요 정리 (정리 1.2): 저자들은 모든 양의 정수 $t$에 대하여, 만약 $G$가 최소 차수 $\delta(G) \ge n + Kn^{1 - 1/t}$를 갖는 $n \times n \times n$ 삼분 그래프라면, $G$는 $K_{t,t,t}$를 포함하는 상수 $K$가 존재함을 증명한다.

  • 이는 $t=2$인 경우의 볼로바이즈-에르되시-세메레디 추측($\tau = O(n^{1/2})$)을 확인한다.
  • 일반적인 경계값을 $O(n^{1 - 1/(t(t+1))})$에서 $O(n^{1 - 1/t})$로 개선한다.

• 타이트함: 저자들은 자란츠키에비치 수 $z(n; t) = \Theta(n^{2 - 1/t})$가 널리 믿어지는 추측을 가정할 때, 이 경계값이 상수 $K$에 대해 최선임을 주장한다. 섹션 2에서 구성된 극한 예시들은 $n + \Omega(n^{1 - 1/t})$의 최소 차수를 달성하면서도 $K_{t,t,t}$-free 상태를 유지한다.

• 극한 예시의 다양성: 본 논문의 중요한 기여 중 하나는 "서로 멀리 떨어진(pairwise far apart)" 극한 그래프들의 무한 가족을 발견한 것이다. 구체적으로, 서로 다른 매개변수 $k \neq k'$에 대해, 하나의 극한 그래프 $G_{k,n}$을 다른 그래프의 부분 그래프로 변환하려면 $\Omega(n^2)$개의 에지를 삭제해야 한다. 이는 기존의 극한 예시들(예: 불어온(blown-up) $C_5$ 기반)과 대조되며, 극한 구성의 구조가 이전에 인식되었던 것보다 훨씬 풍부함을 보여준다.

의의
본 논문은 이분 투란 수(bipartite Turán numbers)에 관한 표준적인 추측 하에서 문제 1.1에 대한 완전한 해답을 제공한다. 이는 최소 차수 임계값의 추측된 차수 규모를 확인함으로써 다분 그래프 투란 이론의 오랜 미결 과제를 해결한다. 또한, 안드라시아이 그래프를 사용하여 다양한 극한 예시를 생성함으로써, 극한 그래프가 구조적으로 유일하거나 몇 가지 알려진 구성에 국한될 것이라는 직관에 도전한다. 개발된 기술들, 특히 부스터 에지에 적용된 밀도 증가 논법과 삼분 설정에서의 헤비 에지 분석은 유사한 극한 그래프론 문제들을 다루기 위한 새로운 도구를 제공한다.