Partition matroid
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
Let [math]\displaystyle{ C_i }[/math] be a collection of disjoint sets ("categories"). Let [math]\displaystyle{ d_i }[/math] be integers with [math]\displaystyle{ 0\le d_i\le |C_i| }[/math] ("capacities"). Define a subset [math]\displaystyle{ I\subset \bigcup_i C_i }[/math] to be "independent" when, for every index [math]\displaystyle{ i }[/math], [math]\displaystyle{ |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]\displaystyle{ 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]\displaystyle{ C_i }[/math] has size exactly [math]\displaystyle{ d_i }[/math]. A circuit of the matroid is a subset of a single block [math]\displaystyle{ C_i }[/math] with size exactly [math]\displaystyle{ d_i+1 }[/math]. The rank of the matroid is [math]\displaystyle{ \sum d_i }[/math].[2]
Every uniform matroid [math]\displaystyle{ U{}^r_n }[/math] is a partition matroid, with a single block [math]\displaystyle{ C_1 }[/math] of [math]\displaystyle{ n }[/math] elements and with [math]\displaystyle{ 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]\displaystyle{ d_i=1 }[/math]. 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 [math]\displaystyle{ (U,V) }[/math], the sets of edges satisfying the condition that no two edges share an endpoint in [math]\displaystyle{ U }[/math] are the independent sets of a partition matroid with one block per vertex in [math]\displaystyle{ U }[/math] and with each of the numbers [math]\displaystyle{ d_i }[/math] equal to one. The sets of edges satisfying the condition that no two edges share an endpoint in [math]\displaystyle{ 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.[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 [math]\displaystyle{ G }[/math] that induce complete subgraphs of [math]\displaystyle{ G }[/math]. A clique complex forms a matroid if and only if [math]\displaystyle{ 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 intersections of families of partition matroids for which every [math]\displaystyle{ d_i=1 }[/math].[6]
Enumeration
The number of distinct partition matroids that can be defined over a set of [math]\displaystyle{ n }[/math] labeled elements, for [math]\displaystyle{ n=0,1,2,\dots }[/math], is
The exponential generating function of this sequence is [math]\displaystyle{ f(x)=\exp(e^x(x-1)+2x+1) }[/math].[7]
References
- ↑ 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.
- ↑ Combinatorial Optimization: Networks and Matroids, Rinehart and Winston, New York: Holt, 1976, p. 272.
- ↑ E.g., see (Kashiwabara Okamoto). (Lawler 1976) uses the broader definition but notes that the [math]\displaystyle{ d_i=1 }[/math] restriction is useful in many applications.
- ↑ Combinatorial Optimization: Algorithms and Complexity, Englewood Cliffs, N.J.: Prentice-Hall Inc., 1982, pp. 289–290, ISBN 0-13-152462-3.
- ↑ 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, doi:10.1007/s001860300301.
- ↑ 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. For the same results in a complementary form using independent sets in place of cliques, see "Matroidal decomposition of a graph", Combinatorics and graph theory (Warsaw, 1987), Banach Center Publ., 25, Warsaw: PWN, 1989, pp. 195–205.
- ↑ Recski, A. (1974), "Enumerating partitional matroids", Studia Scientiarum Mathematicarum Hungarica 9: 247–249 (1975).
 |  |
