2 Fairest Edge Usage and Minimum Expected Overlap for Random Spanning Trees

This chapter formalizes results from Albin, Clemens, Hoare, Poggi-Corradini, Sit, and Tymochko (2021). It specializes the general modulus theory of Chapter 1 to spanning trees, and develops the paper’s two main optimization problems: minimum expected overlap (MEO) and fairest edge usage (FEU).

2.1 Random spanning trees, MEO, and FEU

This section follows Sections 1.1–1.3 of the paper: it sets up random spanning trees and states the two optimization problems, minimum expected overlap (MEO) and fairest edge usage (FEU), whose relationship to spanning tree modulus is the subject of the rest of the paper.

Definition 15 Law of a random spanning tree

Let \(G = (V, E)\) be a finite, connected multigraph and let \(\Gamma _G\) be its (finite) set of spanning trees. A law on \(\Gamma _G\) is a probability mass function \(\mu \colon \Gamma _G \to [0,1]\) with \(\sum _{\gamma \in \Gamma _G} \mu (\gamma ) = 1\); we write \(\mu \in P(\Gamma _G)\). A random spanning tree \(\underline\gamma \) has law \(\mu \) (written \(\underline\gamma \sim \mu \)) if \(\mathbb P_\mu (\underline\gamma = \gamma ) = \mu (\gamma )\) for every \(\gamma \in \Gamma _G\).

Definition 16 Minimum expected overlap problem

For \(\mu \in P(\Gamma _G)\), let \(\underline\gamma , \underline\gamma ' \sim \mu \) be independent. The expected overlap of \(\mu \) is

\[ \mathbb E_\mu |\underline\gamma \cap \underline\gamma '| := \sum _{\gamma , \gamma ' \in \Gamma _G} |\gamma \cap \gamma '| \, \mu (\gamma ) \mu (\gamma '). \]

The minimum expected overlap (MEO) problem is

\[ \operatorname {MEO}(\Gamma _G) := \min _{\mu \in P(\Gamma _G)} \mathbb E_\mu |\underline\gamma \cap \underline\gamma '|. \]

A law achieving this minimum is optimal for \(\operatorname {MEO}(\Gamma _G)\).

Definition 17 Edge usage probability

For \(\mu \in P(\Gamma _G)\) and \(e \in E\), the edge usage probability of \(e\) under \(\mu \) is

\[ \mathbb P_\mu (e \in \underline\gamma ) := \sum _{\gamma \in \Gamma _G} \mathbf1_{\{ e \in \gamma \} } \, \mu (\gamma ). \]

Definition 18 Fairest edge usage problem

The fairest edge usage (FEU) problem asks for the edge usage probability function \(\eta \colon E \to [0,1]\) of minimal variance over \(\mu \in P(\Gamma _G)\):

\[ \text{minimize } \operatorname {Var}(\eta ) \quad \text{subject to} \quad \eta (e) = \mathbb P_\mu (e \in \underline\gamma ) \ \forall e \in E, \quad \mu \in P(\Gamma _G). \]

We write \(\operatorname {FEU}(\Gamma _G)\) for this problem.

Definition 19 Fair and forbidden trees

A spanning tree \(\gamma \in \Gamma _G\) is a fair tree if \(\mu ^*(\gamma ) {\gt} 0\) for some law \(\mu ^*\) optimal for \(\operatorname {FEU}(\Gamma _G)\). The set of fair trees is denoted \(\Gamma _G^f\). A tree \(\gamma \in \Gamma _G \setminus \Gamma _G^f\) (if any exist) is a forbidden tree.

2.2 Spanning tree modulus and the MEO problem

This section follows Section 1.7 of the paper and connects the general modulus framework of Chapter 1 back to spanning trees, recovering MEO and FEU as modulus problems. From here on the paper restricts to \(p = 2\) and unweighted graphs (\(\sigma \equiv 1\)), and we do the same.

2.2.1 Strong duality for 2-modulus

The general existence/uniqueness and Fulkerson duality theorems of Section 1 (Theorems 13 and 14) are stated for general \(1 {\lt} p {\lt} \infty \) but are not yet formalized in that generality. The results below are the \(p = 2\) specializations actually used by this chapter; they are proved directly using the connection between the two-norm and the inner product.

Theorem 20 Existence and uniqueness of the 2-extremal density

Let \(\Gamma \) be a finite family of objects on \(G = (V, E, \sigma )\) with \(\operatorname {Adm}(\Gamma ) \ne \emptyset \). There is a unique density \(\rho ^* \in \operatorname {Adm}(\Gamma )\) achieving \(\operatorname {Mod}_{2,\sigma }(\Gamma )\).

Theorem 21 Strong duality for 2-modulus

Let \(\Gamma \) be a finite family of objects on \(G = (V, E, \sigma )\) with \(\operatorname {Adm}(\Gamma ) \ne \emptyset \), and let \(\rho ^*\) be the extremal density for \(\operatorname {Mod}_{2,\sigma }(\Gamma )\). There exists \(\lambda ^* \in \mathbb R_{\ge 0}^\Gamma \) such that

\[ \rho ^*(e) = \frac{1}{2\sigma (e)} \sum _{\gamma \in \Gamma } \gamma (e) \lambda ^*(\gamma ) \qquad \forall e \in E, \]

\[ \lambda ^*(\gamma ) \bigl(1 - \ell _{\rho ^*}(\gamma )\bigr) = 0 \qquad \forall \gamma \in \Gamma , \]

and

\[ \operatorname {Mod}_{2,\sigma }(\Gamma ) = \sum _{\gamma \in \Gamma } \lambda ^*(\gamma ) - \frac14 \sum _{e \in E} \frac{1}{\sigma (e)} \Bigl(\sum _{\gamma \in \Gamma } \gamma (e) \lambda ^*(\gamma )\Bigr)^{\! 2}. \]

Corollary 22 Weak duality for the Lagrangian dual

For any \(\rho \in \operatorname {Adm}(\Gamma )\) and any \(\lambda \in \mathbb R_{\ge 0}^\Gamma \),

\[ \mathcal{E}_{2,\sigma }(\rho ) \ \ge \ \sum _{\gamma \in \Gamma } \lambda (\gamma ) - \frac14 \sum _{e \in E} \frac{1}{\sigma (e)} \Bigl(\sum _{\gamma \in \Gamma } \gamma (e) \lambda (\gamma )\Bigr)^{\! 2}, \]

with equality if and only if \(\rho \) and \(\lambda \) satisfy the stationarity and complementary slackness conditions of Theorem 21.

Corollary 23 2-modulus Fulkerson duality

In the setting of Theorem 21, define \(\eta ^*(e) := \sigma (e) \rho ^*(e) / \operatorname {Mod}_{2,\sigma }(\Gamma )\) for \(e \in E\). Then \(\eta ^* \in \operatorname {Adm}(\widehat\Gamma )\) and \(\eta ^*\) is extremal for \(\operatorname {Mod}_{2,\sigma ^{-1}}(\widehat\Gamma )\), with

\[ \operatorname {Mod}_{2,\sigma }(\Gamma ) \, \operatorname {Mod}_{2,\sigma ^{-1}}(\widehat\Gamma ) = 1. \]

This recovers the \(p = q = 2\) case of Theorem 14 without the general machinery.

Definition 24 Feasible partition

A feasible partition of \(G = (V, E)\) is a partition \(P = \{ V_1, \dots , V_{k_P}\} \) of \(V\) into \(k_P \ge 2\) parts such that each induced subgraph \(G(V_i)\) is connected. Its edge set \(E_P \subseteq E\) consists of the edges joining vertices belonging to different parts.

Theorem 25 Fulkerson dual of spanning trees

Let \(\Gamma _G\) be the (finite) family of spanning trees of \(G = (V, E)\), with usage given by the indicator vectors \(\mathbf1_{\{ e \in \gamma \} }\). The Fulkerson dual family \(\widehat{\Gamma _G}\) is the set of vectors \(\frac{1}{k_P - 1} \mathbf1_{E_P}\), ranging over all feasible partitions \(P\) of \(G\).

Theorem 26 Spanning tree modulus, MEO, and FEU

Let \(\Gamma = \Gamma _G\) be the (finite) family of spanning trees of \(G = (V, E)\) and let \(\widehat\Gamma \) be its Fulkerson dual. Densities \(\rho , \eta \in \mathbb R_{\ge 0}^E\) and a law \(\mu \in P(\Gamma )\) are simultaneously optimal for \(\operatorname {Mod}_2(\Gamma )\), \(\operatorname {Mod}_2(\widehat\Gamma )\), and \(\operatorname {MEO}(\Gamma )\) respectively if and only if

\[ \rho \in \operatorname {Adm}(\Gamma ), \quad \eta (e) = \sum _{\gamma \in \Gamma } \gamma (e) \, \mu (\gamma ) \ \forall e \in E, \quad \eta (e) = \frac{\rho (e)}{\operatorname {Mod}_2(\Gamma )} \ \forall e \in E, \quad \mu (\gamma ) (1 - \ell _\rho (\gamma )) = 0 \ \forall \gamma \in \Gamma . \]

In particular,

\[ \operatorname {MEO}(\Gamma ) = \operatorname {Mod}_2(\widehat\Gamma ) = \operatorname {Mod}_2(\Gamma )^{-1}. \]

Corollary 27 Weak duality for modulus

Let \(\Gamma \) be a finite family of objects on \(G\) with Fulkerson dual \(\widehat\Gamma \). For any \(\rho \in \operatorname {Adm}(\Gamma )\) and \(\eta \in \operatorname {Adm}(\widehat\Gamma )\),

\[ E_2(\rho ) E_2(\eta ) \ge 1, \qquad \text{where } E_2(\rho ) := \sum _{e \in E} \sigma (e) \rho (e)^2, \]

with equality if and only if \(\rho \) and \(\eta \) are optimal for \(\operatorname {Mod}_2(\Gamma )\) and \(\operatorname {Mod}_2(\widehat\Gamma )\) respectively.