3 ms·
Hypergraphs Reveal Solution to 50-Year-Old Problem
- sdenton4 4y agoNeat! I wonder if the absorption method could be used for my favorite unsolved graph theory problem. The 'tree packing problem,' which goes like this: In my left hand, I have a complete graph on N vertices, which has N-choose-2 edges. In my right hand, I have a collection of trees on 1, 2, 3, ..., N vertices. We may observe that my right hand also contains N-choose-2 edges. So the question: Can I 'pack' the trees into the complete graph so that no edges overlap? In practice, it's pretty easy to pack any particular set of trees, yet hard to prove that it's always possible. There's lots of special cases proven, but (last I checked) no general proof.
- biomcgary 4y agoIn the past, I've applied maximum flow and electrical resistance approaches to biological networks, so I could easily see refinement of this algorithm having practical applications for diverse domains.