A 60-Vertex Lower Bound for Cubic Bipartite Counterexamples to the Erd\H{o}s-Gyárfás Conjecture

기술 요약: 에르되시-갸르파스 추측에 대한 입방 이분 그래프의 60-정점 하한선

문제 정의
에르되시-갸르파스(Erdős–Gyárfás) 추측은 최소 차수가 3 이상인 모든 유한 단순 그래프가 2의 거듭제곱(즉, 4, 8, 16, 32, ...)의 길이를 갖는 단순 사이클을 포함한다는 가설이다. 이 추측은 일반적인 그래프에 대해서는 미해결 상태로 남아 있으나, 특정 제한된 클래스에 대해서는 검증되었다. 본 논문은 단순 입방 이분 그래프(simple cubic bipartite graphs) 클래스에 초점을 맞춘다. 이 연구 이전의 기존 연구에서는 이 클래스의 잠재적 반례에 대한 차수(정점 수)의 하한선이 $n \ge 30$(Markström의 2004년 계산 결과) 또는 $n \ge 32$(2026년 공개된 SAT 기반 계산 결과)로 알려져 있었다. 본 연구의 목적은 60개 미만의 정점을 가진 반례가 존재할 수 있는지 여부를 판별하는 것이다.

방법론
본 증명은 구조적 그래프 이론의 축소 기법과 인증된 전수 조사 컴퓨터 탐색의 결합을 사용한다. 방법론은 다음과 같은 세 가지 주요 단계로 진행된다:

1. 구조적 축소 (무어 상한 및 인시던스 변환):

   • 저자는 먼저 에지 루트 무어 상한(edge-rooted Moore bound) 논증을 적용하여, 58개 이하의 정점을 가진 임의의 단순 입방 이분 그래프가 $C_4$와 $C_8$를 피한다면 반드시 길이 6의 사이클($C_6$)을 포함해야 함을 보여준다.
   • 그 후, 해당 그래프를 인시던스 구조(incidence structure)로 변환한다. 입방 이분 그래프는 대칭 $v_3$-구성(symmetric $v_3$-configuration, $v$개의 점과 $v$개의 블록을 가진 선형 3-유니폼, 3-정규 집합계)의 **레비 그래프(Levi graph)**로 표현된다.
   • 이 변환 하에서, 그래프의 $C_6$는 구성 내의 베르주 삼각형(Berge triangle)(세 개의 블록이 서로 다른 점들에서 쌍으로 교차함)에 대응한다.
   • 그래프에서의 $C_4$ 및 $C_8$의 부재는 해당 구성이 선형(linear)(두 블록이 하나의 점 이상을 공유하지 않음)이며, 베르주 사이클 4 또는 8을 포함하지 않는 것으로 번역된다.

2. 루티드 탐색 및 정규화 (Rooted Search and Normalization):

   • 베르주 삼각형을 고정하고 대칭 축소를 적용함으로써, 저자는 특정 점을 통과하는 블록에 대해 최대 **두 가지 구별된 루티드 확장(rooted extensions, orbit)**만이 가능하다는 것을 입증한다.
   • 이는 문제를 두 가지 특정 루트 오빗(root orbits)에 대한 **제한 성장 탐색(restricted-growth search)**으로 축소시킨다. 탐색은 점과 블록을 사전식 순서로 추가하며 구성(configuration)을 생성하되, "점 캡(point cap)"을 29로 유지한다(왜냐하면 $2v \le 58 \implies v \le 29$이기 때문이다).
   • 금지된 베르주 사이클(길이 4 또는 8)을 생성하거나, 제약 조건을 위반하지 않고 더 이상의 블록을 추가할 수 없는 상태에 도달하면 해당 브랜치를 종료한다.

3. 인증된 전수 계산 (Certified Exhaustive Computation):

   • 서로 다른 알고리즘을 사용하는 두 가지 독립적인 $C_{16}$ 오라클(길이 16의 사이클 탐지) 구현체가 실행되었다:
     • 구현 A: 단순 경로 DFS(Depth-First Search)를 사용한다.
     • 구현 B: 7-에지 하프 패스(half-paths)의 완전한 리스트를 결합한다.
   • 두 탐색 모두 정적 위츠 증명서(static witness certificate) 시스템을 활용하였다. 스트리밍 체커는 탐색 트리를 재구성하고, 양의 사이클 위츠를 검증하며, 모든 점의 차수가 3이 되는 완성된 구성(cap 29 내에서)이 존재하지 않음을 검증한다.
   • 탐색의 정확성을 보장하기 위해 작은 구성($v \le 13$)에 대한 기존 센서스 데이터와 대조하여 검증하였다.

주요 결과

• 정리 1: 모든 단순 입방 이분 그래프는 길이 4, 8, 또는 16의 단순 사이클을 포함한다.
• 따름정리 2: 에르되시-갸르파스 추측에 대한 임의의 단순 입방 반례는 적어도 60개의 정점을 가져야 한다.
• 탐색 통계: 전수 탐색은 총 21,493개의 상태와 1,762,368개의 시도된 확장을 포함하는 두 개의 루트 오빗을 다루었다. 결정적으로, 두 오빗 모두에서 완성된 상태(completions)가 발견되지 않았다.
• 종단 장애물 (Terminal Obstruction): 탐색은 최대 깊이(19개 블록, 29개 점 모두 사용)에서 337개의 생존 상태를 식별하였다. 이 상태들은 6개의 동형 클래스(kernel)로 수렴되었다. 이 커널들에 대한 "호환 가능한 쌍 그래프(compatible-pair graphs)" 분석 결과, 이들이 포레스트(forest, 삼각형이 없는 트리 구조)임이 밝혀졌으며, 이는 20번째 블록을 추가하는 것이 $C_4, C_8, C_{16}$을 생성하지 않고서는 불가능함을 증명한다.

의의 및 주장
본 논문은 입방 이분 반례에 대한 기존 하한선을 $n \ge 30$ (또는 $n \ge 32$)에서 $n \ge 60$으로 높였다고 주장한다.

• 결과의 강점: 이 결과는 단순한 추측의 검증보다 더 강력한 형태로 진술된다. 즉, 이 클래스에서 처음 세 개의 관련 2의 거듭제곱 사이클 길이(4, 8, 16) 중 하나가 58개 이하의 정점을 가진 그래프에서 강제됨을 증명한다. 또한 32-사이클을 확인하는 것이 이 하한선을 확립하는 데 필수적이지 않음을 명시한다.
• 검증: 결과는 서로 다른 오라클과 정적 증명서를 가진 두 가지 별도의 구현체와 함께 수행된 "인증된 전수 계산"에 의해 뒷받침되며, 이는 결과가 단일 소프트웨어 버그의 산물이 아님을 보장한다.
• 한계: 논문은 계산이 측면 크기 30(60 정점)을 조사하지 않음을 명시하며, 따라서 정확히 60 정점인 지점에서 반례가 존재할 가능성을 배제하지 않는다. 본 연구는 58 정점까지의 클래스 내부 경계선을 확립하는 것이다.

아티팩트 (Artifacts)
저자는 소스 코드, 증명서, 로그 및 검증 프로그램을 포함한 완전한 재현성을 제공하며, 이는 Zenodo (DOI: 10.5281/zenodo.21695513) 및 GitHub 저장소에 보관되어 있다. 또한, OpenAI의 도구(ChatGPT 및 Codex)가 코드 개발, 구조적 접근 방식 수립, 원고 작성에 도움을 주었으나, 수학적 논증과 증거적 근거는 유지된 코드, 로그 및 증명서에 기반하고 있음을 밝힌다.