### Metal Trees

*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 , and with each edge *e* we associate three numbers which we interpret in the following way: to construct edge *e* we need to use kilograms of aluminum, kilograms of beryllium, and 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

ktypes of metals, there is a setSof spanning trees, so that for any assignment of prices to the metals, one of the spanning trees inShas minimal price among all spanning trees.

The theorem is interesting since the total number of spanning trees is exponential in . 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

Dbe the set of all directions of its edges. Then any projection of the polyhedron intokdimensions has at most vertices.

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

Filed under: math, polyhedra, talks | Leave a Comment

## No Responses Yet to “Metal Trees”