0xDE (11011110) wrote,

Cryptomorphic

Did you know that, if you have two partitions of a set, then they have a unique coarsest common refinement and a unique finest common coarsening, and that this gives the family of all possible partitions the structure of a lattice? And did you know that it's the kind of lattice that's secretly a matroid, and it's the kind of matroid that's secretly a graph? Specifically, it's a complete graph, the vertices of which form the set that's being partitioned (surprise! matroids are about edges but here it starts and ends with vertices), and each possible way of partitioning these vertices forms the set of connected components of a subgraph of the complete graph.

Finding connections like this, between concepts that I thought I understood but didn't realize were related to each other, is one of the things I like best about editing Wikipedia.

(The graphic matroid and geometric lattice articles are new. This matroid binge got kicked off when I started cleaning up the Fulkerson Prize article (congratulations to all the new winners!) and in doing so was reminded about Rota's conjecture. Other new matroidality: matroid minor, partition matroid, regular matroid, uniform matroid. )
Tags: combinatorics, wikipedia
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded  

  • 0 comments