Monotone Bounded Depth Formula Complexity of Graph Homomorphism Polynomials

Abstract

We introduce baggy elimination trees, a novel graph decomposition that generalises the classical elimination trees underlying treedepth, and use them to give a complete characterisation of the monotone bounded-depth formula complexity of graph homomorphism and coloured isomorphism polynomials. Specifically, we prove that the $\hat{I}”$-product depth monotone formula complexity of these polynomials is $\hat{I}˜\left(n^{\hat{I}{»}_{\hat{I}}”(H)}\right)$, where $\hat{I}{»}_{\hat{I}}”(H)$ is the minimum cost of a baggy elimination tree for $H$ at BET-depth~$\hat{I}”$. This result closes the last open case in the programme initiated by Komarath, Pandey and Rahul and continued by Bhargav, Chen, Curticapean and Dwivedi: tight size characterisations of monotone circuit complexity (via treewidth / bounded-depth treewidth), monotone ABP complexity (via pathwidth / bounded-depth pathwidth), and monotone formula complexity (via treedepth) were already known; our theorem supplies the missing bounded-depth formula characterisation via the new notion of bounded-depth baggy-elimination-tree cost $\hat{I}{»}_{\hat{I}}”$, completing the picture for all three models in algebraic complexity and their fixed depth variants. As applications, for constant-degree polynomial families we derive an almost-optimal separation between monotone circuits and monotone formulas at every fixed product depth: there exists a family computable by $O(N)$-size monotone circuits of product depth $\hat{I}”$ that requires $\hat{I}\text{c◯}(N^{\hat{I}”/2})$-size monotone formulas of the same depth (and this exponent is optimal up to a constant factor). We also prove a strict depth hierarchy: for every $\hat{I}”\ge 1$ and every constant $k\ge 2$, there is a constant-degree family with $O(s(N))$-size monotone formulas of product depth $\hat{I}”$ that requires $\hat{I}\text{c◯}(s(N{)}^k)$-size monotone formulas of product depth $\hat{I}”-1$.

14 pages, 6 figures