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.

Formal definition

edit

Let   be a collection of disjoint sets ("categories"). Let   be integers with   ("capacities"). Define a subset   to be "independent" when, for every index  ,  . The sets satisfying this condition form the independent sets of a matroid, called a partition matroid.

The sets   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   has size exactly  . A circuit of the matroid is a subset of a single block   with size exactly  . The rank of the matroid is  .[2]

Every uniform matroid   is a partition matroid, with a single block   of   elements and with  . 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  . The partitions that obey this more restrictive definition are the transversal matroids of the family of disjoint sets given by their blocks.[3]

Properties

edit

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

edit

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  , the sets of edges satisfying the condition that no two edges share an endpoint in   are the independent sets of a partition matroid with one block per vertex in   and with each of the numbers   equal to one. The sets of edges satisfying the condition that no two edges share an endpoint in   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.[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

edit

A clique complex is a family of sets of vertices of a graph   that induce complete subgraphs of  . A clique complex forms a matroid if and only if   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  .[6]

Enumeration

edit

The number of distinct partition matroids that can be defined over a set of   labeled elements, for  , 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  .[7]

References

edit
  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.
  2. ^ Lawler, Eugene L. (1976), Combinatorial Optimization: Networks and Matroids, Rinehart and Winston, New York: Holt, p. 272, MR 0439106.
  3. ^ E.g., see Kashiwabara, Okamoto & Uno (2007). Lawler (1976) uses the broader definition but notes that the   restriction is useful in many applications.
  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.
  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.
  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.
  7. ^ Recski, A. (1974), "Enumerating partitional matroids", Studia Scientiarum Mathematicarum Hungarica, 9: 247–249 (1975), MR 0379248.