Graph Puzzles II.1: Counterexamples to Jain's Second Unit Vector Flows Conjecture

이 논문은 Tutte 의 5-플로우 추측을 함축할 수 있는 자인 (Jain) 의 두 번째 단위 벡터 흐름 추측이 성립하지 않음을 보이기 위해, 해당 추측을 반증하는 2 개의 반례를 구성하고 있습니다.

핵심

🌍 제목: 구 위의 퍼즐과 깨진 약속 (Jain 의 두 번째 추측에 대한 반증)

1. 배경: "구" 위의 이상한 교통 규칙

이 논문은 **'그래프 (그물망)'**와 **'구 (공)'**를 연결하는 이야기를 합니다.

• 그래프: 도시의 도로망처럼 점 (교차로) 과 선 (도로) 으로 이루어진 구조라고 생각하세요.
• 흐름 (Flow): 이 도로 위를 차들이 지나가는 것이라 상상해 보세요. 각 도로에는 차가 한 방향으로만 지나가야 하고, 모든 교차로에 들어오는 차의 수와 나가는 차의 수가 같아야 합니다.
• 벡터 흐름: 여기서 차의 크기가 아니라, 방향을 중요시합니다. 각 도로에 3 차원 공간 (우주) 에서의 **'단위 벡터 (길이가 1 인 화살표)'**를 붙여주는 것입니다. 마치 구 (공) 표면 위의 점들처럼요.

수학자 K. 자인 (K. Jain) 은 두 가지 멋진 가설을 세웠습니다.

1. 첫 번째 가설: 다리가 끊어지지 않은 모든 도로망에는 이런 '구 위의 흐름'이 항상 존재한다.
2. 두 번째 가설 (이 논문의 주인공): 구 표면의 모든 점에 -4 부터 4 까지의 숫자를 붙일 수 있다. 단, 두 가지 규칙이 있어야 합니다.
   • 규칙 1: 정반대 방향 (북극과 남극처럼) 에 있는 점들은 서로 반대 숫자여야 한다 (예: 3 이면 -3).
   • 규칙 2: 구의 큰 원 (적도 같은 것) 위에 있는 세 점이 서로 같은 간격으로 떨어져 있다면, 그 세 숫자의 합이 0이 되어야 한다.

만약 이 두 가설이 모두 맞다면, 수학계의 거대한 난제인 **' Tutte 의 5-흐름 추측'**이라는 보석 같은 문제를 해결할 수 있었습니다.

2. 문제: "숫자 5"가 필요한 곳

저자 (닐레이 울리야노프) 는 "잠깐만요, 두 번째 가설은 틀릴지도 모릅니다"라고 말합니다.

그는 구 표면 위에 특정 점들을 배치했는데, 이 점들에 -4 부터 4 까지의 숫자만으로는 규칙을 지키면서 숫자를 붙일 수 없다는 것을 증명했습니다.

• 비유: 마치 4 개의 색깔 (빨강, 파랑, 초록, 노랑) 로만 구를 칠해야 하는데, 어떤 구는 무조건 **5 번째 색깔 (보라색)**이 필요해서 칠할 수 없는 상황과 같습니다.
• 이 논문은 그런 **'5 번째 색깔이 필요한 점들의 집합'**을 두 가지 방법으로 찾아냈습니다.

3. 해결책: 두 가지 반증 예시

저자는 두 가지 다른 방법으로 이 '불가능한 구'를 만들었습니다.

① 첫 번째 방법: 50 개의 점으로 만든 거대한 구조

• 비유: 정교하게 만들어진 **20 면체와 12 면체가 섞인 모양 (이코시도데카헤드론)**을 기본으로 삼았습니다. 여기에 점들을 더 추가하고, 점들 사이의 관계를 복잡하게 꼬아 50 개의 점을 만들었습니다.
• 결과: 이 50 개의 점에 숫자를 붙이려고 시도해보니, -4~4 범위의 숫자만으로는 모든 규칙을 만족시킬 수 없었습니다. 반드시 -5 와 5가 필요했습니다.
• 검증: 컴퓨터가 이 문제를 해결할 수 있는지 수천 가지 경우의 수를 다 확인해 보았지만, 불가능하다는 결과가 나왔습니다.

② 두 번째 방법: 36 개의 점으로 만든 더 작은 구조

• 비유: 첫 번째 방법보다 더 작고 간결한 구조를 만들었습니다. 여기서는 '제곱근'이라는 수학적 도구를 이용해 점들의 위치를 계산했습니다.
• 결과: 36 개의 점만으로도 역시 -4~4 범위의 숫자로는 규칙을 지킬 수 없었습니다. 역시 -5 와 5가 필요했습니다.
• 의미: "아니, 점의 개수가 많아서 그런 게 아니라, 점의 개수가 적어도 (36 개) 여전히 불가능하구나"라는 것을 보여줍니다.

4. 결론: 무엇을 의미할까?

이 논문은 **"자인의 두 번째 가설은 틀렸다"**는 것을 증명했습니다.

• 구 표면의 점들에 -4~4 숫자를 붙이는 간단한 규칙은, 생각보다 훨씬 까다롭고 복잡한 구조에서는 통하지 않습니다.
• 하지만 이것이 모든 것이 끝난 것은 아닙니다. 저자는 "아마도 -44 범위를 조금만 넓히거나 (예: -55), 혹은 점들의 위치를 아주 특별한 방식으로만 고르면 여전히 이 가설이 통할지도 모른다"고 말합니다.

한 줄 요약:

"수학자들이 구 (공) 위에 숫자를 붙이는 간단한 규칙을 세웠는데, 저자는 그 규칙이 모든 경우에 적용되지 않는 '예외적인 구' 두 개를 찾아내어 그 규칙이 깨졌음을 증명했습니다. 이제 우리는 더 정교한 규칙을 찾아야 합니다."

이 연구는 수학의 미해결 문제를 풀기 위한 여정에서, "우리가 생각한 길이 (가설) 가 통하지 않는 곳"을 정확히 찾아낸 중요한 이정표가 됩니다.

기술 요약

논문 요약: Jain 의 두 번째 단위 벡터 흐름 추측에 대한 반례

저자: Nikolay Ulyanov
주제: 그래프 이론, 조합론, 기하학적 흐름 (Flows), SAT 솔버 활용

1. 연구 배경 및 문제 정의

이 논문은 K. Jain 이 제안한 두 가지 추측과 W. T. Tutte 의 유명한 5-흐름 추측 (Tutte's 5-flow conjecture) 간의 관계를 다룹니다.

• 추측 1.1 (단위 벡터 흐름): 모든 브리지 (bridge) 가 없는 그래프는 $S^2$ (3 차원 단위 구) 상의 점으로 에지를 매핑하는 0 이 아닌 흐름을 가진다.
• 추측 1.2 ($S^2$ nz5-흐름): $S^2$ 상의 점들에 $\{-4, -3, -2, -1, 1, 2, 3, 4\}$ 값을 할당하는 함수 $q$가 존재하여, 다음 조건을 만족한다.
  1. 대칭점 (antipodal points) 은 서로 반대 부호의 값을 가진다 ($q(-x) = -q(x)$).
  2. 대원 (great circle) 위에서 등간격으로 떨어진 세 점의 값의 합은 0 이다.
• Tutte 의 5-흐름 추측 (Conjecture 1.3): 모든 브리지 없는 3-정규 그래프는 0 이 아닌 5-흐름을 가진다.

핵심 문제: 만약 추측 1.1 과 1.2 가 모두 참이라면, 이는 Tutte 의 5-흐름 추측을 증명하는 것으로 이어집니다. 따라서 이 논문은 추측 1.2 ($S^2$ nz5-흐름) 가 거짓임을 증명하여, 두 추측의 결합을 통한 Tutte 추측 증명 시도가 실패했음을 보여줍니다.

2. 연구 방법론

저자는 추측 1.2 가 성립하지 않는 구체적인 $S^2$ 상의 유한 점 집합 (finite subsets) 을 두 가지 방법으로 구성했습니다.

• 구성 전략:
  • 반례 1: 이코시도데카헤드론 (Icosidodecahedron, 30 점) 을 기반으로 한 50 점 확장 구조.
  • 반례 2: 제곱근 산술 (square root arithmetic) 을 기반으로 한 36 점 구조.
• 검증 도구:
  • 각 점 집합에 대해 $\{-4, \dots, 4\}$ 범위의 값만 사용하여 조건을 만족하는 라벨링이 가능한지 SAT (Boolean Satisfiability) 문제로 변환하여 검증했습니다.
  • PicoSAT/pycosat 솔버를 사용하여 CNF (Conjunctive Normal Form) 식의 불만족 (unsatisfiability) 을 확인했습니다.
  • Lean 4 형식 증명 도구를 사용하여 결과의 엄밀성을 추가로 검증했습니다.
  • 수치 오차 처리를 위해 $\epsilon = 10^{-7}$의 허용 오차를 사용했으며, 가능한 경우 정확한 산술 (exact arithmetic) 로 교차 검증했습니다.

3. 주요 결과 및 기여

논문은 추측 1.2 를 반증하는 두 가지 구체적인 반례를 제시합니다. 두 경우 모두 $\{-4, \dots, 4\}$ 범위의 값으로는 조건을 만족할 수 없으며, 최소 $\pm 5$ 값이 필요함을 보여줍니다. 즉, 5-흐름이 불가능하고 6-흐름 (nz6-flow) 만 가능함을 의미합니다.

A. 반례 1: 50 점 확장 구조 (Icosidodecahedron Expansion)

• 구성: 이코시도데카헤드론의 30 점 각각에 대해 평면 $\langle x, p \rangle = -0.5$ 위에 작은 원을 설정하고, 구면 거리 $2\pi/5$만큼 떨어진 점 쌍에 해당하는 원들의 교점을 추가하여 총 50 점을 생성했습니다.
• 구조적 특징: 40 개의 대원 삼중항 (great-circle triples) 을 가지며, 대칭점을 몫 (quotient) 으로 취하면 페테르슨 그래프 (Petersen graph) 와 10-꼭지점 뫼비우스 사다리 (Möbius ladder) 가 결합된 구조를 가집니다.
• 검증 결과: 25 개의 대칭점 대표와 40 개의 삼중항에 대해 200 개의 변수, 19,765 개의 절 (clauses) 로 구성된 SAT 식이 **불만족 (unsatisfiable)**임을 확인했습니다.

B. 반례 2: 36 점 구성 (Square Root Arithmetic Based)

• 구성: $v_1=1, v_2=3, w=2$ 등의 파라미터를 사용하여 $\sqrt{v_1}, \sqrt{v_2}$의 선형 결합으로 좌표 값을 생성하고, 이를 $S^2$ 상에 배치했습니다.
• 구조적 특징: 126 개의 점과 108 개의 삼중항에서 시작하여, 3 개의 꼭짓점 중 2 개 이상이 오직 하나의 삼중항에만 속하는 점들을 제거하는 과정 (pruning) 을 거쳐 최종적으로 36 개의 점과 13 개의 삼중항으로 축소되었습니다.
• 검증 결과: 144 개의 변수, 6,710 개의 절로 구성된 SAT 식이 불만족임을 확인했습니다. 반면, 범위를 $\{-5, \dots, 5\}$로 확장하면 (180 변수, 13,048 절) 만족하는 해 (nz6-flow) 가 존재함을 확인했습니다.

4. 의의 및 결론

• 추측 1.2 의 부인: $S^2$ 상의 특정 유한 점 집합에 대해 $\{-4, \dots, 4\}$ 값만으로는 대칭점 조건과 대원 삼중항 합 0 조건을 동시에 만족하는 라벨링이 불가능함을 수학적으로 증명했습니다.
• Tutte 추측 증명 경로 차단: Jain 의 두 추측이 결합되어 Tutte 의 5-흐름 추측을 증명할 수 있다는 가설이 깨졌습니다. 이는 새로운 접근법 (예: 무한 집합 사용이나 대수적 좌표의 특정 형태 등) 이 필요함을 시사합니다.
• 추가 연구 질문:
  • $\pm 6$ 이상의 값이 필요한 더 작은 집합이 존재하는가?
  • Tutte 추측 증명을 위해 여전히 유효할 수 있는 $S^2$의 부분 집합은 존재하는가?
  • 0 이 아닌 $k$-흐름과 모듈로 $k$-흐름 사이의 최소 $k$ 값이 항상 일치하는가? (실험 결과 일치했으나 일반화는 미해결)

이 논문은 그래프 흐름 이론과 기하학적 조합론의 교차점에서 중요한 반례를 제시하며, 관련 추측들의 한계를 명확히 하고 향후 연구 방향을 제시했습니다. 모든 코드와 검증 데이터는 GitHub 저장소에서 공개되어 있습니다.