Category Archives: probability

Minimum Spanning Trees of Bounded Depth (Random)

I’ve got a new paper up on the arxiv.  David Wilson recently posted this joint work that was one of the last things I did during my post-doc at Microsoft.  It hasn’t been applied to health metrics yet, but maybe it will be.  Let me tell you the story:

A spanning tree is just what it sounds like, if you know that a tree is a graph with no cycles, and make a good guess that the spanning tree is a subgraph that is a tree “spans” all the vertices in the graph.  Minimum cost spanning trees come up in some very practical optimization problems, like if you want to build a electricity network without wasting wires.  It was in this exact context, designing an electricity network for Moravia, that the first algorithm for finding a minimum spanning tree was developed.

Public Domain image of a Minimum Spanning Tree, from Wikipedia

A Minimum Spanning Tree, from Wikipedia

The great thing about looking for a minimum spanning tree is that you don’t have to be sneaky to find it.  If you repeatedly find the cheapest edge which does not create a cycle, and add that to your subgraph, then this greedy approach never goes wrong.  When you can’t add any more edges, you have a minimum spanning tree.  Set systems with this property have been so fun for people to study that they have an intimidating name, matroids.  But don’t be intimidated, you can go a long way in matroids by doing a search-and-replace s/matroid/spanning tree/.

Continue reading

3 Comments

Filed under combinatorial optimization, probability

Applying Probability

My new job is in a den of Bayesians!  This sort of philosophical trouble is something I avoided for years when I worked on random graphs.  In combinatorial probability, I just said “assume the axioms of probability” and got to look for all the interesting facts that follow logically.  People want these probability calculations to say something about the “real world”?  That’s not my thing; it’s up to them to go from math to science.  Well, now it is my problem.

Continue reading

4 Comments

Filed under probability