Hamilton decompositions of all directed tori at odd modulus

기술 요약: 홀수 모듈로에서의 방향성 토러스 해밀토니안 분해에 대한 접두사-카운트 폐쇄 정리

문제 제기
본 논문은 사이클의 방향성 데카르트 곱, 특히 방향성 등변 $d$-토러스 $D_d(m) = \text{Cay}((\mathbb{Z}/m\mathbb{Z})^d, \{e_0, \dots, e_{d-1}\})$ 에 대한 해밀토니안 분해 문제를 다룬다. 해밀토니안 분해란 그래프의 $d|V|$ 개의 호를 정확히 $d$ 개의 서로소인 방향성 해밀토니안 사이클로 분할하는 것을 요구한다. 이러한 그래프의 해밀토니안성 (단일 스패닝 사이클의 존재) 은 잘 연구되어 왔으나, 모든 차원 $d \ge 2$ 와 홀수 모듈로 $m \ge 3$ 에 대한 더 강력한 호 분할 문제는 해결되지 않은 채 남아 있었다. 본 논문은 모든 정수 $d \ge 2$ 와 모든 홀수 정수 $m \ge 3$ 에 대해 $D_d(m)$ 이 방향성 해밀토니안 분해를 허용함을 증명하는 것을 목표로 한다.

방법론
증명 전략은 "해결된" 기본 차원 집합을 기반으로 임의의 차원에 대한 분해를 구성할 수 있게 해주는 두 가지 주요 폐쇄 메커니즘에 의존한다. 방법론은 모듈로 $m$ 과 차원 $d$ 간의 관계에 따라 두 가지 가지로 나뉜다:

1. 고모듈로 카운트 가지 ($m \ge d$):

   • 루트-플랫 증명서 (Root-Flat Certificates): 저자들은 층 합 $S(x) = \sum x_i = 0$ 위에 정의된 구조인 "루트-플랫 증명서"를 도입한다. 이는 전역 분해 문제를 루트-플랫 슬라이스 $A_{d,m}$ 에 대한 국소 매핑을 구성하는 문제로 축소한다.
   • 접두사 좌표 및 단일 층 인수분해: 루트-플랫 공간은 삼각 전단사 함수를 통해 접두사 좌표로 매핑된다. 분해는 심볼 집합 $\{0, \Delta, 2, \dots, d-1\}$ 에 기반하여 접두사 좌표를 치환하는 매핑 $M^\sigma_c$ 를 사용하여 층별로 구성된다.
   • 접두사-카운트 기원성: 이러한 층 매핑의 합성이 단일 사이클을 형성하도록 보장하는 핵심 기준 (정리 4.4) 이 있다. 이는 시퀀스에 사용된 심볼에 대한 특정 카운트 조건을 요구한다: $\gcd(N_0, m) = 1$ 및 $k \ge 2$ 에 대해 $\gcd(N_k - N_\Delta, m) = 1$.
   • 부호付き 이진 층: $d$ 가 홀수인 $m \ge d$ 에 대해 이러한 카운트 조건을 만족시키기 위해, 저자들은 "접두사 허용 카운트 행렬"을 구성한다. $q \ge 2$ (여기서 $m = (d-1)q + r$) 인 경우, 필요한 모듈로 단위를 유지하면서 행과 열의 합을 균형 있게 맞추기 위해 $\{-2, -1, 1, 2\}$ 의 항목을 가진 부호付き 이진 층 (행렬) 을 활용한다. 제한된 경우 $q=1$ 에 대해서는 별도의 매칭 수정이 처리된다.

2. 기본-꼬리 모듈로-거래 가지 ($m < d$):

   • 기본-꼬리 리프트: 모듈로가 차원에 비해 작을 때, 본 논문은 "기본-꼬리" 구성을 채택한다. 해결된 기본 차원 $b$ ($D_b(m)$ 이 분해 가능함) 를 차원 $T = d-b$ 의 꼬리와 결합한다.
   • 원통 분해: 기본 다중 그래프는 원통으로 분해된다. 기본 내의 활성 호는 "국소 심볼 거래"를 예약하기 위해 꼬리 알파벳의 심볼을 할당받는다.
   • 활성 잔여물 예약: "원통 거래 저장소"를 사용하여 저자들은 색상 간 심볼의 국소 스왑을 수행할 특정 정점을 예약한다. 이는 꼬리 차원에 필요한 접두사-카운트 기원성 조건을 만족시키기 위해 색상 - 심볼 카운트 잔여물을 조정하여, 기본 분해를 전체 차원 $d$ 로 리프트하는 것을 가능하게 한다.

주요 기여

• 두 가지 폐쇄 메커니즘: 본 논문은 해결된 차원 집합 $S$ 에 대해 두 가지 명확한 폐쇄 규칙을 확립한다:
  • 곱 폐쇄: $a, b \in S$ 이면 $ab \in S$.
  • 후속자 폐쇄: $b \in S$ 이고 $b \ge 5$ 이면 $2b + 1 \in S$.
• 고모듈로 구성: 부호付き 이진 층과 접두사-카운트 행렬을 사용하여, 미리 해결된 기본 차원에 의존하지 않는 홀수 $d \ge 5$ 및 $m \ge d$ 에 대한 균일한 구성.
• 기본-꼬리 모듈로-거래 정리: 해결된 기본 $b$ 가 주어졌을 때, $d$ 가 모듈로 $m$ 에 대한 단위들의 합으로 분해될 수 있고 특정 크기 부등식 ($T > b$ 및 $mb > m \cdot d \cdot T$) 이 성립한다면 $m < d$ 인 $D_d(m)$ 을 해결하는 일반 정리 (정리 1.3).
• 형식화: 모든 차원 정리와 증명의 특정 의존성 구조를 검증하는 Lean(Lean 4) 형식화가 결과에 수반된다.

결과
본 논문은 정리 1.5를 증명한다: 모든 정수 $d \ge 2$ 와 모든 홀수 정수 $m \ge 3$ 에 대해, 방향성 기본 케일리 토러스 $D_d(m)$ 은 방향성 해밀토니안 분해를 허용한다.

증명은 최소한의 기본 차원 집합을 식별함으로써 진행된다:

• 차원 2 및 3: 부록 B 에서 증명됨 (차원 2 는 고전적; 차원 3 은 홀수 $m$ 에 대해 증명됨).
• 차원 5 및 7: 인용된 외부 정리 ([22], [23]) 에서 비롯됨.

폐쇄 규칙을 사용하여:

• 곱 폐쇄는 차원 $4, 6, 8, 9, 10, \dots$ 를 생성한다.
• 후속자 폐쇄 ($b=5$ 에서 시작) 는 $11$ 을 생성하고, 이어서 더 높은 홀수 차원을 생성한다.
• "이진 - 삼진 구간 타격" 논증 (보조정리 10.3) 은 임의의 홀수 $d \ge 29$ 에 대해, 기본 - 꼬리 조건이 충족되는 해결된 기본 $b \in \langle 2, 3 \rangle$ 이 존재함을 보여준다.
• 강한 수학적 귀납법은 모든 $d \ge 2$ 가 커버됨을 확인한다.

의의 및 주장
본 논문은 홀수 모듈로를 가진 등변 방향성 토러스 전체 클래스에 대한 해밀토니안 분해 문제를 해결했다고 주장한다. 이는 이전 문헌 (예: Trotter–Erdős, Curran–Witte) 에서 다루어진 해밀토니안성 문제보다 강력한 호 분할 문제에 대한 해결책으로 이 작업을 위치시킨다.

저자들은 증명의 구조적 성격을 강조한다:

• 이는 카운트 행렬 대 모듈로 거래와 같은 상이하지만 상호 보완적인 메커니즘을 통해 고모듈로 및 저모듈로 사례를 통합한다.
• 이는 모든 차원에 대한 무한한 문제를 유한한 기본 입력 집합 (2, 3, 5, 7) 과 두 가지 대수적 폐쇄 연산으로 축소한다.
• 기계 검증 가능한 형식화의 포함은 특히 기본 - 꼬리 가지의 정교한 카운팅 및 매칭 조건과 같은 복잡한 조합론적 논증에 대한 검증 산출물 역할을 한다.

본 논문은 짝수 모듈로나 비등변 토러스에 대한 문제 해결을 주장하지 않으며, 이 특정 분해 문제의 이론적 해결을 넘어 새로운 응용을 제안하지도 않는다. 그 의의는 지정된 그래프 클래스에 대한 결과의 완전성과 제공된 엄격한 형식 검증에 있다.