# Partition matroid

In mathematics, a partition matroid or partitional matroid is a matroid that is a direct sum of uniform matroids. 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.

## Formal definition

Let $C_{i}$ be a collection of disjoint sets ("categories"). Let $d_{i}$ be integers with $0\leq d_{i}\leq |C_{i}|$ ("capacities"). Define a subset $I\subseteq \bigcup _{i}C_{i}$ to be "independent" when, for every index $i$, $|I\cap C_{i}|\leq d_{i}$. The sets satisfying this condition form the independent sets of a matroid, called a partition matroid.
The sets $C_{i}$ are called the categories or the blocks of the partition matroid.
A basis of the partition matroid is a set whose intersection with every block $C_{i}$ has size exactly $d_{i}$. A circuit of the matroid is a subset of a single block $C_{i}$ with size exactly $d_{i}+1$. The rank of the matroid is $\sum d_{i}$.
Every uniform matroid $U_{n}^{r}$ is a partition matroid, with a single block $C_{1}$ of $n$ elements and with $d_{1}=r$. Every partition matroid is the direct sum of a collection of uniform matroids, one for each of its blocks.
In some publications, the notion of a partition matroid is defined more restrictively, with every $d_{i}=1$. The partitions that obey this more restrictive definition are the transversal matroids of the family of disjoint sets given by their blocks.

## Properties

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.

## Matching

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)$, the sets of edges satisfying the condition that no two edges share an endpoint in $U$ are the independent sets of a partition matroid with one block per vertex in $U$ and with each of the numbers $d_{i}$ equal to one. The sets of edges satisfying the condition that no two edges share an endpoint in $V$ are the independent sets of a second partition matroid. Therefore, the bipartite maximum matching problem can be represented as a matroid intersection of these two matroids.
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.

## Clique complexes

A clique complex is a family of sets of vertices of a graph $G$ that induce complete subgraphs of $G$. A clique complex forms a matroid if and only if $G$ is a complete multipartite graph, and in this case the resulting matroid is a partition matroid. The clique complexes are exactly the set systems that can be formed as intersections of families of partition matroids for which every $d_{i}=1$.

## Enumeration

The number of distinct partition matroids that can be defined over a set of $n$ labeled elements, for $n=0,1,2,\dots$, is
    1, 2, 5, 16, 62, 276, 1377, 7596, 45789, 298626, 2090910, ... (sequence A005387 in the OEIS).
The exponential generating function of this sequence is $f(x)=\exp(e^{x}(x-1)+2x+1)$.