partition matroid

Let $C\_i$ be a collection of disjoint sets ("categories"). Let $d\_i$ be integers with $0\backslash le\; d\_i\backslash le\; |C\_i|$ ("capacities"). Define a subset $I\backslash subseteq\; \backslash bigcup\_i\; C\_i$ to be "independent" when, for every index $i$, $|I\backslash cap\; C\_i|\backslash le\; d\_i$. The sets satisfying this condition form the independent sets of a matroid, called a partition matroid.

The sets $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$ has size exactly $d\_i$. A circuit of the matroid is a subset of a single block $C\_i$ with size exactly $d\_i+1$. The rank of the matroid is $\backslash sum\; d\_i$.{{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}}.

Every uniform matroid $U\{\}^r\_n$ is a partition matroid, with a single block $C\_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.E.g., see {{harvtxt|Kashiwabara|Okamoto|Uno|2007}}. {{harvtxt|Lawler|1976}} uses the broader definition but notes that the $d\_i=1$ restriction is useful in many applications.

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.

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.{{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}}.

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.{{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}}.

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 {{nowrap|$d\_i=1$.{{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}}.}}

The number of distinct partition matroids that can be defined over a set of $n$ labeled elements, for $n=0,1,2,\backslash dots$, is

:1, 2, 5, 16, 62, 276, 1377, 7596, 45789, 298626, 2090910, ... {{OEIS|A005387}}.

The exponential generating function of this sequence is $f(x)=\backslash exp(e^x(x-1)+2x+1)$.{{citation

| last = Recski | first = A.

| journal = Studia Scientiarum Mathematicarum Hungarica

| mr = 0379248

| pages = 247–249 (1975)

| title = Enumerating partitional matroids

| volume = 9

| year = 1974}}.

{{reflist}}

Category:Matroid theory

Category:Matching (graph theory)