### Metal Trees

01Mar11

Roxy Paine’s sculpture “Defunct” (photo, Nicole Marti)

There were a couple of seminars today and one mentioned a result giving the following interesting corollary. Suppose we have a graph $G=(V, E)$, and with each edge e we associate three numbers $a_e, b_e, c_e$ which we interpret in the following way: to construct edge e we need to use $a_e$ kilograms of aluminum, $b_e$ kilograms of beryllium, and $c_e$ kilograms of chromium. Later on we’ll decide to construct a spanning tree of the graph, which we would like to do cheaply; however the market price of the three metals affects which spanning tree is cheap. Nonetheless, it’s possible to fix a relatively small set of spanning trees ahead of time, and buy just one:

For k types of metals, there is a set S of $O(|E|^{2(k-1)})$ spanning trees, so that for any assignment of prices to the metals, one of the spanning trees in S has minimal price among all spanning trees.

The theorem is interesting since the total number of spanning trees is exponential in $|E|$. Is the theorem tight? I do not know.

The theorem follows from a more general result in the seminar (which was presented by Marco Di Summa, another member of my group at EPFL).

Take a polyhedron, and let D be the set of all directions of its edges. Then any projection of the polyhedron into k dimensions has at most $O(|D|^{k-1})$ vertices.

We combine this with the fact that the spanning tree polytope has at most $|E|^2$ directions (a similar fact holds for any matroid).