|
|
本帖最后由 Czhang271828 于 2023-5-24 14:49 编辑 扒一篇以前写的文章, 讲讲一般 $m\times n$ 格点的 dimer covering 问题:
二聚覆盖问题主要研究二聚体(dimer)在晶体状面(crystalline substrate)上的完美覆盖数. 统计物理中, 该指标可反应系统的熵, 自由能等统计量. 例如, 设$Z_{m,n}$为采用二聚方体覆盖$m\times n$棋盘面的完美覆盖总数, 则依照自由能之定义, 极限
$$
-\lim_{m,n\to \infty}\dfrac{1}{mn}\log Z_{m,n}
$$
存在.
不妨设 $m$ 为偶数, 下研究 $m\times n$ 棋盘上的二聚覆盖总数. 不失一般性地, 可转化问题为 $m\times n$ 格点图的 perfect matching 计数. 下图为 $4\times6$ 棋盘图(记作 $G_{4,6}$ )对应的二聚覆盖图.
记 $E'\subset E(G_{4,6})$ 为某一二聚覆盖, 则该覆盖的 Boltzman 权为 $w(E'):=\prod_{e\subset E'}w(e)$. 其中 $w(e)$ 为边 $e$ 的权重. 定义覆盖总权为 $w(G)=\sum_{E'\text{ covers }G} w(E')$. 若能够$w(E')$恒为$1$, 则$w(G)$为图$G$的二聚覆盖总数.
Step I: 定义 Kasteleyn 矩阵, 选择图的定向.沿着所有平行于对角线的方向将点黑白染色( $G_{m,n}$ 为二分图), 则白点数量为 $N:=\dfrac{nm}{2}$ . 记 $\{W_1,W_2,\ldots, W_N\}$ 为白点集, $\{B_1,B_2,\ldots,B_N\}$ 为黑点集. 对每一个定向, 都可如下定义 Kasteleyn 矩阵 $K_{N\times N}$:
$$
k_{ij}=\left\{\begin{align*}
&w(W_i,B_j)&&W_i\to B_j,\\
-&w(W_i,B_j)&&W_i\leftarrow B_j,\\
&0&&\text{else.}
\end{align*}\right.
$$
注意到
$$
\det K=\sum_{\sigma\in S_N}\mathrm{sgn}(\sigma)\prod_{i=1}^Nk_{i,\sigma(i)}.
$$
以及 $E'$ 为二聚覆盖时, 存在 $\sigma$ 使得 $E'=\{(W_i,B_{\sigma(i)})\}$. 从而只需找到合适的定向使得 $w(G)=|\det K|$, 即对任意覆盖 $E'_1$ 与 $E'_2$, 对应 $\sigma_1$ 与 $\sigma_2$, 有
$$
\mathrm{sgn}(\sigma_1)\prod_{i=1}^Nk_{i,\sigma_1(i)}=\mathrm{sgn}(\sigma_2)\prod_{i=1}^Nk_{i,\sigma_2(i)}.
$$
为计算之便, 记所有边无权(推广解时, 会将横边与纵边赋予不同的权重). 考虑如图所示的定向
以及任意两组二聚覆盖
下证明 $\mathrm{sgn}(\sigma_1\cdot \sigma_2)\prod_{i=1}^Nk_{i,\sigma_1(i)}k_{i,\sigma_2(i)}\equiv 1$.
注意到 ①: 对 $E_1'$ 与 $E_2'$ 的中相交的二重边, 显然 $k$ 之积为 $1$, 同时两置换在此二重边之局上同号.
注意到 ②: 对红蓝交错的长为 $2l$ 的圈而言, $\sigma_1^{-1}\circ\sigma_2$ 实则一次轮换, 从而 $\mathrm{sgn}(\sigma_1\cdot\sigma_2)=(-1)^{l+1}$. 注意到 $C_4$ 中, 两种染色中对应的 $B\to W$ 之边数量改变了 $\pm 1$. 从而归纳知长为 $2l$ 的圈中 $B\to W$ 之数量改变了 $
\sum_i^{l-1}\pm 1\equiv l-1\mod 2$. 故在长为 $2l$ 的圈中(不妨记顶点为 $1,\ldots,2l$)有
$$
\mathrm{sgn}(\sigma_1\cdot \sigma_2)\prod_{i=1}^{2l}k_{i,\sigma_1(i)}k_{i,\sigma_2(i)}=(-1)^{l+1}(-1)^{l-1}\equiv 1.
$$
从而该定向合理.
Step II: 计算 $\det K$.
不妨设 $G_{m,n}$ 中的点具有形式 $(x,y)$, 其中 $1\leq x\leq m$ 且 $1\leq y\leq n$, 则
$$
K_{(x_1,y_1),(x_2,y_2)}=(\delta_{x'}^{x+1}-\delta_{x'}^{x-1})\delta_y^{y'}+(-1)^x\delta_x^{x'}(\delta_{y'}^{y+1}-\delta_{y'}^{y-1}).
$$
注意到 $K$ 为"半边矩阵", 即 $K$ 行数为 $G_{m,n}$ 总顶点数之一半, 可补全 $K$ 为 $A(G_{m,n})$. 记 $Q_{m\times m}=(-1)^x(\delta_{x'}^{x+1}-\delta_{x'}^{x-1})$, $R_{n\times n}=(\delta_{y'}^{y+1}-\delta_{y'}^{y-1})$, $S_{m\times m}=\mathrm{diag}((-1)^x)$. 则
$$
\tilde K:=(S\otimes \mathbf 1_n)(Q\otimes \mathbf 1_n+\mathbf 1_m\otimes R).
$$
对于边加权之情形(如横向边权为 $z_1$, 纵向边权为 $z_2$), 有
$$
\tilde K:=(S\otimes \mathbf 1_n)(z_1Q\otimes \mathbf 1_n+z_2\mathbf 1_m\otimes R).
$$
对三对角矩阵
$$
R=\begin{pmatrix}0&1\\-1&0&\ddots\\&\ddots&\ddots&1\\&&-1&0\end{pmatrix}
$$
数学归纳法知, $R$ 的递推式为 Чебышёв 多项式, 故特征值为 $\{2i\cos(\pi k/(n+1))\}_{k=1}^n$. 同理, $Q$ 的特征值为 $\{2\cos(\pi k/(m+1))\}_{k=1}^m$. 故
$$
\begin{align*}
|\det K|^2&=|\det \tilde K|\\
&=\sqrt{|\det (S\otimes I_n)|\cdot|\det (z_1Q\otimes I_n+z_2I_m\otimes R)|}\\
&=\sqrt{\prod _{k=1}^m\prod _{l=1}^n\left(z_1\cdot 2i\cos\dfrac{\pi k}{n+1}+z_2\cdot\cos\dfrac{\pi l}{m+1}\right)}\\
&=2^{mn}\prod_{l=1}^n\prod_{k=1}^{m/2}\left[(z_1\cos\dfrac{\pi k}{m+1})^2+(z_2\cos\dfrac{\pi l}{n+1})^2\right]\\
\end{align*}
$$
随后, 我们自然关心 $Z_{m,n}(z_1,z_2)$ 与 $m,n$ 的关系, 尤其是渐进性态.
据物理学背景, 平均自由能
$$
f(z_1,z_2):=-\min_{m,n\to\infty}\dfrac{1}{mn}\log Z_{mn}(z_1,z_2)
$$
应为某一常数, 下求出该常数: 据二重黎曼积分之定义, 有
$$
\begin{align*}
f(z_1,z_2)&=-\lim_{m,n\to\infty}\dfrac{\log 2^{mn/2}}{mn}\log\prod_{p=1}^n\prod_{q=1}^{m/2}\sqrt{(z_1\cos\dfrac{\pi q}{m+1})^2+(z_2\cos\dfrac{\pi p}{n+1})^2}\\
&=-\dfrac{1}{\pi^2}\int_0^{\pi/2}\mathrm d\theta\int_0^{\pi/2}\log[4(z_1^2\cos^2\theta+z_2^2\cos^2\phi)]\mathrm d\phi\\
&=-\dfrac{1}{\pi}\int_0^{\pi/2}\mathrm d\theta\left[\dfrac{1}{2}\log^2(2z_2\cos\theta)+\dfrac{1}{\pi}\int_0^{\pi/2}\log\left(1+\dfrac{\cos^2\phi}{(\frac{z_2}{z_1})^2\cos^2\theta}\right)\mathrm d\phi\right]\\
&=-\dfrac{1}{\pi}\int_0^{\pi/2}\mathrm d\theta\left[\log(2z_2\cos\theta)+\log\dfrac{1+\sqrt{1+\dfrac{z_1^2}{z_2^2\cos^2\theta}}}{2}\right]\\
&=-\dfrac{1}{\pi}\int_0^{\pi/2}\mathrm d\theta(\log z_1+\log(\frac{z_2}{z_1}\cos\theta+\sqrt{1+(\frac{z_2}{z_1})^2\cos^2\theta})\\
&=-\dfrac{1}{2}\log z_1
-\dfrac{1}{\pi}\int_0^{\pi/2}g(\frac{z_2}{z_1}\cos\theta)\mathrm d \theta
\end{align*}
$$
其中
$$
g(x)=\log(x+\sqrt{1+x^2})=\sum_{j=0}^\infty\binom{2j}{j}\dfrac{(-1)^j}{(2j+1)2^{2j}}x^{2j+1}.
$$
故
$$
\begin{align*}
\int_0^{\pi/2}g(\cos\theta)\mathrm d \theta=&\sum_{j=0}^\infty\int_0^{\pi/2}\binom{2j}{j}\dfrac{(-1)^j(z_2/z_1)^{2j+1}}{(2j+1)2^{2j}}\cos^{2j+1}\theta\mathrm d\theta\\
=&\sum_{j=0}^\infty\dfrac{(-1)^j}{(2j+1)^2}(z_2/z_1)^{2j+1}\\
=&\int_0^{z_1/z_1}\dfrac{\arctan t}{t}\mathrm dt\\
\end{align*}
$$
特殊地, 令 $z_1=z_2=1$, 则
$$
f(1,1)=-\dfrac{1}{\pi}\int_0^1\dfrac{\arctan t}{t}\mathrm dt=-\dfrac{G}{\pi}
$$
其中 $G$ 为 Catalan 常数. 一般地, 有
$$
f(z_1,z_2)=\dfrac{1}{2}\log z_1+\dfrac{1}{\pi}\mathrm{Ti_2}(z_2/z_1).
$$
其中 $\displaystyle{\mathrm{Ti_2(z)}:=\sum_{k\geq 1}(-1)^{k-1}\dfrac{x^{2k-1}}{(2k-1)^2}}$.
|
|
kuing
发表于 2016-10-30 17:14
Czhang271828
发表于 2022-2-12 16:11
