[HN Gopher] Hypergraphs Reveal Solution to 50-Year-Old Problem
       ___________________________________________________________________
        
       Hypergraphs Reveal Solution to 50-Year-Old Problem
        
       Author : theafh
       Score  : 49 points
       Date   : 2022-07-14 13:54 UTC (9 hours ago)
        
 (HTM) web link (www.quantamagazine.org)
 (TXT) w3m dump (www.quantamagazine.org)
        
       | sdenton4 wrote:
       | Neat! 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 wrote:
       | In 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.
        
       ___________________________________________________________________
       (page generated 2022-07-14 23:02 UTC)