Posts tagged graph theory
Partitions and Graphs

A partition of a set is a way of dividing that set into several non-empty, non-overlapping subsets. For example, the partitions of the set {A,B,C} are as follows:

  • A|B|C
  • AB|C
  • AC|B
  • BC|A
  • ABC

The Bell numbers (OEIS/A000110) describe the number of unique partitions for a set of n elements. The sequence grows pretty fast:

1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437, 190899322, 1382958545, ...

Set partitions are interesting for a number of reasons. One reason is that set partitions also describe the number of equivalence relations on a set. So, for an arbitrary set there are B_n ways to treat the n elements of that set as equivalent. This puts an upper bound on measurement, since we can understand these equivalence relations as modes of indistinguishability.

Another reason is that Bell numbers also describe the number of unique component graphs for n nodes. E.g. for a simple graph with 3 labeled nodes, there are 5 unique graphs:

  • A B C
  • A-B C
  • A-C B
  • B-C A
  • A-B-C

Set partitions also describe the possible ways of dividing a set of events into equivalent outcomes for Bayesian learning. If I want to know how to think about the possible outcomes of some experiment, for example, I partition the set of possible observations. However, your choice of partition matters a lot to how you should set your credences. This suggests that you should follow a rule or be otherwise internally consistent in some way in how you partition the set of possible observations. What I'd like to know is whether we can give well-defined conditions under which this requirement is met.