Monotone Bounded Depth Formula Complexity of Graph Homomorphism Polynomials

We characterize the monotone bounded depth formula complexity for graph homomorphism and colored isomorphism polynomials using a graph parameter called the cost of bounded product depth baggy elimination tree. Using this characterization, we show an almost optimal separation between monotone circuits and monotone formulas using constant-degree polynomials for all fixed product depths, and an almost optimal separation between monotone formulas of product depths $\mathrm{\Delta }$ and $\mathrm{\Delta }$ + 1 for all $\mathrm{\Delta }$ $\ge$ 1.