Holographic Approximation: Difference between revisions
imported>Etone |
imported>Etone No edit summary |
||
| Line 2: | Line 2: | ||
== Recursion on tree == | == Recursion on tree == | ||
<math> | |||
Z_b(G,e)=\#\{\sigma_G\mid \sigma_G(e)=b\}=\sum_{\sigma\in[q]^G\atop\sigma(e)=b}wt(\sigma) | |||
</math> | |||
<math> | <math> | ||
\begin{align} | \begin{align} | ||
Z_0(T,e) | |||
&= | &= | ||
\sum_{\ell=0}^k\sum_{S\in{[k]\choose \ell}}f_\ell \prod_{i\in S} | \sum_{\ell=0}^k\sum_{S\in{[k]\choose \ell}}f_\ell \prod_{i\in S}Z_{1}(T_i,e_i)\prod_{i\in [k]\setminus S}Z_0(T_i,e_i)\\ | ||
Z_1(T,e) | |||
&= | &= | ||
\sum_{\ell=0}^k\sum_{S\in{[k]\choose \ell}}f_{\ell+1} \prod_{i\in S} | \sum_{\ell=0}^k\sum_{S\in{[k]\choose \ell}}f_{\ell+1} \prod_{i\in S}Z_1(T_i,e_i)\prod_{i\in [k]\setminus S}Z_0(T_i,e_i) | ||
\end{align} | \end{align} | ||
</math> | </math> | ||
| Line 17: | Line 21: | ||
R_T | R_T | ||
&= | &= | ||
\frac{ | \frac{Z_0(T,e)}{Z_1(T,e)}\\ | ||
&= | &= | ||
\frac{ | \frac{ | ||
\sum_{\ell=0}^k\sum_{S\in{[k]\choose \ell}}f_\ell \prod_{i\in S} | \sum_{\ell=0}^k\sum_{S\in{[k]\choose \ell}}f_\ell \prod_{i\in S}Z_{1}(T_i,e_i)\prod_{i\in [k]\setminus S}Z_0(T_i,e_i) | ||
}{ | }{ | ||
\sum_{\ell=0}^k\sum_{S\in{[k]\choose \ell}}f_{\ell+1} \prod_{i\in S} | \sum_{\ell=0}^k\sum_{S\in{[k]\choose \ell}}f_{\ell+1} \prod_{i\in S}Z_1(T_i,e_i)\prod_{i\in [k]\setminus S}Z_0(T_i,e_i) | ||
} | } | ||
\end{align} | \end{align} | ||
</math> | </math> | ||
Revision as of 18:50, 18 April 2012
Holant Problem
Recursion on tree
[math]\displaystyle{ Z_b(G,e)=\#\{\sigma_G\mid \sigma_G(e)=b\}=\sum_{\sigma\in[q]^G\atop\sigma(e)=b}wt(\sigma) }[/math]
[math]\displaystyle{ \begin{align} Z_0(T,e) &= \sum_{\ell=0}^k\sum_{S\in{[k]\choose \ell}}f_\ell \prod_{i\in S}Z_{1}(T_i,e_i)\prod_{i\in [k]\setminus S}Z_0(T_i,e_i)\\ Z_1(T,e) &= \sum_{\ell=0}^k\sum_{S\in{[k]\choose \ell}}f_{\ell+1} \prod_{i\in S}Z_1(T_i,e_i)\prod_{i\in [k]\setminus S}Z_0(T_i,e_i) \end{align} }[/math]
[math]\displaystyle{ \begin{align} R_T &= \frac{Z_0(T,e)}{Z_1(T,e)}\\ &= \frac{ \sum_{\ell=0}^k\sum_{S\in{[k]\choose \ell}}f_\ell \prod_{i\in S}Z_{1}(T_i,e_i)\prod_{i\in [k]\setminus S}Z_0(T_i,e_i) }{ \sum_{\ell=0}^k\sum_{S\in{[k]\choose \ell}}f_{\ell+1} \prod_{i\in S}Z_1(T_i,e_i)\prod_{i\in [k]\setminus S}Z_0(T_i,e_i) } \end{align} }[/math]