Pauling의 차수가 증가하는 정규 그래프에 대한 잔여 엔트로피 추정에 관하여

기본 정보

• 논문 ID: 2509.20671
• 제목: On Pauling's residual entropy estimate for regular graphs with growing degree
• 저자: Mahdieh Hasheminezhad (Yazd University), Mikhail Isaev (UNSW Sydney), Brendan D. McKay (Australian National University), Rui-Ray Zhang
• 분류: math.CO (조합론)
• 발표 시간: 2025년 11월 5일 (arXiv v2)
• 논문 링크: https://arxiv.org/abs/2509.20671

초록

1935년 Pauling은 물 얼음의 이론적 거동을 연구하면서 그래프의 오일러 방향의 개수에 관한 추정을 제시했다. 오일러 방향 개수의 로그를 정점 개수로 나눈 값을 잔여 엔트로피라고 한다. 선행 논문에서 저자들은 차수가 증가하는 정규 그래프 수열의 잔여 엔트로피가 점근적으로 Pauling 추정과 같다고 추측했다. 본 논문은 짧은 폐로(closed walk) 개수의 제약 조건 하에서 이 추측을 증명한다. 이러한 제약 조건은 약한 고유값 조건 하에서 성립하며, 둘레가 증가하는 그래프 수열과 반복 데카르트 곱(예: 초입방체)에 적용된다.

연구 배경 및 동기

1. 연구 문제

본 논문은 그래프의 오일러 방향(Eulerian orientations) 계산 문제를 연구한다. d-정규 그래프 G (d는 짝수)에 대해, 오일러 방향은 각 정점의 입차수가 출차수와 같도록 간선을 방향 지은 것이다. 잔여 엔트로피를 다음과 같이 정의한다: $\rho(G) := \frac{1}{n}\log EO(G)$ 여기서 EO(G)는 오일러 방향의 개수이고, n은 정점의 개수이다.

2. 문제의 중요성

• 물리학적 배경: 잔여 엔트로피는 통계 물리학의 얼음 모형(ice-type models)에서 중요한 의미를 가지며, 물 얼음 결정의 미시 상태 개수와 관련된다
• 수학적 의의: 특정 격자(정사각형 격자, 삼각형 격자, 육각형 얼음 단층)에 대해 잔여 엔트로피의 정확한 값이 알려져 있지만, 일반 그래프의 점근적 거동은 여전히 미해결 문제이다
• 이론적 가치: 조합론, 통계 물리학, 확률론을 연결한다

3. Pauling 추정

Pauling은 1935년에 휴리스틱 추정을 제시했다: 각 간선을 독립적으로 무작위로 방향 지을 때, 정점 i의 입차수가 출차수와 같을 확률을 $2^{-d}\binom{d}{d/2}$라고 가정한다. n개 정점의 사건이 독립이라고 가정하면 다음을 얻는다: $\hat{\rho}(G) = \log\binom{d}{d/2} - \frac{d}{2}\log 2$

Lieb과 Wu는 모든 그래프에 대해 $\rho(G) \geq \hat{\rho}(G)$임을 증명했다.

4. 기존 연구의 한계

• 이전 결과 (Isaev, McKay, Zhang 5)는 좋은 확장 성질을 가지고 $d \geq \log^8 n$인 그래프에만 적용된다
• 무작위 그래프의 결과 (6)는 높은 확률 성질에 의존한다
• Las Vergnas 7의 결과는 둘레가 $\log d$보다 빠르게 증가할 것을 요구한다

5. 연구 동기

추측 1.1: d-정규 그래프 수열 G(n)에 대해, 짝수 $d = d(n) \to \infty$이면 $\rho(G) = \hat{\rho}(G) + o(1)$이다.

본 논문의 목표는 더 약한 조건 하에서 이 추측을 증명하는 것이다.

핵심 기여

1. 주요 정리(정리 2.1): 짧은 폐로 개수 제약 조건 하에서 추측 1.1을 증명한다. 조건은:
   • $\ell_{max} = \omega(\log d)$와 상수 C > 0이 존재한다
   • 모든 $3 \leq \ell \leq \ell_{max}$에 대해: $c_\ell(G) \leq Ce^{-(l+1)}d^{\ell-1}n$
2. 고유값 조건 따름정리(따름정리 2.2): 최대 $nd^{-\omega(1)}$개의 고유값이 $[-d^{1-\delta}, d^{1-\delta}]$ 외부에 있으면 (어떤 상수 δ > 0에 대해), 추측이 성립한다
3. 둘레 조건 따름정리(따름정리 2.3): 둘레 $g \to \infty$인 d-정규 그래프 수열에 대해, 추측이 성립한다 ($d \to \infty$를 요구하지 않음)
4. 데카르트 곱 따름정리(따름정리 2.4): 데카르트 곱 $G_t = H_1^{(t)} \square \cdots \square H_t^{(t)}$에 대해, 차수의 제곱 합이 $\sum_{i=1}^t (h_i^{(t)})^2 = O(d_t^{2-\delta})$를 만족할 때 추측이 성립한다. 특히 초입방체 $Q_d$에 적용된다
5. 기술적 혁신: 문제를 무작위 오일러 분할로 유도된 폐로 개수의 적률 생성 함수 분석으로 변환한다

방법 상세 설명

작업 정의

d-정규 그래프 G (d는 짝수)가 주어졌을 때, 잔여 엔트로피 $\rho(G) = \frac{1}{n}\log EO(G)$를 계산하고 이것이 점근적으로 Pauling 추정 $\hat{\rho}(G)$과 같음을 증명한다.

핵심 방법 프레임워크

1. 오일러 분할 표현

정의: 오일러 분할 P는 그래프의 간선을 여러 폐로로 분할하는 것이다. 각 정점의 간선 쌍 짓기(pairing)는 유일한 오일러 분할을 결정한다.

핵심 공식: $\rho(G) = \hat{\rho}(G) + \frac{1}{n}\log \mathbb{E} 2^{|T(P)|}$ 여기서 P는 균일 무작위 오일러 분할이고, T(P)는 P로 유도된 폐로 집합이다.

동치성: 추측은 $\mathbb{E} 2^{|T(P)|} = e^{o(n)}$을 증명하는 것과 동치이다.

2. 폐로 분해 전략

$k = \lfloor\min\{\ell_{max}/2, \log^2 d\}\rfloor$로 정의하고, 폐로를 다음과 같이 분류한다:

• 긴 폐로 $L_k(P)$: 서로 다른 정점을 k개 이상 포함하는 폐로의 개수
• 짧은 폐로 $S_k(P)$: 서로 다른 정점을 최대 k개 포함하는 폐로의 개수

Hölder 부등식을 사용한다: $\mathbb{E} 2^{|T(P)|} = \mathbb{E} 2^{L_k(P)+S_k(P)} \leq \left(\mathbb{E} 2^{\frac{7}{2}L_k(P)}\right)^{2/7}\left(\mathbb{E} 2^{\frac{7}{5}S_k(P)}\right)^{5/7}$

기술적 요소

3. 긴 폐로 제어 (보조정리 3.4)

핵심 보조정리(보조정리 3.1): 짝수 m과 λ ≥ 0에 대해, $\mathbb{E} e^{\lambda X(m)} \leq (Bm)^{(e^\lambda-1)/2}$ 여기서 $X(m)$은 매개변수 $1/(2j-1)$ (j=1,...,m/2)를 가진 독립 베르누이 무작위 변수의 합이다.

쌍 독립성(보조정리 3.2): 무작위 쌍 짓기에서, 정점 v를 통과하는 서로 다른 폐로의 개수는 분포 X(m)을 따르며, 다른 정점의 쌍 짓기와 독립이다.

적률 생성 함수 경계(보조정리 3.3): 정점 부분집합 U에 대해, $\mathbb{E} e^{\lambda Y(U)} = d^{O(|U|)}$

최종 경계: $|U| = \lfloor n/k\rfloor$인 무작위 부분집합을 선택하고, 확률이 최소 1/2인 $L_k \leq 2Y(U)$를 이용하면: $\mathbb{E} e^{\lambda L_k} \leq (edk)^{O(n/k)} = e^{o(n)}$

4. 짧은 폐로 제어 (보조정리 4.5)

전환 방법(switching method)(정리 4.1)을 사용한다 — 이는 강력한 조합 계산 도구이다.

전환 정의: 오일러 분할 P와 폐로 T가 주어졌을 때, T-전환은 T가 지나가는 각 정점에서 쌍 짓기를 수정한다:

• 정점 v가 T에 의해 t번 방문되고, 간선 쌍 $(e_1,e_1'),\ldots,(e_t,e_t')$에 대응된다
• t개의 추가 간선 쌍 $(e_{t+1},e_{t+1}'),\ldots,(e_{2t},e_{2t}')$을 선택한다
• 새로운 쌍 짓기 $\{e_1,e_{t+1}\},\ldots,\{e_t,e_{2t}\}$와 $\{e_1',e_{t+1}'\},\ldots,\{e_t',e_{2t}'\}$로 대체한다

전환 그래프: 유향 다중 그래프 Γ를 구성한다:

• 정점: $\mathbf{m} = (m_3,\ldots,m_L)$, 정확히 길이 ℓ인 짧은 폐로 $m_\ell$개를 가진 오일러 분할 클래스를 나타낸다
• 간선: 색상이 ℓ인 유향 간선 $(\mathbf{m},\mathbf{m}')$은 C(m)에서 C(m')로의 ℓ-전환이 존재함을 나타낸다

핵심 추정(보조정리 4.3):

• P ∈ C(m)에서 출발하는 ℓ-전환의 개수: $\geq \|\mathbf{m}\|_1(d-2L)^\ell/L$
• P' ∈ C(m')에 도달하는 ℓ-전환의 개수: $\leq c_{k,\ell}$

가중치 함수: $\hat{\alpha}(e) \leq \frac{2c_{k,\ell}L^2}{d^\ell m}$

정리 4.1 적용: 다음을 정의한다 $M_0 := 2CnL^2/d, \quad Y = \bigcup_{m>M} C_m, \quad Z = \bigcup_{m\leq M_0} C_m$

모든 $\|\mathbf{m}\|_1 > M_0$인 간선에 대해 $\hat{\alpha}(e) < 1/2$이므로: $|Y| \leq 2e^{-M+M_0}|Z|$

꼬리 확률 경계: $\mathbb{P}(S_k(P) > M) \leq 2e^{-M+M_0}$

적률 경계: 적분 표현을 통해, $\mathbb{E} e^{\lambda S_k(P)} \leq e^{\lambda M_0} + \frac{2e^{\lambda M_0}}{1-\lambda} = e^{o(n)}$ 여기서 $\lambda = \frac{7}{5}\log 2 \approx 0.97 < 1$이다.

기술적 혁신점

1. 분해 전략의 정교함: k 값의 선택을 통해 긴 폐로와 짧은 폐로의 기여도를 균형 있게 조정하고, Hölder 부등식의 지수 선택 (7/2와 7/5)은 정교하게 설계되었다
2. 전환 방법의 혁신적 적용:
   • 오일러 분할의 계산 문제를 유향 그래프의 흐름 문제로 변환한다
   • 짧은 폐로 개수 가정을 이용하여 전환 가중치를 제어한다
   • 정리 4.1을 통해 꼬리 확률의 지수 감소를 얻는다
3. 조건의 약화:
   • $d \geq \log^8 n$에서 $d \to \infty$로 약화된다
   • 강한 확장 성질에서 짧은 폐로 개수 제약으로 약화된다
   • 고유값 조건은 $nd^{-\omega(1)}$개의 이상값만 필요하다
4. 통일된 프레임워크: 둘레 증가, 고유값 제약, 데카르트 곱 등 다양한 경우를 동시에 처리한다

실험 설정

이론 증명의 특성

본 논문은 순수 이론 논문으로, 수치 실험이나 계산 실험을 포함하지 않는다. 모든 결과는 엄격한 수학적 증명이다.

응용 예시

논문은 다음 그래프 클래스에서 추측이 성립함을 따름정리를 통해 검증한다:

1. 둘레 증가 그래프(따름정리 2.3)
2. 스펙트럼 제약 그래프(따름정리 2.2)
3. 초입방체 $Q_d$ (d는 짝수)
4. 순환 데카르트 곱: 국소적으로 고차원 정사각형 격자로 수렴한다
5. 무작위 정규 그래프 (참고문헌 6의 결과 인용)

실험 결과

주요 결과

정리 2.1의 조건 검증:

1. 둘레 g → ∞인 그래프:
   • 길이 ℓ < g인 폐로의 개수는 0이므로 조건을 자동으로 만족한다
   • d = O(1)이어도 성립한다
2. 고유값 제약 그래프:
   • 폐로 개수 $\leq \sum_i \lambda_i^\ell$
   • 최대 $nd^{-f(n)}$개의 고유값이 $[-d^{1-\delta}, d^{1-\delta}]$ 외부에 있으면
   • $\ell_{max} = \frac{1}{2}f(n)\log d$로 선택하면 조건이 만족된다
3. 데카르트 곱:
   • Hoeffding 부등식을 이용하여 고유값 분포를 제어한다
   • $\sum_i (h_i^{(t)})^2 = O(d_t^{2-\delta})$인 경우 조건이 만족된다
   • 초입방체: $h_i = 1$이므로 $\sum h_i^2 = t = o(d_t^2)$를 만족한다

기술적 결과

긴 폐로 경계(보조정리 3.4): $\mathbb{E} e^{\lambda L_k(P)} = e^{o(n)}, \quad \forall \lambda \geq 0, \, k \gg \log d$

짧은 폐로 경계(보조정리 4.5): $\mathbb{E} 2^{\frac{7}{5}S_k(P)} = e^{o(n)}$

핵심 부등식 체인