• Images
• Videos
• Documents
• Books
• Articles

Formal definition

Let C i {\displaystyle C_{i}} be a collection of 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, 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 of the matroid is ∑ d i {\displaystyle \sum d_{i}} .²

Every 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 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 ) {\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 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 {\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, 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 {\displaystyle d_{i}=1} .⁶

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

The 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)} .⁷

References

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 0389630. /wiki/MR_(identifier) ↩

2. Lawler, Eugene L. (1976), Combinatorial Optimization: Networks and Matroids, Rinehart and Winston, New York: Holt, p. 272, MR 0439106. /wiki/Eugene_Lawler ↩

3. E.g., see Kashiwabara, Okamoto & Uno (2007). Lawler (1976) uses the broader definition but notes that the d i = 1 {\displaystyle d_{i}=1} restriction is useful in many applications. - Kashiwabara, Kenji; Okamoto, Yoshio; Uno, Takeaki (2007), "Matroid representation of clique complexes", Discrete Applied Mathematics, 155 (15): 1910–1929, doi:10.1016/j.dam.2007.05.004, MR 2351976 https://doi.org/10.1016%2Fj.dam.2007.05.004 ↩

4. Papadimitriou, Christos H.; Steiglitz, Kenneth (1982), Combinatorial Optimization: Algorithms and Complexity, Englewood Cliffs, N.J.: Prentice-Hall Inc., pp. 289–290, ISBN 0-13-152462-3, MR 0663728. 0-13-152462-3 ↩

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:math/0212235, doi:10.1007/s001860300301, MR 2015015. /wiki/ArXiv_(identifier) ↩

6. Kashiwabara, Kenji; Okamoto, Yoshio; Uno, Takeaki (2007), "Matroid representation of clique complexes", Discrete Applied Mathematics, 155 (15): 1910–1929, doi:10.1016/j.dam.2007.05.004, MR 2351976. For the same results in a complementary form using independent sets in place of cliques, see Tyshkevich, R. I.; 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 1097648. /wiki/Doi_(identifier) ↩

7. Recski, A. (1974), "Enumerating partitional matroids", Studia Scientiarum Mathematicarum Hungarica, 9: 247–249 (1975), MR 0379248. /wiki/MR_(identifier) ↩