2025-11-18T06:10:11.875624

The $Î±$-representation for Tait coloring and sums over spanning trees

Kalimullin, Lerner

Consider a connected pseudograph $H$ such that each edge is associated with weight $x_e$, $x_e \in \mathbb{F}_3$; $\mathcal{T}(H)$ is the set of spanning trees of graph $H$. Assume that $s(H;{\mathbf x})=\sum_{T\in\mathcal{T}(H)} \prod_{e\in E(T)} x_e$. Let $G$ be a maximal planar graph (arbitrary planar triangulation) such that each face $F$ is assigned the value $Î±(F)=\pm 1 \in \mathbb{F}_3$. Then we can associate each edge with $x_e=Î±(F'_e)+Î±(F''_e)$, where $F'_e$ and $F''_e$ are the faces containing edge $e$. Let us define the value $w_G({\mathbf x})$ as $\left(\frac{s(G/W^*({\mathbf x});{\mathbf x})}3\right)/(-3)^{\left(|V(G/W^*({\mathbf x}))| - 1\right)/2}$; here $\left(\frac{x}3\right)$ is the Legendre symbol, $G/W$ is the graph with the contracted set of vertices $W$, while $W^*({\mathbf x})$ is a set of vertices $W$, $W \subseteq V(G)$, with minimal cardinality such that $s(G/W;{\mathbf x})$ differs from zero. In the following, we prove that the number of Tait colorings for graph $G$ equals the tripled sum $w_G({\mathbf x}(Î±))$ with respect to all possible vectors $Î±\in \{-1, 1\}^{\mathcal F(G)}$ such that $G/W^*({\mathbf x}(Î±))$ has an odd number of vertices, where $\mathcal F(G)$ is the set of faces of graph $G$. Keywords: maximal planar graph, Tait coloring, Laplace-Kirchhoff matrix, spanning tree.

academic

Tait着色のα-表現と全域木の和

基本情報

論文ID: 2510.10213
タイトル: The α-representation for Tait coloring and sums over spanning trees
著者: Ilyas Kalimullin, Eduard Lerner
分類: math.CO（組合数学）、math.NT（数論）
投稿日時: 2025年10月11日にarXivに投稿
論文リンク: https://arxiv.org/abs/2510.10213

摘要

本論文は、最大平面図のTait着色数と全域木の重み付き和の間の代数的関係を研究している。著者は連結疑似グラフ $H$ を考察し、各辺に重み $x_e \in \mathbb{F}_3$ を関連付け、 $s(H;\mathbf{x})=\sum_{T\in\mathcal{T}(H)} \prod_{e\in E(T)} x_e$ を全域木の重み付き和として定義する。最大平面図 $G$ に対して、各面 $F$ に $\alpha(F)=\pm 1 \in \mathbb{F}_3$ を割り当て、辺の重みを $x_e=\alpha(F'_e)+\alpha(F''_e)$ と定義する。重み関数 $w_G(\mathbf{x})$ を導入し、ルジャンドル記号と頂点縮約技術を利用することで、Tait着色数が特定の条件を満たすすべての $\alpha$ ベクトルに対応する重みの和の3倍に等しいことを証明した。

研究背景と動機

中心的問題: 本論文は、最大平面図のTait着色数の新しい代数的表現を確立し、全域木の重み付き和との関連性を示すことを目指している。
歴史的背景: 研究は1997年にKontsevichが提唱した予想に由来し、有限体上の全域木の重み付き和の非零値の数量に関わっている。元の予想は反駁されたが、新しい研究方向を啓発した。
重要性:
- Tait着色は四色定理と同値であり、グラフ理論の基本的問題である
- 組合グラフ理論、代数幾何、量子場論の技術を結合している
- 平面図の着色理解に新しい代数的視点を提供する
既存方法の限界: 従来のTait着色計数方法は主に組合技術に基づいており、他の数学分野との深い関連性が不足していた。本論文はα-表現技術を通じて、量子場論のFeynman振幅計算との類似性を確立している。

核心的貢献

新しい代数的表現の確立: Tait着色数がルジャンドル記号と全域木の重み付き和を含む特定の重み関数の和として表現できることを証明した。
α-表現技術の導入: 量子場論のα-表現技術を有限体 $\mathbb{F}_3$ に適応させ、組合問題に新しい分析ツールを提供した。
複数の数学分野の結合: グラフ理論の着色問題を数論のGauss和および代数幾何の二次形式理論と関連付けた。
具体的な計算公式の提供: 全域木の重み付き和を通じてTait着色数を計算するための明示的な公式を与え、 $K_4$ の例を通じて理論結果を検証した。

方法の詳細説明

タスク定義

入力: 最大平面図 $G$ （すなわち、すべての面が三角形である平面図）出力: $G$ のTait着色数 $\text{Tai}(G)$ 制約: Tait着色は隣接する辺が異なる色を使用し、各三角形面の3本の辺が3つの異なる色を使用することを要求する

中心的数学フレームワーク

1. 全域木の重み付き和の定義

連結疑似グラフ $H$ と辺の重み $\mathbf{x} \in \mathbb{F}_3^{E(H)}$ に対して： $s(H;\mathbf{x}) = \sum_{T\in\mathcal{T}(H)} \prod_{e\in E(T)} x_e$

2. 重み関数の定義

$w_G(\mathbf{x}) = \left(\frac{s(G/W^*(\mathbf{x});\mathbf{x})}{3}\right)/(-3)^{(|V(G/W^*(\mathbf{x}))|-1)/2}$

ここで：

$\left(\frac{x}{3}\right)$ はルジャンドル記号
$W^*(\mathbf{x})$ は $s(G/W;\mathbf{x}) \neq 0$ を満たす最小基数の頂点集合
$G/W$ は頂点集合 $W$ を縮約した後のグラフ

Gauss和の応用: 多次元Gauss和 $\text{Gau}(C) = \sum_{y\in\mathbb{F}_3^n} \exp(2\pi iy^TCy/3)$ を利用して二次形式を処理する。
Heawood定理の代数化: HeawoodによるTait着色の組合的特性化を線形方程式系の解の計数問題に変換する。
Fourier変換技術: 有限体上のFourier変換を使用し、特に恒等式を活用する： $\sum_{y\in\mathbb{F}_3^*} \exp(2\pi iky/3) = 3\delta(k) - 1$
Laplace-Kirchhoff行列との関連性: 重み関数とグラフのLaplace-Kirchhoff行列の主小行列式の関係を確立する。

実験設定

検証ケース：完全グラフ $K_4$

著者は $K_4$ の詳細な分析を通じて理論結果を検証した：

データ特性:

4個の頂点、6本の辺、4個の三角形面
16個の可能な $\alpha$ ベクトル

分類分析:

ケース1: すべての面が同じ符号（2つのケース）
- すべての辺に対して $x_e = -1$
- $s(K_4;\mathbf{x}(\alpha)) = -16 = -1$
- 頂点数が偶数であり、最終的な和に寄与しない
ケース2: 1つの面のみが異なる符号（8つのケース）
- 3本の辺の重みが0、1本の辺の重みが非零
- 重みが相互に相殺され、最終的な和に寄与しない
ケース3: 2つの面が+1、2つの面が-1（6つのケース）
- $s(K_4;\mathbf{x}(\alpha)) = 0$ 、頂点縮約が必要
- $w_{K_4}(\mathbf{x}(\alpha)) = 1/3$
- 最終結果： $\text{Tai}_0(K_4) = 6 \times \frac{1}{3} = 2$