Is it possible to quantify the number of dimensions in combinatorial spaces. The space I am particularly interested is all partitions of a set, bounded by the Bell number, where objects in this space are particular partitions.
Quantifying dimensionality of combinatorial space
-
1For what purpose? – 2010-09-14
-
0Just to understand the the dimensionality of the space of all partitions of a graph – 2010-09-16
-
0I know next to nothing about matroids, but what I do know is that they are used as a way to generalize the notion of "independence" in both vector spaces and graphs. Perhaps that path could be fruitful. I'm not sure. – 2010-11-02
1 Answers
It makes sense to consider some sets of combinatorial objects as spaces (or polytopes) and therefore discuss dimensionality (e.g. the set of n by n (-1,0,+1)-matrices). Although, perhaps the word "dimension" could better be described as "degrees of freedom".
Mathematically, degrees of freedom is the dimension of the domain of a random vector, or essentially the number of 'free' components: how many components need to be known before the vector is fully determined.
I suspect that it will be difficult to discuss dimensionality in many combinatorial settings. For example, imagine constructing a Latin square, starting from an empty matrix, placing symbols one-at-a-time in a non-clashing manner. After placing (say) half of the symbols, we might find: (a) there are still many completions of this partial Latin square, (b) there are no completions of this partial Latin square or (c) there is a unique completion of this partial Latin square. This seems to go against the notion of dimensionality -- the number of "components" required to determine the Latin square is not fixed.
You could think of the set of partitions of a set of n elements as having dimension n. You require n pieces of information to determine the partition (which set each element is in). But as Qiaochu Yuan points out, who cares? There's no point in having a notion of "dimension" unless you can use it for something.