Metal Trees

01Mar11

Roxy Paine's sculpture "Defunct" (photo, Nicole Marti)

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).



No Responses Yet to “Metal Trees”

  1. Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: