{{Use American English|date = January 2019}} {{Short description|Direct sum of uniform matroids}} [[File:Partition matroid.svg|thumb|upright=1.35|For the [[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]] on the right is allowed a maximum of 1 edge of each color. Thus, the matroid is a '''partition matroid''' with <math>|C_i| = 3</math> and <math>d_i = 1</math> for all <math>i</math>. The latter condition means this matroid is also a [[transversal matroid]].]]
In mathematics, a '''partition matroid''' or '''partitional matroid''' is a [[matroid]] that is a [[direct sum]] of [[uniform matroid]]s.<ref>{{citation | last = Recski | first = A. | contribution = On partitional matroids with applications | location = Amsterdam | mr = 0389630 | pages = 1169–1179 | publisher = North-Holland | series = Colloq. Math. Soc. János Bolyai | title = Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vol. III | volume = 10 | year = 1975}}.</ref> 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 <math>C_i</math> be a collection of [[disjoint sets]] ("categories"). Let <math>d_i</math> be integers with <math>0\le d_i\le |C_i|</math> ("capacities"). Define a subset <math>I\subseteq \bigcup_i C_i</math> to be "independent" when, for every index <math>i</math>, <math>|I\cap C_i|\le d_i</math>. The sets satisfying this condition form the independent sets of a [[matroid]], called a '''partition matroid'''.
The sets <math>C_i</math> 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 <math>C_i</math> has size exactly <math>d_i</math>. A '''circuit''' of the matroid is a subset of a single block <math>C_i</math> with size exactly <math>d_i+1</math>. The [[Matroid rank|'''rank''']] of the matroid is <math>\sum d_i</math>.<ref>{{citation | last = Lawler | first = Eugene L. | authorlink = Eugene Lawler | location = Rinehart and Winston, New York | mr = 0439106 | page = 272 | publisher = Holt | title = Combinatorial Optimization: Networks and Matroids | year = 1976}}.</ref>
Every [[uniform matroid]] <math>U{}^r_n</math> is a partition matroid, with a single block <math>C_1</math> of <math>n</math> elements and with <math>d_1=r</math>. 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 <math>d_i=1</math>. The partitions that obey this more restrictive definition are the [[transversal matroid]]s of the family of disjoint sets given by their blocks.<ref>E.g., see {{harvtxt|Kashiwabara|Okamoto|Uno|2007}}. {{harvtxt|Lawler|1976}} uses the broader definition but notes that the <math>d_i=1</math> restriction is useful in many applications.</ref>
==Properties== As with the uniform matroids they are formed from, the [[dual matroid]] of a partition matroid is also a partition matroid, and every [[matroid minor|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 <math>(U,V)</math>, the sets of edges satisfying the condition that no two edges share an endpoint in <math>U</math> are the independent sets of a partition matroid with one block per vertex in <math>U</math> and with each of the numbers <math>d_i</math> equal to one. The sets of edges satisfying the condition that no two edges share an endpoint in <math>V</math> 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.<ref>{{citation | last1 = Papadimitriou | first1 = Christos H. | author1-link = Christos Papadimitriou | last2 = Steiglitz | first2 = Kenneth | author2-link = Kenneth Steiglitz | isbn = 0-13-152462-3 | location = Englewood Cliffs, N.J. | mr = 663728 | pages = 289–290 | publisher = Prentice-Hall Inc. | title = Combinatorial Optimization: Algorithms and Complexity | year = 1982}}.</ref>
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.<ref>{{citation | last1 = Fekete | first1 = Sándor P. | last2 = Firla | first2 = Robert T. | last3 = Spille | first3 = Bianca | arxiv = math/0212235 | doi = 10.1007/s001860300301 | issue = 2 | journal = Mathematical Methods of Operations Research | mr = 2015015 | pages = 319–329 | title = Characterizing matchings as the intersection of matroids | volume = 58 | year = 2003}}.</ref>
==Clique complexes== A [[clique complex]] is a [[family of sets]] of vertices of a graph <math>G</math> that induce complete subgraphs of <math>G</math>. A clique complex forms a matroid if and only if <math>G</math> 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 [[Matroid intersection|intersections]] of families of partition matroids for which every {{nowrap|<math>d_i=1</math>.<ref>{{citation | last1 = Kashiwabara | first1 = Kenji | last2 = Okamoto | first2 = Yoshio | last3 = Uno | first3 = Takeaki | doi = 10.1016/j.dam.2007.05.004 | issue = 15 | journal = Discrete Applied Mathematics | mr = 2351976 | pages = 1910–1929 | title = Matroid representation of clique complexes | volume = 155 | year = 2007| doi-access = free }}. For the same results in a complementary form using independent sets in place of cliques, see {{citation | last1 = Tyshkevich | first1 = R. I. | author1-link = Regina Tyshkevich | last2 = Urbanovich | first2 = O. P. | last3 = Zverovich | first3 = I. È. | contribution = Matroidal decomposition of a graph | location = Warsaw | mr = 1097648 | pages = 195–205 | publisher = PWN | series = Banach Center Publ. | title = Combinatorics and graph theory (Warsaw, 1987) | volume = 25 | year = 1989}}.</ref>}}
==Enumeration== The number of distinct partition matroids that can be defined over a set of <math>n</math> labeled elements, for <math>n=0,1,2,\dots</math>, is :1, 2, 5, 16, 62, 276, 1377, 7596, 45789, 298626, 2090910, ... {{OEIS|A005387}}. The [[exponential generating function]] of this sequence is <math>f(x)=\exp(e^x(x-1)+2x+1)</math>.<ref>{{citation | last = Recski | first = A. | journal = Studia Scientiarum Mathematicarum Hungarica | mr = 0379248 | pages = 247–249 (1975) | title = Enumerating partitional matroids | volume = 9 | year = 1974}}.</ref>
==References== {{reflist}}
[[Category:Matroid theory]] [[Category:Matching (graph theory)]]