Matroids having the same connectivity function (Q1332425)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Matroids having the same connectivity function |
scientific article |
Statements
Matroids having the same connectivity function (English)
0 references
14 February 1995
0 references
Let \(M_ i\) be matroids on the same set \(E\) having rank functions \(r_ i\), and let \(\xi(M_ i,X)= r_ i(X)+ r_ i(E\backslash X)- r_ i(E)+ 1\) for all \(X\subseteq E\) and \(1\leq i\leq 4\). Then \((M_ 1,M_ 2)\) is said to be connected provided that \(\xi(M_ 1,X)+ \xi(M_ 2,X)> 2\) for every \(\varnothing\neq X\subset E\). And moreover, \((M_ 1,M_ 2)\sim (M_ 3,M_ 4)\) provided that \(r_ 1(X)+ r_ 2(X)= r_ 3(X)+ r_ 4(X)\) for every \(X\subseteq E\). Using these concepts the author formulates and proves the following main theorem: If \((M_ 1,M_ 2)\sim (M_ 3,M_ 4)\) and \((M_ 1,M_ 2)\) is connected, then \(B\) is a base of \(M_ 1\) or \(M_ 2\) if and only if \(B\) is a base of \(M_ 3\) or \(M_ 4\). Several interesting consequences are discussed including the following one: Let \(M\) be a connected matroid on \(E\) with dual matroid \(M^*\) such that \(r(M)\neq r(M^*)\). If \(N\) is a matroid on \(E\) having the same connectivity function as \(M\), then \(M= N\) or \(M= N^*\). This is a generalization of an earlier result proved by \textit{P. D. Seymour} [J. Comb. Theory, Ser. B 28, 305-359 (1980; Zbl 0443.05027)] for the case of binary matroids.
0 references
matroids
0 references
rank functions
0 references
connectivity function
0 references