Rooted connected polymer sums obey the tree majorant

Fix $n\ge 2$ and a tuple $({\gamma }_1,\dots ,{\gamma }_n)$, and let $H$ be the simple graph on $[n]$ whose edge $\{i,j\}$ is present exactly when ${\gamma }_i\sim {\gamma }_j$. By [F1], $U_n={\sum }_{G\subseteq H,G\text{ connected}}(-1{)}^{\mathrm{\mid }E(G)\mathrm{\mid }}$. Here the complete graph on $[n]$ has edge set $\left(\genfrac{}{}{0px}{}{[n]}{2}\right)$, and $G\subseteq H$ means that $G$ has the same vertex set and $E(G)\subseteq E(H)$. Represent each edge $\{i,j\}$ with $i<j$ by $(i,j)$ and order these pairs lexicographically, first by $i$ and then by $j$; list the edges as $e_1{<}_{\mathrm{l}\mathrm{e}\mathrm{x}}\cdots {<}_{\mathrm{l}\mathrm{e}\mathrm{x}}{e}_m$ and assign rank $\rho (e_k)=k\cdot 1_{\mathbb{R}}$. For a tree $T$, its rank sum is ${\sum }_{e\in E(T)}\rho (e)$. By [F8], each connected graph $G$ has a spanning tree; by [F9], its spanning trees form a finite nonempty set, so their finite real rank sums have a minimum. A tree has a unique path between any two vertices: connectedness gives a path, and two distinct paths would contain a cycle between their first divergence and next common vertex, contradicting acyclicity. Here is the cut and exchange argument used below. Let $f=\{u,v\}$ be an edge of a tree $T$. There is no $u$-$v$ path in $T-f$, since such a path together with $f$ would be a cycle in $T$. For any vertex $w$, the unique $T$-path from $u$ to $w$ either avoids $f$, or crosses $f$ from $u$ to $v$ and then has a suffix from $v$ to $w$ avoiding $f$. Thus every vertex is reachable from $u$ or from $v$ in $T-f$, but not both: reachability from both would concatenate to a $u$-$v$ walk avoiding $f$, and deleting repeated-vertex portions of a finite walk gives a path, contradicting the preceding observation. Vertices reachable from the same endpoint are joined by concatenating their endpoint paths and deleting repetitions. Hence $T-f$ has exactly two connected components, with vertex sets $C_u,C_v$, and no remaining tree edge crosses this partition; call it the cut of $f$. If $e=\{x,y\}\mathrm{\notin }E(T)$ and $f$ lies on its unique $T$-path, then $x,y$ lie in opposite components, for otherwise a path in $T-f$ would contradict uniqueness of the $T$-path. Adding $e$ to $T-f$ joins the two components, so $T-f+e$ is connected. It is acyclic: a cycle would have to use $e$ since $T-f$ is acyclic, and removing $e$ from that cycle would give a path in $T-f$ between opposite components. Thus $T-f+e$ is a spanning tree on the same vertex set. Every path from one side of any such cut to the other has a crossing edge, by considering the first vertex at which its finite vertex list changes sides. The minimum-rank-sum spanning tree is unique: if distinct minimizing trees $T,S$ existed, take the least-ranked edge $e$ in their symmetric difference and, after swapping their names if needed, take $e\in T\setminus S$. Deleting $e$ from $T$ gives a cut crossed by the $S$-path between the endpoints of $e$; a crossing edge $f$ on that path lies in $S\setminus T$, and replacing $f$ by the earlier edge $e$ lowers the rank sum of $S$ by [F10], a contradiction. For a tree $T$, let $A(T)\subseteq \left(\genfrac{}{}{0px}{}{[n]}{2}\right)\setminus E(T)$ consist of the edges later than every edge on their unique $T$-path. If $G$ contains $T$ and a non-tree edge $e$ is earlier than a path edge $f$, then $T-f+e$ is a spanning tree of lower rank sum by [F10], so $T$ is not minimum. Conversely, if every non-tree edge of $G$ is later than every edge on its $T$-path, then for each $f\in T$ every other edge of $G$ crossing the cut made by deleting $f$ is later than $f$. Choose a minimum-rank-sum spanning tree $S$ of $G$, which exists by [F8]–[F9]. If $S$ omitted $f$, the $S$-path between the endpoints of $f$ crosses this cut at an edge $e$; adding $f$ to $S$ and deleting that path edge $e$ gives a spanning tree with lower rank sum by [F10], contradicting minimality of $S$. Hence $S$ contains every edge $f$ of $T$ and equals $T$: any additional edge would form a cycle with its $T$-path. Thus $T$ is the unique minimum tree of $G$ exactly when $T\subseteq G\subseteq T\cup A(T)$. Consequently, connected subgraphs of $H$ split into disjoint classes indexed by trees $T\subseteq H$, each class consisting of $T\cup A$ for $A\subseteq A(T)\cap E(H)$. The signed sum in one class is $(-1{)}^{n-1}(1-1{)}^{\mathrm{\mid }A(T)\cap E(H)\mathrm{\mid }}$, whose real absolute value is at most $1$. Applying the finite-sum triangle inequality from [F5, F7] to the class contributions gives $\mathrm{\mid }{U}_n({\gamma }_1,\dots ,{\gamma }_n)\mathrm{\mid }\le {\sum }_{T\in {\mathcal{T}}_n}{\prod }_{\{i,j\}\in E(T)}{\mathbf{1}}_{\{{\gamma }_i\sim {\gamma }_j\}}$. For $n=1$ both sides equal $1$.

A rooted tree means a tree with one distinguished vertex; its height is the greatest number of edges in a path from that root. A size-$n$ labelled tree here has vertex set $[n]$, and in $S_{\gamma }^{(k)}$ its root is label $1$; removing the root separates it into child subtrees. For fixed root label $1$ of type $\gamma$, let $S_{\gamma }^{(k)}$ be the nonnegative sum over all such finite rooted labelled trees of height at most $k$, with all other vertex types summed over $\mathrm{\Gamma }$, each non-root vertex of type $\eta$ weighted by $\mathrm{\mid }{z}_{\eta }\mathrm{\mid }$, each edge weighted by ${\mathbf{1}}_{\{\eta \sim {\eta }^{\mathrm{\prime }}\}}$, and each size-$n$ sum divided by $(n-1)!$. The root has weight $1$, so $S_{\gamma }^{(0)}=1$. At height at most $k+1$, the root has $m$ child subtrees of height at most $k$. For ordered subtree sizes $n_1,\dots ,n_m$, assigning the $n-1$ labels to the ordered branch vertex sets contributes $(n-1)!\mathrm{/}(n_1!\cdots n_m!)$. In each branch there are $n_j$ choices for its child-root label; with the fixed-root subtree sum normalized by $(n_j-1)!$, the factor $n_j(n_j-1)!\mathrm{/}{n}_j!$ is $1$. The parent normalization $(n-1)!$ therefore leaves the product of the branch weights, and division by $m!$ removes the ordering of the branches. Since $\mathrm{\Gamma }$ is finite or in bijection with $\mathbb{N}$, increasing finite type and size cutoffs exhaust the choices; by the nonnegative-sum convention [F6], the branch decomposition gives the corresponding countable-sum identity. Now suppose $S_{\eta }^{(k)}\le e^{a_{\eta }}$ for every $\eta$. The sum $A_{\gamma }^{(k)}:={\sum }_{\eta \sim \gamma }\mathrm{\mid }{z}_{\eta }\mathrm{\mid }{S}_{\eta }^{(k)}$ then satisfies $0\le A_{\gamma }^{(k)}\le a_{\gamma }<\mathrm{\infty }$ by [A1]. The branch identity is therefore the convergent exponential series $S_{\gamma }^{(k+1)}={\sum }_{m=0}^{\mathrm{\infty }}(A_{\gamma }^{(k)}{)}^m\mathrm{/}m!=e^{A_{\gamma }^{(k)}}$, so monotonicity of the real exponential [F3] gives $S_{\gamma }^{(k+1)}\le e^{a_{\gamma }}$. Since $S_{\gamma }^{(0)}=1\le e^{a_{\gamma }}$ by [F2], induction gives this bound for every $k$. The nonnegative sums increase with $k$ and every finite tree has finite height, so their limit is the full rooted tree sum and is at most $e^{a_{\gamma }}$.

Apply the pointwise graph-to-tree bound of step 1.1 to each tuple in the definition of $R_{\gamma }$. All weights are nonnegative after taking absolute values, so summing over the countable polymer labels and then over $n$ preserves the inequality; the right side is the rooted tree sum bounded in step 1.2. Hence $R_{\gamma }\le e^{a_{\gamma }}$.