Matroids having the same connectivity function (Q1332425)

From MaRDI portal





scientific article; zbMATH DE number 626347
Language Label Description Also known as
English
Matroids having the same connectivity function
scientific article; zbMATH DE number 626347

    Statements

    Matroids having the same connectivity function (English)
    0 references
    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
    0 references
    matroids
    0 references
    rank functions
    0 references
    connectivity function
    0 references

    Identifiers