A partitioning of a set of
items is a grouping of these items into
disjoint, equally sized classes. Any partition can be modeled as a graph. The items become the vertices of the graph and two vertices are connected by an edge if and only if the associated items belong to the same class. In a planted partition model a graph that models a partition is given, which is obscured by random noise, i.e., edges within a class can get removed and edges between classes can get inserted. The task is to reconstruct the planted partition from this graph. We design a spectral partitioning algorithm and analyze how many items it misclassifies in the worst case. The number of classes
is one parameter in the model that allows to control the difficulty of the problem. Our analysis extends the range of
for which any non-trivial quality guarantees can be given.