Exact Zarankiewicz Values On Two Finite Frontier Slices

기술 요약: 두 개의 유한 프런티어 슬라이스에 대한 정확한 자란키비치 값(Exact Zarankiewicz Values)

문제 정의
본 논문은 $m$과 $n$ 크기의 두 부분 집합을 가진 이분 그래프에서 $K_{s,t}$ 완전 이분 부분 그래프를 포함하지 않는 최대 간선 수 $Z(m, n, s, t)$를 찾는 자란키비치 문제를 다룬다. 저자는 특히 $s=t=3$ (즉, $K_{3,3}$을 회피하는 경우)인 중간 규모의 유한 파라미터에 집중한다. 점근적 이론은 잘 발달되어 있으나, 특정 유한 차원에 대한 정확한 값은 극심한 대칭성과 증명 인증의 높은 비용으로 인해 여전히 어려운 과제로 남아 있다. 본 논문은 이전에 미해결되었거나 부분적으로 해결된 값들의 "유한 프런티어(finite frontier)"를 목표로 하며, 여기에는 스트립 $Z(12, n, 3, 3)$ ($18 \le n \le 22$), 특정 사례 $Z(13, 22, 3, 3)$, 그리고 $13 \times 18$ 및 $16 \times 17$ 주변의 인접한 값들이 포함된다.

방법론
본 연구는 컴퓨터 보조 방식이지만, 단순히 혼합 정수 선형 계획법(MILP) 솔버가 반환하는 "불가능(infeasible)"이나 명시적인 증거(witness) 없는 SAT 솔버에 의존하는 방식과는 구별되는 엄격한 증명서 기반(certificate-based) 방식을 채택한다. 검증은 Python의 Fraction 및 표준 라이브러리를 사용하는 정밀 정수 및 유리수 산술에 의존하며, 부동 소수점 최적화는 오직 증명서의 초기 발견 단계에서만 사용된다.

방법론은 다층적 축소 전략을 사용한다:

1. 전역 완화 및 차수 프로필(Global Relaxation and Degree Profiles): $13 \times 22$ 사례의 경우, 저자는 가상의 138개 간선을 가진 행렬을 가정한다. 열 차수(column degrees)와 관련된 페널티 함수 $p(d) = \binom{d}{3} - 15d + 70$을 분석함으로써, 탐색 공간을 모든 가능한 행렬에서 83개의 구별된 차수 프로필(열 차수의 히스토그램)로 축소한다.
2. 파르카스 증명서(Farkas Certificates): 83개 프로필 중 77개에 대해, 저자는 정확한 유리수 파르카스 증명서를 구성한다. 이 증명서들은 $K_{3,3}$-free 조건(구체적으로, 모든 행의 3개 원소 조합이 최대 2개의 열에만 나타나야 함)에 의해 부과된 선형 제약 조건이 해당 프로필에 대해 어떠한 비음수 정수 해도 만족할 수 없음을 보여줌으로써 불가능성을 증명한다.
3. 표식 행 및 잔여물 열거(Marked-Row and Leave Enumeration): 나머지 6개의 프로플은 더 세밀한 기법을 사용하여 제외된다. 저자는 "표식 행(marked row)"을 고정하고 이를 삭제한 후, 남은 12개 지점 상의 "잔여 다중 그래프(leave multigraph)"를 분석한다. 여기에는 다음이 포함된다:
   • 합동식 논증(Congruence Arguments): 행 결핍(row deficits)에 대한 모듈로 산술을 사용하여 특정 구성(예: 프로필 6187391)을 배제한다.
   • 그람 행렬 제약(Gram Matrix Constraints): 잔여 블록의 인시던스 행렬(incidence matrix)의 계수(rank)와 행렬식 조건을 확인한다.
   • 정밀 열거(Exact Enumeration): 잔여 블록 설계를 전수 열거하고, 남은 인수 분해 시스템에 정수 스케일링된 파르카스 증명서를 적용한다.
4. 삭제 정리 및 증거(Deletion Lemmas and Witnesses): $12 \times n$ 스트립 및 프런티어 폐쇄를 위해, 저자는 "삭제 정리"( $Z(m, n)$과 $Z(m, n-1)$의 관계)를 명시적 구성적 증거(하한을 달성하는 행렬)와 결합하여 정확한 등식을 확립한다.

주요 기여 및 결과
본 논문은 다음의 정확한 값과 경계에 대한 결합된 증명서 기반 증명을 제공한다:

• $12 \times n$ 스트립: $Z(12, n, 3, 3) = 6n$ ($18 \le n \le 22$)임을 증명한다. 이는 $Z(12, 18, 3, 3) = 108$에 대한 정확한 증명서와 $n=19, 20, 21, 22$에 대한 명시적 증거로 뒷받침되는 순차적 삭제 논증을 통해 확립된다.
• $13 \times 22$ 사례: $Z(13, 22, 3, 3) = 137$임을 증명한다. 상한인 138은 위에서 설명한 전수 프로필 분석을 통해 제거된다. 하한인 137은 명시적 구성(137개의 1과 $K_{3,3}$이 없는 $13 \times 22$ 이진 행렬)을 통해 확인된다.
• 프런티어 폐쇄(Frontier Closure): 다음의 네 가지 인접 셀에 대한 정확한 값을 확립한다:
  • $Z(13, 18, 3, 3) = 116$
  • $Z(14, 17, 3, 3) = 118$
  • $Z(14, 18, 3, 3) = 124$
  • $Z(15, 17, 3, 3) = 126$
  • $Z(15, 18, 3, 3) = 132$
• $16 \times 17$ 구간: $132 \le Z(16, 17, 3, 3) \le 133$의 범위를 보고한다. 하한은 새로운 132-간선 증거에 의해 뒷받침되며, 상한인 133은 기존 문헌(Collins et al.)에서 가져온 것이다. 저자는 이 특정 셀에 대한 정확한 값은 본 연구 내에서 결정되지 않았음을 명시한다.

의의 및 주장
저자는 본 연구가 이러한 특정 자란키비치 값들에 대해 완전하고 재현 가능하며 증명서 기반인 증명을 제공한다고 주장한다. 본 연구의 의의는 발견 단계(부동 소수점 휴리스틱이 사용될 수 있는 단계)와 검증 단계(오직 정확한 산술만을 사용하는 단계)를 엄격히 분리했다는 점에 있다.

• 재현 가능성: 본 논문은 모든 570만 개의 정확한 비음수성 체크(차수 프로필 재생, 파르카스 증명서 재실행, 잔여 블록 설계의 전수 열거 포함)를 다시 실행하는 "단일 명령 검증 게이트(one-command verification gate)"를 포함한다.
• 겸손함: 저자는 이 결과들이 "독립적인 재현과 동료 검토를 기다리는 새로운 컴퓨터 보조 증명"으로 간야되어야 한다고 명시적으로 밝힌다. 본 논문은 일반적인 자란키비치 문제를 해결하거나 보편적인 알고리즘을 제공한다고 주장하지 않는다. 대신, 거친 전역 완화를 사용하여 대부분의 사례를 제거하고, 몇 안 되는 "어려운" 잔여 프로필에 대해서만 정밀하고 계산 집약적인 열거를 수행하는 유한 극한 문제의 역할 분담을 보여준다.
• 선행 연구: 저자는 $13 \times 22$에 대한 137-간선 구성이 이전에 보고되었으나, 정확한 상한은 새로운 기여임을 언급한다. 마찬가지로, $12 \times n$ 스트립의 특정 값들($n=18$에서 $21$)과 프런티어 폐쇄 값들도 논문 작성일(2026년 8월) 기준 색인된 문헌에서 발견되지 않은 새로운 정확한 결과로 보고된다.

본 논문은 결론적으로, 검증되지 않은 DRAT 주장, SAT 타임아웃, 또는 부동 소수점 솔버의 상태가 정리의 전제로 사용되지 않았음을 강조하며, 수학적 주장이 전적으로 명시적인 유한 데이터와 정확한 산술에 기초하고 있음을 보장한다.