In mathematics, a partition matroid or partitional matroid is a matroid that is a direct sum of uniform matroids.[1] It is defined over a base set in which the elements are partitioned into different categories. For each category, there is a capacity constraint - a maximum number of allowed elements from this category. The independent sets of a partition matroid are exactly the sets in which, for each category, the number of elements from this category is at most the category capacity.
Let
Ci
di
0\ledi\le|Ci|
I\subsetcupiCi
i
|I\capCi|\ledi
The sets
Ci
A basis of the partition matroid is a set whose intersection with every block
Ci
di
Ci
di+1
\sumdi
r | |
U{} | |
n |
C1
n
d1=r
In some publications, the notion of a partition matroid is defined more restrictively, with every
di=1
As with the uniform matroids they are formed from, the dual matroid of a partition matroid is also a partition matroid, and every minor of a partition matroid is also a partition matroid. Direct sums of partition matroids are partition matroids as well.
A maximum matching in a graph is a set of edges that is as large as possible subject to the condition that no two edges share an endpoint. In a bipartite graph with bipartition
(U,V)
U
U
di
V
More generally the matchings of a graph may be represented as an intersection of two matroids if and only if every odd cycle in the graph is a triangle containing two or more degree-two vertices.[5]
A clique complex is a family of sets of vertices of a graph
G
G
G
The number of distinct partition matroids that can be defined over a set of
n
n=0,1,2,...
1, 2, 5, 16, 62, 276, 1377, 7596, 45789, 298626, 2090910, ... .The exponential generating function of this sequence is
f(x)=\exp(ex(x-1)+2x+1)