# Partition matroid

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Partition_matroid
> Markdown URL: https://mediated.wiki/source/Partition_matroid.md
> Source: https://en.wikipedia.org/wiki/Partition_matroid
> Source revision: 1288137819
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

Direct sum of uniform matroids

For the [bipartite graph](/source/Bipartite_graph) shown on the left, each vertex in the first column is assigned a unique color. Then, each edge is colored based on which colored vertex it is connected to. Each independent set in the [matroid](/source/Matroid) on the right is allowed a maximum of 1 edge of each color. Thus, the matroid is a **partition matroid** with

          |

          C

            i

          |

        =
        3

    {\displaystyle |C_{i}|=3}

 and

          d

            i

        =
        1

    {\displaystyle d_{i}=1}

 for all

        i

    {\displaystyle i}

. The latter condition means this matroid is also a [transversal matroid](/source/Transversal_matroid).

In mathematics, a **partition matroid** or **partitional matroid** is a [matroid](/source/Matroid) that is a [direct sum](/source/Direct_sum) of [uniform matroids](/source/Uniform_matroid).[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.

## Formal definition

Let C i {\displaystyle C_{i}} be a collection of [disjoint sets](/source/Disjoint_sets) ("categories"). Let d i {\displaystyle d_{i}} be integers with 0 ≤ d i ≤ | C i | {\displaystyle 0\leq d_{i}\leq |C_{i}|} ("capacities"). Define a subset I ⊆ ⋃ i C i {\displaystyle I\subseteq \bigcup _{i}C_{i}} to be "independent" when, for every index i {\displaystyle i} , | I ∩ C i | ≤ d i {\displaystyle |I\cap C_{i}|\leq d_{i}} . The sets satisfying this condition form the independent sets of a [matroid](/source/Matroid), called a **partition matroid**.

The sets C i {\displaystyle 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 {\displaystyle C_{i}} has size exactly d i {\displaystyle d_{i}} . A **circuit** of the matroid is a subset of a single block C i {\displaystyle C_{i}} with size exactly d i + 1 {\displaystyle d_{i}+1} . The [**rank**](/source/Matroid_rank) of the matroid is ∑ d i {\displaystyle \sum d_{i}} .[2]

Every [uniform matroid](/source/Uniform_matroid) U n r {\displaystyle U{}_{n}^{r}} is a partition matroid, with a single block C 1 {\displaystyle C_{1}} of n {\displaystyle n} elements and with d 1 = r {\displaystyle 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 {\displaystyle d_{i}=1} . The partitions that obey this more restrictive definition are the [transversal matroids](/source/Transversal_matroid) of the family of disjoint sets given by their blocks.[3]

## Properties

As with the uniform matroids they are formed from, the [dual matroid](/source/Dual_matroid) of a partition matroid is also a partition matroid, and every [minor](/source/Matroid_minor) of a partition matroid is also a partition matroid. Direct sums of partition matroids are partition matroids as well.

## Matching

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

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]

## Clique complexes

A [clique complex](/source/Clique_complex) is a [family of sets](/source/Family_of_sets) of vertices of a graph G {\displaystyle G} that induce complete subgraphs of G {\displaystyle G} . A clique complex forms a matroid if and only if G {\displaystyle G} is a [complete multipartite graph](/source/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](/source/Matroid_intersection) of families of partition matroids for which every d i = 1 {\displaystyle d_{i}=1} .[6]

## Enumeration

The number of distinct partition matroids that can be defined over a set of n {\displaystyle n} labeled elements, for n = 0 , 1 , 2 , … {\displaystyle n=0,1,2,\dots } , is

- 1, 2, 5, 16, 62, 276, 1377, 7596, 45789, 298626, 2090910, ... (sequence [A005387](https://oeis.org/A005387) in the [OEIS](/source/On-Line_Encyclopedia_of_Integer_Sequences)).

The [exponential generating function](/source/Exponential_generating_function) of this sequence is f ( x ) = exp ⁡ ( e x ( x − 1 ) + 2 x + 1 ) {\displaystyle f(x)=\exp(e^{x}(x-1)+2x+1)} .[7]

## References

1. **[^](#cite_ref-1)** Recski, A. (1975), "On partitional matroids with applications", *Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vol. III*, Colloq. Math. Soc. János Bolyai, vol. 10, Amsterdam: North-Holland, pp. 1169–1179, [MR](/source/MR_(identifier)) [0389630](https://mathscinet.ams.org/mathscinet-getitem?mr=0389630).

1. **[^](#cite_ref-2)** [Lawler, Eugene L.](/source/Eugene_Lawler) (1976), *Combinatorial Optimization: Networks and Matroids*, Rinehart and Winston, New York: Holt, p. 272, [MR](/source/MR_(identifier)) [0439106](https://mathscinet.ams.org/mathscinet-getitem?mr=0439106).

1. **[^](#cite_ref-3)** E.g., see [Kashiwabara, Okamoto & Uno (2007)](#CITEREFKashiwabaraOkamotoUno2007). [Lawler (1976)](#CITEREFLawler1976) uses the broader definition but notes that the d i = 1 {\displaystyle d_{i}=1} restriction is useful in many applications.

1. **[^](#cite_ref-4)** [Papadimitriou, Christos H.](/source/Christos_Papadimitriou); [Steiglitz, Kenneth](/source/Kenneth_Steiglitz) (1982), *Combinatorial Optimization: Algorithms and Complexity*, Englewood Cliffs, N.J.: Prentice-Hall Inc., pp. 289–290, [ISBN](/source/ISBN_(identifier)) [0-13-152462-3](https://en.wikipedia.org/wiki/Special:BookSources/0-13-152462-3), [MR](/source/MR_(identifier)) [0663728](https://mathscinet.ams.org/mathscinet-getitem?mr=0663728).

1. **[^](#cite_ref-5)** Fekete, Sándor P.; Firla, Robert T.; Spille, Bianca (2003), "Characterizing matchings as the intersection of matroids", *Mathematical Methods of Operations Research*, **58** (2): 319–329, [arXiv](/source/ArXiv_(identifier)):[math/0212235](https://arxiv.org/abs/math/0212235), [doi](/source/Doi_(identifier)):[10.1007/s001860300301](https://doi.org/10.1007%2Fs001860300301), [MR](/source/MR_(identifier)) [2015015](https://mathscinet.ams.org/mathscinet-getitem?mr=2015015).

1. **[^](#cite_ref-6)** Kashiwabara, Kenji; Okamoto, Yoshio; Uno, Takeaki (2007), "Matroid representation of clique complexes", *Discrete Applied Mathematics*, **155** (15): 1910–1929, [doi](/source/Doi_(identifier)):[10.1016/j.dam.2007.05.004](https://doi.org/10.1016%2Fj.dam.2007.05.004), [MR](/source/MR_(identifier)) [2351976](https://mathscinet.ams.org/mathscinet-getitem?mr=2351976). For the same results in a complementary form using independent sets in place of cliques, see [Tyshkevich, R. I.](/source/Regina_Tyshkevich); Urbanovich, O. P.; Zverovich, I. È. (1989), "Matroidal decomposition of a graph", *Combinatorics and graph theory (Warsaw, 1987)*, Banach Center Publ., vol. 25, Warsaw: PWN, pp. 195–205, [MR](/source/MR_(identifier)) [1097648](https://mathscinet.ams.org/mathscinet-getitem?mr=1097648).

1. **[^](#cite_ref-7)** Recski, A. (1974), "Enumerating partitional matroids", *Studia Scientiarum Mathematicarum Hungarica*, **9**: 247–249 (1975), [MR](/source/MR_(identifier)) [0379248](https://mathscinet.ams.org/mathscinet-getitem?mr=0379248).

---
Adapted from the Wikipedia article [Partition matroid](https://en.wikipedia.org/wiki/Partition_matroid) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Partition_matroid?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.