“Partition matroid”的意思、由来-开放百科全书

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

Definition

Let

be a collection of disjoint sets, and let

be integers with

. Define a set

to be "independent" when, for every index

. Then the sets that are independent sets in this way form the independent sets of a matroid, called a partition matroid. The sets

are called the blocks of the partition matroid. A basis of the matroid is a set whose intersection with every block

has size exactly

, and 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

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

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

, 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

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 {{nowrap|

.^[6]}}

Enumeration

The number of distinct partition matroids that can be defined over a set of

labeled elements, for

, is

References

1. ^{{citation | last = Recski | first = A. | contribution = On partitional matroids with applications | location = Amsterdam | mr = 0389630 | pages = 1169–1179 | publisher = North-Holland | series = Colloq. Math. Soc. János Bolyai | title = Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vol. III | volume = 10 | year = 1975}}.
2. ^{{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}}.
3. ^E.g., see {{harvtxt|Kashiwabara|Okamoto|Uno|2007}}. {{harvtxt|Lawler|1976}} uses the broader definition but notes that the

restriction is useful in many applications.
4. ^{{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}}.
5. ^{{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}}.
6. ^{{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}}. 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}}.
7. ^{{citation | last = Recski | first = A. | journal = Studia Scientiarum Mathematicarum Hungarica | mr = 0379248 | pages = 247–249 (1975) | title = Enumerating partitional matroids | volume = 9 | year = 1974}}.