Partition matroid

In mathematics, a partition matroid or partitional matroid is a matroid formed from a direct sum of uniform matroids.^[1]

Definition

Let $B_{i}$ be a collection of disjoint sets, and let $d_{i}$ be integers with $0\leq d_{i}\leq |B_{i}|$. Define a set $I$ to be "independent" when, for every index $i$, $|I\cap B_{i}|\leq d_{i}$. Then the sets that are independent sets in this way form the independent sets of a matroid, called a partition matroid. The sets $B_{i}$ are called the blocks of the partition matroid. A basis of the matroid is a set whose intersection with every block $B_{i}$ has size exactly $d_{i}$, and a circuit of the matroid is a subset of a single block $B_{i}$ with size exactly $d_{i}+1$. The rank of the matroid is $\sum d_{i}$.^[2]

Every uniform matroid $U{}_{n}^{r}$ is a partition matroid, with a single block $B_{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.^[3]

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.^[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 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$.^[6]

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)$.^[7]

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, 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 $d_{i}=1$ 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 663728.
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., 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.