New Upper Bounds for the Classical Ramsey Numbers $R(4,4,4)$, $R(3,4,5)$ and $R(3,3,6)$

이 논문은 고전적인 램지 수 $R(4,4,4)$, $R(3,4,5)$, $R(3,3,6)$에 대해 기존에 알려진 상한선보다 더 엄격한 새로운 상한값 (각각 229, 157, 91) 을 제시합니다.

핵심

🎨 1. 램지 수란 무엇일까요? (우산과 친구들)

먼저, 이 논문이 다루는 **'램지 수'**가 무엇인지 이해해야 합니다.

상상해 보세요. 여러분이 거대한 파티를 열고 있습니다. 파티에는 아주 많은 손님이 오고, 서로의 관계를 나타내기 위해 빨간색, 파란색, 초록색 등 여러 가지 색의 실로 서로를 연결합니다.

• 질문: "이 파티에 최소한 몇 명이 모여야, 서로 3 명 이상이 모두 빨간색 실로 연결되어 있거나, 서로 4 명 이상이 모두 파란색 실로 연결되어 있는 '친구 그룹'이 반드시 하나씩은 생기게 될까요?"

이때 필요한 최소 인원수가 바로 '램지 수'입니다.

• 숫자가 작을수록 (예: 3 명) 쉽게 찾을 수 있지만, 숫자가 커질수록 (예: 4 명, 5 명) 그 수를 정확히 계산하는 것은 마치 우주 전체의 별을 세는 것처럼 어렵습니다.

지금까지 수학자들은 이 수를 구할 때 **"상한선 (최대 가능성)"**을 계산하는 하나의 공식 (정리 1.1) 을 주로 사용했습니다. 하지만 이 공식은 항상 정확한 답을 주지는 못했고, "아마도 이 정도는 넘지 않을 거야"라고 대략적인 상한을 제시할 뿐이었습니다.

---

🔍 2. 이 논문이 한 일은 무엇일까요? (더 좁은 울타리)

이 논문 (루이스 보자 저자) 의 핵심은 **"기존에 알려진 상한선을 조금 더 좁게 만들었다"**는 점입니다.

기존의 공식은 파티 인원이 100 명일 때 "적어도 90 명 이상은 있어야 친구 그룹이 생길 거야"라고 말한다면, 이 논문은 **"아니야, 89 명만 있어도 생길 거야"**라고 더 정확한 (더 낮은) 숫자를 제시한 것입니다.

🧱 비유: 벽돌 쌓기

기존의 공식은 벽돌을 쌓아 올릴 때, "이 높이는 절대 넘지 않아"라고 말해주는 거대한 지붕과 같습니다. 하지만 이 지붕이 너무 높아서 실제 건물의 높이를 정확히 알기 어렵습니다.

이 논문은 그 지붕을 조금만 낮추는 새로운 방법을 고안했습니다. 특히 3 가지 이상의 색상이 섞인 복잡한 상황 (예: 빨강, 파랑, 초록이 모두 섞인 파티) 에서 기존 공식이 약점을 보였던 특정 경우들을 찾아내어, 더 정확한 상한선을 제시했습니다.

---

🚀 3. 구체적인 성과 (새로운 기록)

이 논문을 통해 다음과 같은 새로운 '최대 인원수' 기록이 세워졌습니다. (기존보다 더 낮은 숫자가 나왔다는 뜻입니다.)

1. R(4, 4, 4) ≤ 229
   • 이전: 230 명 이상이면 무조건 4 명씩 같은 색 친구 그룹이 생김.
   • 이제: 229 명만 있어도 생김. (1 명 줄임)
2. R(3, 4, 5) ≤ 157
   • 이전: 158 명.
   • 이제: 157 명으로 줄임.
3. R(3, 3, 6) ≤ 91
   • 이전: 92 명.
   • 이제: 91 명으로 줄임.

이 숫자 차이가 작아 보일 수 있지만, 수학적으로 이는 매우 큰 발견입니다. 왜냐하면 램지 수를 구하는 것은 매우 어렵기 때문에, 1 만 명 단위의 숫자에서 1 만 1 천 명으로 줄이는 것보다, 100 명 단위의 숫자에서 1 명을 줄이는 것이 훨씬 더 치밀한 계산과 통찰이 필요하기 때문입니다.

---

💡 4. 어떻게 이런 일을 했을까요? (3 의 법칙과 미끼)

저자는 기존 공식이 완벽하지 않은 특정한 상황을 찾아냈습니다.

• 기존 공식의 약점: 기존 공식은 모든 경우에 적용되지만, 가끔은 "너무 보수적으로" 상한선을 높게 잡습니다. 마치 "비가 올 확률이 50% 라면 우산을 꼭 챙겨라"라고 말하는 것과 비슷합니다.
• 새로운 방법 (Theorem 2.1): 저자는 **"만약 파티 인원 수가 3 으로 나누어 떨어지지 않는 특정 패턴을 가진다면, 그리고 특정 조건을 만족한다면, 기존 공식이 제시한 숫자보다 1 명만 줄여도 된다"**는 규칙을 발견했습니다.

이를 **미끼 (Trap)**에 비유할 수 있습니다.
기존 공식은 "이 미끼에 걸리면 100% 잡힌다"고 했지만, 저자는 "아니, 이 미끼는 99% 만 걸리고 1% 는 빠져나갈 수 있어. 그래서 우리가 잡을 수 있는 최대 숫자는 100 이 아니라 99 야"라고 증명해낸 것입니다.

특히 **나머지 3 (Modulo 3)**이라는 수학적 개념을 이용해, "이 숫자는 3 으로 나누어 떨어지지 않으므로, 기존 공식이 말한 최대 인원수는 틀릴 수밖에 없어"라고 논리적으로 반박했습니다.

---

🌟 5. 결론: 왜 이 연구가 중요할까요?

이 논문은 마치 지도 제작자가 "이 산의 높이는 1,000m 야"라고 적혀있던 지도를 수정하여, "아니, 실제로는 999m 야"라고 정확히 고쳐주는 것과 같습니다.

• 정확성 향상: 수학자들이 복잡한 조합 문제를 풀 때, 더 좁은 범위에서 답을 찾을 수 있게 도와줍니다.
• 새로운 통찰: 단순히 숫자를 줄이는 것을 넘어, "왜 기존 공식이 실패했는지"에 대한 새로운 수학적 원리 (3 의 법칙 등) 를 제시했습니다.
• 미래의 가능성: 이번 연구에서 사용된 방법은 앞으로 더 큰 숫자 (예: 10 가지 색상이 섞인 경우) 에 대한 램지 수를 계산할 때도 적용될 수 있는 토대가 됩니다.

한 줄 요약:

"수학자들은 복잡한 파티에서 친구 그룹이 생기는 최소 인원을 계산할 때, 기존에 알려진 '최대 가능성'이 조금 과장되었음을 발견하고, 3 가지 색상의 경우에 대해 더 정확하고 낮은 숫자를 찾아냈습니다."

이 연구는 우리가 세상을 이해하는 데 필요한 '불확실성'을 조금 더 줄여주는, 작지만 의미 있는 진전입니다.

기술 요약

논문 요약: 고전적 램지 수에 대한 새로운 상한선

1. 연구 배경 및 문제 정의 (Problem)

• 램지 수 (Ramsey Numbers): $R(k_1, \dots, k_r)$는 완전 그래프 $K_N$의 간선을 $r$ 가지 색상으로 칠할 때, 어떤 색 $i$에 대해 $k_i$ 개의 정점을 가진 완전 부분 그래프 ($K_{k_i}$) 가 반드시 존재하도록 하는 최소 정수 $N$을 의미합니다.
• 현재의 한계: 3 가지 이상의 색상 ($r \ge 3$) 을 가진 고전적 램지 수의 정확한 값은 거의 알려져 있지 않습니다. 기존에 알려진 가장 강력한 상한선 (Upper Bound) 은 Theorem 1.1로 알려진 재귀적 부등식에서 유도되었습니다.
  • 기존 부등식: $R(k_1, \dots, k_r) \le P(k_1, \dots, k_r) = 2 - r + \sum_{i=1}^r R(k_1, \dots, k_i-1, \dots, k_r)$
  • 이 부등식은 우변과 합계 중 적어도 한 항이 짝수일 때 엄격하게 성립합니다.
• 연구 목적: Theorem 1.1 로부터 직접 유도되지 않는, 더 강력한 새로운 상한선을 도출하여 $R(4, 4, 4)$, $R(3, 4, 5)$, $R(3, 3, 6)$ 등 특정 램지 수의 상한을 낮추는 것입니다.

2. 방법론 (Methodology)

저자는 기존 부등식의 한계를 극복하기 위해 **정규성 (Regularity)**과 삼각형 (Triangle) 의 개수에 대한 모듈러 산술 (Modular Arithmetic) 조건을 결합한 새로운 판정 기준을 제시했습니다.

• 핵심 아이디어:
  • 만약 $R(k_1, \dots, k_r) = P(k_1, \dots, k_r)$라고 가정하면, $P-1$개의 정점을 가진 그래프 $G$가 존재해야 합니다.
  • Lemma 1.2 에 따르면, 이 그래프는 특정 색 $i_0$에 대해 정규 그래프 (Regular Graph) 성질을 가지며, 각 정점 $v$는 $M$개의 $i_0$색 삼각형에 속하게 됩니다.
  • 전체 그래프에서 $i_0$색 삼각형의 총 개수를 세면 $(P-1)M$이 되며, 이는 각 삼각형이 3 번씩 세어지므로 3 의 배수여야 합니다.
• Theorem 2.1 (주요 판정 기준):
  다음 세 가지 조건이 만족될 때, $R(k_1, \dots, k_r) \le P(k_1, \dots, k_r) - 1$이 성립합니다.
  1. $P(k_1, \dots, k_r) \not\equiv 1 \pmod 3$
  2. 특정 $i_0$에 대해 $R(\dots, k_{i_0}-1, \dots) = P(\dots, k_{i_0}-1, \dots) \not\equiv 1 \pmod 3$ (즉, 하위 램지 수가 기존 상한선과 일치하고 3 으로 나눈 나머지가 1 이 아님)
  3. $R(\dots, k_{i_0}-2, \dots) \not\equiv 1 \pmod 3$
  • 증명 논리: 위 조건 하에서 $(P-1)M$이 3 의 배수가 될 수 없으므로 (모든 인자가 3 의 배수가 아님), $R = P$라는 가정이 모순이 됩니다. 따라서 실제 램지 수는 $P-1$ 이하여야 합니다.

3. 주요 기여 및 결과 (Key Contributions & Results)

이 논문의 주요 기여는 Theorem 2.1 을 적용하여 기존 Theorem 1.1 로부터 얻어진 상한선보다 1 만큼 낮은 새로운 상한선을 제시한 것입니다.

• 새로운 상한선 도출:

  1. $R(4, 4, 4) \le 229$: 기존 상한선 $P_3(4) = 230$을 1 만큼 낮춤.
     • $R(3, 4, 4) = 77$ ($77 \not\equiv 1 \pmod 3$) 임을 이용.
  2. $R(3, 4, 5) \le 157$: 기존 상한선 $P(3, 4, 5) = 158$을 1 만큼 낮춤.
     • $R(3, 3, 5) = 57$ 및 $R(3, 4, 4) = 77$임을 이용.
  3. $R(3, 3, 6) \le 91$: 기존 상한선 $P(3, 3, 6) = 92$를 1 만큼 낮춤.
     • $R(3, 3, 5) = 57$임을 이용.
  4. $R(\underbrace{3, \dots, 3}_{10}, 4) \le 608,152,553$: 10 개의 3 과 하나의 4 로 구성된 11 색 램지 수에 대한 상한선 개선.
     • $R_{11}(3)$과 $R_{10}(3)$의 값이 기존 상한선과 일치함을 전제로 증명.

• 한계점 명시:

  • Theorem 2.1 을 통해 얻어지는 추가적인 개선은 Theorem 2.2~2.5 의 결과에 의존합니다.
  • $r \le 10$인 경우, $R(3, \dots, 3, 5)$나 $R(3, \dots, 3, 4, 4)$와 같은 특정 형태에 대해서는 Theorem 1.1 로부터 유도된 것보다 더 나은 상한선을 얻지 못했습니다.

4. 의의 (Significance)

• 이론적 발전: 3 색 이상 램지 수에 대한 상한선을 개선하는 데 있어, 단순한 재귀적 부등식 (Theorem 1.1) 을 넘어선 첫 번째 체계적인 방법론을 제시했습니다.
• 구체적 수치 개선: 수십 년간 갱신되지 않았던 $R(4, 4, 4)$, $R(3, 4, 5)$, $R(3, 3, 6)$의 상한선을 각각 1 만큼 낮추어, 정확한 램지 수를 찾는 범위를 좁혔습니다.
• 방법론적 확장: 그래프의 국소적 구조 (정점의 차수, 삼각형 개수) 와 전역적 성질 (모듈러 산술) 을 결합하여 램지 수의 성질을 분석하는 새로운 접근법을 제시했습니다. 이는 향후 더 큰 램지 수에 대한 상한선 개선 연구의 기초가 될 수 있습니다.

결론

Luis Boza 는 기존에 알려진 재귀적 부등식의 한계를 극복하기 위해 모듈러 산술 조건을 활용한 새로운 판정 기준 (Theorem 2.1) 을 제시했습니다. 이를 통해 $R(4, 4, 4)$, $R(3, 4, 5)$, $R(3, 3, 6)$ 등 주요 다색 램지 수의 상한선을 기존 값보다 1 만큼 낮추는 새로운 결과를 도출했습니다. 이는 다색 램지 이론 분야에서 중요한 진전으로 평가됩니다.