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

The α-representation for Tait coloring and sums over spanning trees

基本信息

论文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$ 向量对应的权重和的三倍。

研究背景与动机

核心问题: 本文旨在建立最大平面图Tait着色数的新代数表示，将其与生成树权重和联系起来。
历史背景: 研究起源于Kontsevich在1997年提出的猜想，该猜想涉及有限域上生成树权重和的非零值数量。虽然原猜想已被反驳，但启发了新的研究方向。
重要性:
- Tait着色与四色定理等价，是图论中的基本问题
- 连接了组合图论、代数几何和量子场论中的技术
- 为理解平面图着色提供了新的代数视角
现有方法局限性: 传统的Tait着色计数方法主要基于组合技术，缺乏与其他数学分支的深层联系。本文通过α-表示技术，建立了与量子场论中Feynman振幅计算的类比。

核心贡献

建立了新的代数表示: 证明了Tait着色数可以表示为特定权重函数的和，该权重函数涉及勒让德符号和生成树权重和。
引入了α-表示技术: 将量子场论中的α-表示技术适配到有限域 $\mathbb{F}_3$ 上，为组合问题提供了新的分析工具。
连接了多个数学领域: 将图论中的着色问题与数论中的Gauss和、代数几何中的二次型理论联系起来。
提供了具体的计算公式: 给出了通过生成树权重和计算Tait着色数的显式公式，并通过 $K_4$ 的例子验证了理论结果。

方法详解

任务定义

输入: 最大平面图 $G$ （即每个面都是三角形的平面图）输出: $G$ 的Tait着色数 $\text{Tai}(G)$ 约束: Tait着色要求相邻边使用不同颜色，且每个三角形面的三条边使用三种不同颜色

核心数学框架

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: 仅一个面异号（8种情况）
- 三条边权重为0，一条边权重非零
- 权重相互抵消，不贡献最终和
情况3: 两个面为+1，两个面为-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$