Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a set of vertices $V$ such each vertex $v\in V$ is labelled with a color $col(v)$. I want to consider the class of partitions of $V$ that have the following property in common: all vertices having the same color must belong to the same part.

For example:

  1. Partition the vertices of $V$ according to their colors. $V(col)$ is a subset of vertices of $V$ whose color is $col$.

  2. Partition the vertices of $V$ according to the first letter of their color. $V(r)$ is the set of vertices of $V$ whose color starts with letter (r), for example (red).

  3. Partition the vertices of $V$ according to the number of the letters of their color. $V(4)$ is the set of vertices of $V$ whose colors have 4 letters (blue, ....).

I need a (concise) notation to describe the set of all these partitions. The notation have to give me access to the parameter of the partition, for example I need to be able to speak about $V(x)$ where $x$ may be a color, a first letter in a color, .... Thank you.

share|improve this question
add comment

1 Answer 1

Let's say that such a partition of the vertices of $G$ respects colors.

If there are $n$ colors, the number of partitions that respect colors is $B_n$, the $n$-th Bell number. There is no nice closed form for the Bell numbers, but they grow rather quickly: starting with $B_0$, the first few are $1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147$, and $115975$. (This is sequence A000110 in the Online Encyclopedia of Integer Sequences). With only five colors you already have $52$ possible partitions.

Thus, it seems very likely that a partition that respects colors may not have its pieces determined by an identifiable parameter, unless the number of colors is very small, perhaps no more than four.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.