Montone Complexity of Spanning Tree Polynomial Re-visited

2021-09-14-CDGM-Monotone Complexity of Spanning Tree Polynomial Re-visited

paper

Results

• Spanning Tree polynomial is in VP
• Has monotone circuit complexity $2^{\Omega(n)}$.
• There are some other results in this paper.

Details

• Spanning Tree polynomial is sum over edges of spanning tree.
• $ST(G') = \sum_{t\in T} \prod_{(u,v)\in t, u,v\neq r} x_{u,v}$.
• $G'$ is directed version of an undirected graph (i.e., both edges included).
• Here $r$ is the root, i.e., the root is not in the polynomial and assumed to be 1.
• The polynomial is given as ordered over $u$ in the paper.
• $ST(G)$ can be computed by an ABP via determinant.
• Let $G$ be a $d$-regular expander, then every monotone circuit for $ST(G)$ has size at least $2^{\Omega(n)}$.

Proof

Prerequisites

• Expander Mixing Lemma: Let $G$ be an undirected $d$ regular graph such that $\gamma_2$, the second largest eigenvalue of the adjacency matrix. Then for every set $S,T$ $| |E(S,T)| -\frac{d}{n} |S| |T| | \leq \gamma_2 \sqrt{|S| |T|}$.
  • $E(S,T)$ is the edges in the cut of $S,T$.
• Matrix Tree Theorem: Let $G$ be an undirected graph and $0,\mu_1,\dots,\mu_{n-1}$ be the eigenvalues of the Laplacian of $G$. Then the number of spanning trees is $1/n \mu_1 \cdots \mu_{n-1}$.
• Theorem 2.1 (Yeh19): Let $p$ be a monotone polynomial. Then we can write $p=\sum_{t=1}^s a_t b_t$ with $n/3\leq \supp(a_t) \leq 2n/3$ and $\supp(b_t) = [n]\setminus \supp(a_t)$.
  • Here, supp is the variables occurring in the polynomial.
  • Moreover, the coefficients of any monomial in $a_t b_t$ is bounded by the coefficient of the same monomial in $p$.

Proof

• We can look at the sum $\sum_{i=1}^s a_i b_i$ into buckets.
• Let $X_t={x_{t,i} \mid x_{t,i}\in \supp(a_i)\cup \supp(b_i)}$.
• Our buckets now make the computation look like this $\sum_{i=1}^{s/(n-1)} \sum_{t=2}^n a'_i b'_i$.
• Let us study one of the buckets, by fixing $s$ arbitrarily.
• We want to have an upper bound of $\sum_{t=2}^n |X_t|$.
  • This will give us a lower bound on the size, as we will count the monomials for this fixed $s$.
  • If $x_{i,i'}\in \supp(a_s)$ and $x_{j,j'}\in \supp(b_s)$ then not $x_{i,j}$ and $x_{j,i}$ can be in $\cup_{t=2}^n X_t$.
    • Otherwise, $x_{i,j}\in \supp(a_s)$ and $x_{j,i}\in \supp(b_s)$.
    • Otherwise $x_{i,j}x_{j,i}$ would be contained in a monomial of $a_s b_s$.
    • This is a cycle and hence not allowed in a spanning tree.
    • Notice that $x_{i,j}$ and $x_{j,i}$ are in $X_i,X_j$ respectively.
  • This means that at least one of the two directed edges must be absent in $\cup_{t=2}^n X_t$.
  • Hence, $\sum_{t=2}^n |X_t| \geq dn - E(a_s,b_s)$ where $E(a_s,b_s)$ is the set of undirected edges.
    • The number of monomials is given by $dn$ for the whole graph.
    • Except we have $E(a_s,b_s)$ removed from this because one edge is missing from this for every undirected edge this has.
  • Setting $|a_s|,|b_s| \geq n/3$ and $|a_s|+|b_s| =n$ and the expander Lemma we get
  • $|E(a_s,b_s)| \geq d/n n^2/9 - \lambda_2 n/2 = n(d/9 - \lambda_2/2)$.
  • This gives us the number of monomials for one fixed $s$, namely $\leq 1.01d(1-\alpha)^{n-1}$ for a constant $\alpha$.
  • As the number of monomials in a spanning tree is (in our case) $1/n(d-\lambda_2)^{n-1}$.
  • Our bound is now $(1/n (d-\lambda_2)^{n-1})/ 1.01(1-\alpha)^{n-1}$ which is exponential.

Interesting Open Problems

• Is there an explicit polynomial computable by a formula that has exponential monotone circuits?